Student or educator? Sign up with your school email and get 6 months of Pro free.
CoChat

The DOI matches its Crossref record; 36 of the 36 references it cites were found in a registry or an index.

Adiabatic Quantum Computation Is Equivalent to Standard Quantum Computation

Aharonov, Dorit, van Dam, Wim, Kempe, Julia, Landau, Zeph, Lloyd, Seth, Regev, Oded · 2008 · SIAM Review

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

Crossref · 10.1137/080734479

Cites

36 of 36 references verified0 citation errors · 0 not checkable

Statistics

Recomputing p-values needs the paper’s full text.

Verification

Claims the paper makes

This paper’s full text isn’t openly available, so its claims and self-check weren’t run. The registry and citation checks still apply.

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?

Citations

Cites

Research works printed but not linked: 25

  1. 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
  2. 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
  3. 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
  4. D. Aharonov and T. Naveh, Quantum NP - a Survey , preprint, 2002; available online from http://arxiv.org/abs/quant-ph/0210077. · arXiv
  5. 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
  6. 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
  7. 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.
  8. R. Bhatia, Matrix Analysis , Grad. Texts in Math. 169, Springer-Verlag, New York, 1997. · DOI · Paper page
  9. A. Childs, Universal Computation by Quantum Walk , preprint, 2008; available online from http://arxiv.org/PS_cache/arxiv/pdf/0806/0806.1972v1.pdf.
  10. 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
  11. 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
  12. 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
  13. 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
  14. 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
  15. J. Friedman, Expanding Graphs , DIMACS Ser. Discrete Math. Theoret. Comput. Sci., AMS, Providence, RI, 1993. · doi:10.1090/dimacs/010
  16. R. A. Horn and C. R. Johnson, Matrix Analysis , Cambridge University Press, Cambridge, UK, 1985. · DOI · Paper page
  17. A. Kitaev, A. Shen, and M. Vyalyi, Classical and Quantum Computation , Grad. Stud. in Math. 47, AMS, Providence, RI, 2002. · DOI · Paper page
  18. 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.
  19. A. Messiah, Quantum Mechanics , John Wiley and Sons, New York, 1958.
  20. D. Nagaj, Local Hamiltonians in Quantum Computation , Ph.D. thesis, MIT, 2008; available online from http://eprintweb.org/S/article/arxiv/0808.2117.
  21. M. Nielsen and I. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, Cambridge, UK, 2000.
  22. 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
  23. B. Pepper, Adiabatic Computing Using 2-Local Hamiltonians on a Line , preprint.
  24. 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
  25. 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

See all 395

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
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.