The DOI matches its Crossref record; 7 of the 7 references it cites were found in a registry or an index.
Anderson localization makes adiabatic quantum optimization fail
Open accessAbstract
Understanding NP-complete problems is a central topic in computer science (NP stands for nondeterministic polynomial time). This is why adiabatic quantum optimization has attracted so much attention, as it provided a new approach to tackle NP-complete problems using a quantum computer. The efficiency of this approach is limited by small spectral gaps between the ground and excited states of the quantum computer’s Hamiltonian. We show that the statistics of the gaps can be analyzed in a novel way, borrowed from the study of quantum disordered systems in statistical mechanics. It turns out that due to a phenomenon similar to Anderson localization, exponentially small gaps appear close to the end of the adiabatic algorithm for large random instances of NP-complete problems. This implies that unfortunately, adiabatic quantum optimization fails: The system gets trapped in one of the numerous local minima.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Absence of Diffusion in Certain Random Lattices
Anderson, P. W. (1958) · Physical Review · doi:10.1103/physrev.109.1492 · Cited by 12,468 · cited 3×
“This is the limit that was shown to be relevant for the localization problem (20, 24).”
BackgroundMethodPolynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Shor, P. W. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539795293172 · Cited by 8,472
Computational Complexity: A Modern Approach
Arora, S., & Barak, B. (2009) · doi:10.1017/cbo9780511804090 · Cited by 1,690
Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation
Aharonov, D., van Dam, W., Kempe, J., Landau, Z., Lloyd, S., & Regev, O. (2007) · SIAM Journal on Computing · doi:10.1137/s0097539705447323 · Cited by 457
How powerful is adiabatic quantum computation?
van Dam, W., Mosca, M., & Vazirani, U. (2001) · Proceedings 42nd IEEE Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2001.959902 · Cited by 175 · cited 1×
“Previously, it was shown that the gap can become exponentially small under specific conditions, such as a bad choice of initial Hamiltonian (8, 9), or for specifically designed hard instances (10, 11).”
BackgroundThe quantum adiabatic optimization algorithm and local minima
Reichardt, B. W. (2004) · Proceedings of the thirty-sixth annual ACM symposium on Theory of computing · doi:10.1145/1007352.1007428 · Cited by 110 · cited 2×
“Previously, it was shown that the gap can become exponentially small under specific conditions, such as a bad choice of initial Hamiltonian (8, 9), or for specifically designed hard instances (10, 11).”
BackgroundHOW TO MAKE THE QUANTUM ADIABATIC ALGORITHM FAIL
FARHI, E., GOLDSTONE, J., GUTMANN, S., & NAGAJ, D. (2008) · International Journal of Quantum Information · doi:10.1142/s021974990800358x · Cited by 81
Cited by
Ising formulations of many NP problems
Lucas, A. (2014) · Frontiers in Physics · doi:10.3389/fphy.2014.00005 · Cited by 2,512
Albash, T., & Lidar, D. A. (2018) · Reviews of Modern Physics · doi:10.1103/revmodphys.90.015002 · Cited by 1,546
Evidence for quantum annealing with more than one hundred qubits
Boixo, S., Rønnow, T. F., Isakov, S. V., Wang, Z., Wecker, D., Lidar, D. A., Martinis, J. M., & Troyer, M. (2014) · Nature Physics · doi:10.1038/nphys2900 · Cited by 810
“Many spins would need to be flipped to reach a ground state, which results in small tunneling matrix elements between the state found and the true ground state and thus small gap avoided level crossings [26].”
BackgroundPerspectives of quantum annealing: methods and implementations
Hauke, P., Katzgraber, H. G., Lechner, W., Nishimori, H., & Oliver, W. D. (2020) · Reports on Progress in Physics · doi:10.1088/1361-6633/ab85b8 · Cited by 507
What is the Computational Value of Finite-Range Tunneling?
Denchev, V. S., Boixo, S., Isakov, S. V., Ding, N., Babbush, R., Smelyanskiy, V., Martinis, J., & Neven, H. (2016) · Physical Review X · doi:10.1103/physrevx.6.031015 · Cited by 399
Metadata
- Authors
- Altshuler, B., Krovi, H., & Roland, J.
- Venue
- Proceedings of the National Academy of Sciences
- Published
- 2010-06-24
- Volume
- 107
- Issue
- 28
- Pages
- 12446-12450
- ISSN
- 0027-8424 (ISSN-L)
- 1091-6490
- OpenAlex
- W2076227063
- Cited by
- 246
- References
- 7
- FWCI
- 11.56
- Type
- journal article
- Language
- en
- Open access
- green
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.