Abstract

Adiabatic quantum computation has recently attracted attention in the physics and computer science communities, but its computational power has been unknown. We settle this question and describe an efficient adiabatic simulation of any given quantum algorithm, which implies that the adiabatic computation model and the conventional quantum circuit model are polynomially equivalent. Our result can be extended to the physically realistic setting of particles arranged on a two-dimensional grid with nearest neighbor interactions. The equivalence between the models provides a new vantage point from which to tackle the central issues in quantum computation, namely designing new quantum algorithms and constructing fault tolerant quantum computers. In particular, by translating the main open questions in quantum algorithms to the language of spectral gaps of sparse matrices, the result makes quantum algorithmic questions accessible to a wider scientific audience, acquainted with mathematical physics, expander theory and rapidly mixing Markov chains.

Keywords

Quantum computerAdiabatic quantum computationComputationAdiabatic processQuantum algorithmQuantum operationQuantum circuitQuantumEquivalence (formal languages)Open quantum systemStatistical physicsPhysicsQuantum mechanicsQuantum error correctionComputer scienceMathematicsAlgorithmDiscrete mathematics

Affiliated Institutions

Related Publications

Adiabatic quantum computation

Tameem Albash , Daniel A. Lidar

Adiabatic quantum computing (AQC) started as an approach to solving optimization problems, and has evolved into an important universal alternative to the standard circuit model ...

2018 Reviews of Modern Physics 1385 citations

Quantum circuit complexity

Andrew Chi-Chih Yao

We propose a complexity model of quantum circuits analogous to the standard (acyclic) Boolean circuit model. It is shown that any function computable in polynomial time by a qua...

2002 Proceedings of 1993 IEEE 34th Annual ... 633 citations

Publication Info

Year
2008
Type
article
Volume
50
Issue
4
Pages
755-787
Citations
380
Access
Closed

External Links

View on DOI.org

Social Impact

Altmetric
PlumX Metrics

Social media, news, blog, policy document mentions

Citation Metrics

380
OpenAlex

Cite This

Dorit Aharonov, Wim van Dam, Julia Kempe et al. (2008). Adiabatic Quantum Computation Is Equivalent to Standard Quantum Computation. SIAM Review , 50 (4) , 755-787. https://doi.org/10.1137/080734479

Identifiers

DOI
10.1137/080734479