Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation
Abstract
Adiabatic quantum computation has recently attracted attention in the physics and computer science communities, but its computational power was unknown. We describe an efficient adiabatic simulation of any given quantum algorithm, which implies that the adiabatic computation model and the conventional quantum computation 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 allows stating the main open problems in quantum computation using well‐studied mathematical objects such as eigenvectors and spectral gaps of sparse matrices.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
AQC has been proved universal for quantum computing, equivalent to the standard circuit model up to polynomial resource-overhead.
“More generally, AQC has been proved to be universal for quantum computing, being equivalent to the standard circuit model of quantum computation up to polynomial resource-overhead15.”
From Superadiabatic Controlled Evolutions and Universal Quantum Computation (2015) · cites this paper as [15]
Cites
Fault-tolerant quantum computation by anyons
Kitaev, A. Y. (2003) · Annals of Physics · doi:10.1016/s0003-4916(02)00018-0 · Cited by 7,238 · see citing works
A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
Farhi, E., Goldstone, J., Gutmann, S., Lapan, J., Lundgren, A., & Preda, D. (2001) · Science · doi:10.1126/science.1057726 · Cited by 2,056 · see citing works
On the Adiabatic Theorem of Quantum Mechanics
Kato, T. (1950) · Journal of the Physical Society of Japan · doi:10.1143/jpsj.5.435 · Cited by 1,068 · see citing works
Geometric quantum computation using nuclear magnetic resonance
Jones, J. A., Vedral, V., EKERT, A. K., & Castagnoli, G. (2000) · Nature · doi:10.1038/35002528 · Cited by 795 · see citing works
Theory of Quantum Annealing of an Ising Spin Glass
Santoro, G. E., Martoňák, R., Tosatti, E., & Car, R. (2002) · Science · doi:10.1126/science.1068774 · Cited by 734 · see citing works
Adiabatic Theorem without a Gap Condition
Avron, J. E., & Elgart, A. (1999) · Communications in Mathematical Physics · doi:10.1007/s002200050620 · Cited by 205 · see citing works
Experimental Implementation of an Adiabatic Quantum Optimization Algorithm
Steffen, M., van Dam, W., Hogg, T., Breyta, G., & Chuang, I. L. (2003) · Physical Review Letters · doi:10.1103/physrevlett.90.067903 · Cited by 180 · see citing works
QUANTUM HOLONOMIES FOR QUANTUM COMPUTING
Pachos, J. K., & Paolo Zanardi, A. (2001) · International Journal of Modern Physics B · doi:10.1142/s0217979201004836 · Cited by 131 · see citing works
3-Local Hamiltonian is QMA-complete
Kempe, J., & Regev, O. (2003) · Quantum Information and Computation · doi:10.26421/qic3.3-7 · Cited by 107 · see citing works
Self-citationImproved Bounds on the Spectral Gap Above Frustration-Free Ground States of Quantum Spin Chains
Spitzer, W. L., & Starr, S. L. (2003) · Letters in Mathematical Physics · doi:10.1023/a:1023059518455 · Cited by 24 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
Quantum annealing with manufactured spins
Johnson, M. W., Amin, M. H. S., Gildert, S., Lanting, T., Hamze, F., Dickson, N., Harris, R., Berkley, A. J., Johansson, J., Bunyk, P., et al. (2011) · Nature · doi:10.1038/nature10012 · Cited by 1,891 · see citing works
Quantum computation and quantum-state engineering driven by dissipation
Verstraete, F., Wolf, M. M., & Ignacio Cirac, J. (2009) · Nature Physics · doi:10.1038/nphys1342 · Cited by 1,570 · see citing works
Albash, T., & Lidar, D. A. (2018) · Reviews of Modern Physics · doi:10.1103/revmodphys.90.015002 · Cited by 1,546 · see citing works
Universal Computation by Quantum Walk
Childs, A. M. (2009) · Physical Review Letters · doi:10.1103/physrevlett.102.180501 · Cited by 1,002 · see citing works
<i>Colloquium</i> : Quantum annealing and analog quantum computation
Das, A., & Chakrabarti, B. K. (2008) · Reviews of Modern Physics · doi:10.1103/revmodphys.80.1061 · Cited by 700 · see citing works
Simulating Chemistry Using Quantum Computers
Kassal, I., Whitfield, J. D., Perdomo-Ortiz, A., Yung, M.-H., & Aspuru-Guzik, A. (2011) · Annual Review of Physical Chemistry · doi:10.1146/annurev-physchem-032210-103512 · Cited by 352 · see citing works
Quantum algorithms for algebraic problems
Childs, A. M., & van Dam, W. (2010) · Reviews of Modern Physics · doi:10.1103/revmodphys.82.1 · Cited by 344 · see citing works
Quantum Supremacy through the Quantum Approximate Optimization Algorithm
Farhi, E., & Harrow, A. W. (2016) · arXiv · doi:10.48550/arxiv.1602.07674 · Cited by 331 · see citing works
Quantum computing for energy systems optimization: Challenges and opportunities
Ajagekar, A., & You, F. (2019) · Energy · doi:10.1016/j.energy.2019.04.186 · Cited by 289 · see citing works
Ajagekar, A., Humble, T., & You, F. (2020) · Computers & Chemical Engineering · doi:10.1016/j.compchemeng.2019.106630 · Cited by 191 · see citing works
Dissipative Quantum Church-Turing Theorem
Kliesch, M., Barthel, T., Gogolin, C., Kastoryano, M., & Eisert, J. (2011) · Physical Review Letters · doi:10.1103/physrevlett.107.120501 · Cited by 154 · see citing works
Superadiabatic Controlled Evolutions and Universal Quantum Computation
Santos, A. C., & Sarandy, M. S. (2015) · Scientific Reports · doi:10.1038/srep15775 · Cited by 125 · see citing works
Quantum-resistance in blockchain networks
Allende, M., León, D. L., Cerón, S., Pareja, A., Pacheco, E., Leal, A., Da Silva, M., Pardo, A., Jones, D., Worrall, D. J., et al. (2023) · Scientific Reports · doi:10.1038/s41598-023-32701-6 · Cited by 109 · see citing works
Biology and medicine in the landscape of quantum advantages
Cordier, B. A., Sawaya, N. P. D., Guerreschi, G. G., & McWeeney, S. K. (2022) · Journal of The Royal Society Interface · doi:10.1098/rsif.2022.0541 · Cited by 87 · see citing works
Classical signature of quantum annealing
Smolin, J. A., & Smith, G. (2014) · Frontiers in Physics · doi:10.3389/fphy.2014.00052 · Cited by 79 · see citing works
Nested quantum annealing correction
Vinci, W., Albash, T., & Lidar, D. A. (2016) · npj Quantum Information · doi:10.1038/npjqi.2016.17 · Cited by 57 · see citing works
Kendon, V. M., Nemoto, K., & Munro, W. J. (2010) · Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rsta.2010.0017 · Cited by 41 · see citing works
Quantum gates with controlled adiabatic evolutions
Hen, I. (2015) · Physical Review A · doi:10.1103/physreva.91.022309 · Cited by 37 · see citing works
Hamiltonian gadgets with reduced resource requirements
Cao, Y., Babbush, R., Biamonte, J., & Kais, S. (2015) · Physical Review A · doi:10.1103/physreva.91.012315 · Cited by 35 · see citing works
Adiabatic optimization versus diffusion Monte Carlo methods
Jarret, M., Jordan, S. P., & Lackey, B. (2016) · Physical Review A · doi:10.1103/physreva.94.042318 · Cited by 36 · see citing works
- Authors
- Aharonov, D., van Dam, W., Kempe, J., Landau, Z., Lloyd, S., & Regev, O.
- Affiliations
- Hebrew University of Jerusalem (IL)
- Université Paris-Sud (FR)
- City University of New York (US)
- Massachusetts Institute of Technology (US)
- University of California, Berkeley (US)
- Venue
- SIAM Journal on Computing
- Published
- 2007-01
- Volume
- 37
- Issue
- 1
- Pages
- 166-194
- ISSN
- 0097-5397 (ISSN-L)
- 1095-7111
- OpenAlex
- W2086456560
- Cited by
- 457
- References
- 10
- Citations by year
- 2026: 15 · 2025: 16 · 2024: 22 · 2023: 13 · 2022: 20 · 2021: 31 · 2020: 25 · 2019: 22 · 2018: 18 · 2017: 10 · 2016: 19 · 2015: 24 · 2014: 43 · 2013: 22 · 2012: 22
- FWCI
- 40.64
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- SIAM Journal on Computing (publishedVersion)
- Funders
- National Science Foundation (0121555, 9987845)
- U.S. Department of Energy (FC02-94ER40818, DF-FC02-94ER40818)
- Deutscher Akademischer Austauschdienst
- Defense Advanced Research Projects Agency
- U.S. Air Force
- Advanced Research Projects Agency
- Division of Mathematical Sciences
- Army Research Office (DAAD19-03-1-0082)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Keywords
- adiabatic quantum computation, quantum computing, computational equivalence, quantum algorithms, spectral gap, sparse matrices, eigenvectors, nearest-neighbor interactions, two-dimensional grids, computational complexity
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
