Adiabatic Quantum Computation Is Equivalent to Standard Quantum Computation
The DOI matches its Crossref record; 36 of the 36 references it cites were found in a registry or an index.
Abstract
The model of adiabatic quantum computation is a relatively recent model of quantum computation that has attracted attention in the physics and computer science communities. We describe an efficient adiabatic simulation of any given quantum circuit. This implies that the adiabatic computation model and the standard circuit-based 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 one to state the main open problems in quantum computation using well-studied mathematical objects such as eigenvectors and spectral gaps of Hamiltonians.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
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?
In the citing paper
“In principle, adiabatic quantum computing is equivalent to universal quantum computing [187].This universality holds only if the evolution is allowed to be nonstoquastic, meaning that the Hamiltonian has nonnegative off-diagonal elements at some point of the evolution.”
From The prospects of quantum computing in computational molecular biology (2021) · cites this paper as [187]
Citations
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 · cited 1×
“It is a crucial ingredient in topological (and later, geometrical) quantum computation [18,23,27].”
BackgroundQuantum Mechanics Helps in Searching for a Needle in a Haystack
Grover, L. K. (1997) · Physical Review Letters · doi:10.1103/physrevlett.79.325 · Cited by 4,306 · cited 1×
“In [9,30] it was shown that Grover’s quadratic speed-up for an unsorted search [16] can be realized as an adiabatic computation.”
BackgroundQuantum annealing in the transverse Ising model
Kadowaki, T., & Nishimori, H. (1998) · Physical Review E · doi:10.1103/physreve.58.5355 · Cited by 2,339
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 · cited 1×
“[14, 15] suggested an ingenious paradigm for quantum algorithms calledadiabatic computation , which attracted considerable attention [14–21] since it w as shown to exhibit promising algorithmic capabilities [16–18], as well as inherent robustness against decoherence and control errors [20].”
BackgroundAn area law for one-dimensional quantum systems
Hastings, M. B. (2007) · Journal of Statistical Mechanics: Theory and Experiment · doi:10.1088/1742-5468/2007/08/p08024 · Cited by 1,131
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,055 · cited 1×
“Experimental realizat ion of small-scale adiabatic computation was already demonstrated [31].”
MethodFeynman, R. P. (1985) · Optics News · doi:10.1364/on.11.2.000011 · Cited by 1,023
Geometric quantum computation using nuclear magnetic resonance
Jones, J. A., Vedral, V., Ekert, A., & Castagnoli, G. (2000) · Nature · doi:10.1038/35002528 · Cited by 812 · cited 1×
“It is a crucial ingredient in topological (and later, geometrical) quantum computation [ 18 ,23,27].”
BackgroundTheory 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 · cited 1×
“Moreover, [11,29,32] showed that adiabatic computation can ‘tunnel’ through wide energy barriers and thus outperform simulated annealing, a classical counterpart of the adiabatic model.”
BackgroundEfficient Quantum Algorithms for Simulating Sparse Hamiltonians
Berry, D. W., Ahokas, G., Cleve, R., & Sanders, B. C. (2007) · Communications in Mathematical Physics · doi:10.1007/s00220-006-0150-x · Cited by 692
Research works printed but not linked: 25
- D. Aharonov, W. van Dam, J. Kempe, Z. Landau, S. Lloyd, and O. Regev, Adiabatic quantum computation is equivalent to standard quantum computation , in Proceedings of the 45th IEEE Symposium on Foundations of Computer Science, Rome, Italy, 2004, pp. 42–51. · DOI · Paper page
- D. Aharonov, D. Gottesman, S. Irani, and J. Kempe, The power of quantum systems on a line , in Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, 2007, pp. 373–383. · DOI
- D. Aharonov, A. Kitaev, and N. Nisan, Quantum circuits with mixed states , in Proceedings of the 30th Annual ACM Symposium on Theory of Computing, Dallas, TX, 1998, pp. 20–30. · DOI · Paper page
- D. Aharonov and T. Naveh, Quantum NP - a Survey , preprint, 2002; available online from http://arxiv.org/abs/quant-ph/0210077. · arXiv
- D. Aharonov and A. Ta-Shma, Adiabatic quantum state generation and statistical zero-knowledge , in Proceedings of the 35th Annual ACM Symposium on Theory of Computing, San Diego, CA, 2003, pp. 20–29. · DOI · Paper page
- A. Ambainis and O. Regev, An Elementary Proof of the Quantum Adiabatic Theorem , preprint, 2004; available online from http://arxiv.org/abs/quant-ph/0411152v2. · arXiv
- B. Apolloni, N. Cesa-Bianchi, and D. de Falco, A numerical implementation of quantum annealing , in Proceedings of the Ascona/Locarno Conference, 1988, pp. 97–111.
- R. Bhatia, Matrix Analysis , Grad. Texts in Math. 169, Springer-Verlag, New York, 1997. · DOI · Paper page
- A. Childs, Universal Computation by Quantum Walk , preprint, 2008; available online from http://arxiv.org/PS_cache/arxiv/pdf/0806/0806.1972v1.pdf.
- W. van Dam, M. Mosca, and U. Vazirani, How powerful is adiabatic quantum computation? , in Proceedings of the 42nd IEEE Symposium on Foundation of Computer Science, Las Vegas, NV, IEEE Computer Society, Los Alamitos, CA, 2001, pp. 279–287. · DOI · Paper page
- L. Eldar and O. Regev, Quantum SAT for a qutrit-cinquit pair is $QMA_1$-complete , in Proceedings of the 35th International Colloquium on Automata, Languages and Programming, Reykjavik, Iceland, 2008, pp. 881–892. · DOI
- E. Farhi, J. Goldstone, and S. Gutmann, Quantum Adiabatic Evolution Algorithms versus Simulated Annealing , preprint, 2002; available online from http://arxiv.org/abs/quant-ph/0201031v1. · arXiv
- E. Farhi, J. Goldstone, and S. Gutmann, Quantum Adiabatic Evolution Algorithms with Different Paths , preprint, 2002; available online from http://arxiv.org/abs/quant-ph/0208135v1. · arXiv
- E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser, Quantum Computation by Adiabatic Evolution , preprint, 2000; available online from http://arxiv.org/abs/quant-ph/0001106v1. · arXiv
- J. Friedman, Expanding Graphs , DIMACS Ser. Discrete Math. Theoret. Comput. Sci., AMS, Providence, RI, 1993. · doi:10.1090/dimacs/010
- R. A. Horn and C. R. Johnson, Matrix Analysis , Cambridge University Press, Cambridge, UK, 1985. · DOI · Paper page
- A. Kitaev, A. Shen, and M. Vyalyi, Classical and Quantum Computation , Grad. Stud. in Math. 47, AMS, Providence, RI, 2002. · DOI · Paper page
- L. Lovász, Random walks on graphs: A survey , in Combinatorics, Paul Erdős is Eighty, Vol. 2 (Keszthely, 1993), Bolyai Soc. Math. Stud. 2, János Bolyai Math. Soc., Budapest, 1996, pp. 353–397.
- A. Messiah, Quantum Mechanics , John Wiley and Sons, New York, 1958.
- D. Nagaj, Local Hamiltonians in Quantum Computation , Ph.D. thesis, MIT, 2008; available online from http://eprintweb.org/S/article/arxiv/0808.2117.
- M. Nielsen and I. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, Cambridge, UK, 2000.
- X. Peng, Z. Liao, N. Xu, G. Qin, X. Zhou, D. Suter, and J. Du, A Quantum Adiabatic Algorithm for Factorization and Its Experimental Implementation , preprint, 2008; available online from http://arxiv.org/abs/0808.1935v1. · DOI · Paper page
- B. Pepper, Adiabatic Computing Using 2-Local Hamiltonians on a Line , preprint.
- N. Schuch and F. Verstraete, Interacting Electrons, Density Functional Theory, and Quantum Merlin Arthur , preprint, 2007; available online from http://arxiv.org/abs/0712.0483v1. · arXiv
- A. Sinclair and M. Jerrum, Approximate counting, uniform generation, and rapidly mixing Markov chains (extended abstract), in Graph-Theoretic Concepts in Computer Science (Staffelstein, 1987), Lecture Notes in Comput. Sci. 314, Springer-Verlag, Berlin, 1988, pp. 134–148. · doi:10.1007/3-540-19422-3_11
Cited by
Quantum Computing in the NISQ era and beyond
Preskill, J. (2018) · Quantum · doi:10.22331/q-2018-08-06-79 · Cited by 8,830
The theory of variational hybrid quantum-classical algorithms
McClean, J. R., Romero, J., Babbush, R., & Aspuru-Guzik, A. (2016) · New Journal of Physics · doi:10.1088/1367-2630/18/2/023023 · Cited by 2,227
Noisy intermediate-scale quantum algorithms
Bharti, K., Cervera-Lierta, A., Kyaw, T. H., Haug, T., Alperin-Lea, S., Anand, A., Degroote, M., Heimonen, H., Kottmann, J. S., Menke, T., et al. (2022) · Reviews of Modern Physics · doi:10.1103/revmodphys.94.015004 · Cited by 2,231
Quantum computational chemistry
McArdle, S., Endo, S., Aspuru-Guzik, A., Benjamin, S. C., & Yuan, X. (2020) · Reviews of Modern Physics · doi:10.1103/revmodphys.92.015003 · Cited by 1,621
Superconducting Qubits: Current State of Play
Kjaergaard, M., Schwartz, M. E., Braumüller, J., Krantz, P., Wang, J. I.-J., Gustavsson, S., & Oliver, W. D. (2020) · Annual Review of Condensed Matter Physics · doi:10.1146/annurev-conmatphys-031119-050605 · Cited by 1,544
Metadata
- Authors
- Aharonov, D., van Dam, W., Kempe, J., Landau, Z., Lloyd, S., & Regev, O.
- Venue
- SIAM Review
- Published
- 2008-01
- Volume
- 50
- Issue
- 4
- Pages
- 755-787
- ISSN
- 0036-1445 (ISSN-L)
- 1095-7200
- OpenAlex
- W2041432245
- Semantic Scholar
- ab891721d230583649a4af16d8af6f602ff2f6b8
- Cited by
- 395
- References
- 35
- Citations by year
- 2026: 15 · 2025: 30 · 2024: 26 · 2023: 53 · 2022: 36 · 2021: 48 · 2020: 40 · 2019: 25 · 2018: 20 · 2017: 36 · 2016: 9 · 2015: 12 · 2014: 7 · 2013: 4 · 2012: 9
- FWCI
- 7.93
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- SIAM Review (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Information and Cryptography
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
- Keywords
- adiabatic quantum computation, eigenvectors, nearest-neighbor interactions, two-dimensional grids
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
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.