Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:0912.0746 · Proceedings of the National Academy of Sciences

Anderson localization makes adiabatic quantum optimization fail

B. L. Altshuler, Hari Krovi, Jérémie Roland

Published Jun 24, 2010• 246 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1073/pnas.1002116107

Related papers

Adiabatic Quantum Optimization and Anderson Localization

B. L. Altshuler

Understanding NP-complete problems is a central topic in computer science. 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 will discuss the statistics of the gaps using the borrowed from the theory of quantum disordered systems. 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. We will present the quantitative analysis of the small spectral gaps and discuss possible consequence of this phenomenon on the adiabatic optimization paradigm.

•Jan 1, 2010•0 citations

Adiabatic quantum optimization fails for random instances of NP-complete problems

B. L. Altshuler, Hari Krovi, Jérémie Roland

Adiabatic quantum optimization has attracted a lot of attention because small scale simulations gave hope that it would allow to solve NP-complete problems efficiently. Later, negative results proved the existence of specifically designed hard instances where adiabatic optimization requires exponential time. In spite of this, there was still hope that this would not happen for random instances of NP-complete problems. This is an important issue since random instances are a good model for hard instances that can not be solved by current classical solvers, for which an efficient quantum algorithm would therefore be desirable. Here, we will show that because of a phenomenon similar to Anderson localization, an exponentially small eigenvalue gap appears in the spectrum of the adiabatic Hamiltonian for large random instances, very close to the end of the algorithm. This implies that unfortunately, adiabatic quantum optimization also fails for these instances by getting stuck in a local minimum, unless the computation is exponentially long.

arXiv:0908.2782•Aug 19, 2009•27 citations

Does Adiabatic Quantum Optimization Fail for NP-hard problems?

Neil G. Dickson, M. H. S. Amin

It has been recently argued that adiabatic quantum optimization would fail in solving NP-complete problems because of the occurrence of exponentially small gaps due to crossing of local minima of the final Hamiltonian with its global minimum near the end of the adiabatic evolution. Using perturbation expansion, we analytically show that for the NP-hard problem of maximum independent set there always exist adiabatic paths along which no such crossings occur. Therefore, in order to prove that adiabatic quantum optimization fails for any NP-complete problem, one must prove that it is impossible to find any such path in polynomial time.

•Oct 4, 2010•0 citations

Does Adiabatic Quantum Optimization Fail for NP-Complete Problems?

Neil G. Dickson, M. H. S. Amin

It has been recently argued that adiabatic quantum optimization would fail in solving NP-complete problems because of the occurrence of exponentially small gaps due to crossing of local minima of the final Hamiltonian with its global minimum near the end of the adiabatic evolution. Using perturbation expansion, we analytically show that for the NP-hard problem known as maximum independent set, there always exist adiabatic paths along which no such crossings occur. Therefore, in order to prove that adiabatic quantum optimization fails for any NP-complete problem, one must prove that it is impossible to find any such path in polynomial time.

arXiv:1010.0669•Physical Review Letters•Feb 2, 2011•64 citations

Effect of Local Minima on Adiabatic Quantum Optimization

M. H. S. Amin

We present a perturbative method to estimate the spectral gap for adiabatic quantum optimization, based on the structure of the energy levels in the problem Hamiltonian. We show that, for problems that have an exponentially large number of local minima close to the global minimum, the gap becomes exponentially small making the computation time exponentially long. The quantum advantage of adiabatic quantum computation may then be accessed only via the local adiabatic evolution, which requires phase coherence throughout the evolution and knowledge of the spectrum. Such problems, therefore, are not suitable for adiabatic quantum computation.

arXiv:0709.0528•Physical Review Letters•Apr 4, 2008•36 citations

On the relevance of avoided crossings away from quantum critical point to the complexity of quantum adiabatic algorithm

Sergey Knysh, Vadim Smelyanskiy

Two recent preprints [B. Altshuler, H. Krovi, and J. Roland, "Quantum adiabatic optimization fails for random instances of NP-complete problems", arXiv:0908.2782 and "Anderson localization casts clouds over adiabatic quantum optimization", arXiv:0912.0746] argue that random 4th order perturbative corrections to the energies of local minima of random instances of NP-complete problem lead to avoided crossings that cause the failure of quantum adiabatic algorithm (due to exponentially small gap) close to the end, for very small transverse field that scales as an inverse power of instance size N. The theoretical portion of this work does not to take into account the exponential degeneracy of the ground and excited states at zero field. A corrected analysis shows that unlike those in the middle of the spectrum, avoided crossings at the edge would require high [O(1)] transverse fields, at which point the perturbation theory may become divergent due to quantum phase transition. This effect manifests itself only in large instances [exp(0.02 N) >> 1], which might be the reason it had not been observed in the authors' numerical work. While we dispute the proposed mechanism of failure of quantum adiabatic algorithm, we cannot draw any conclusions on its ultimate complexity.

arXiv:1005.3011•May 17, 2010•21 citations
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.
Understanding NP-complete problems is a central topic in computer science. 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 will discuss the statistics of the gaps using the borrowed from the theory of quantum disordered systems. 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. We will present the quantitative analysis of the small spectral gaps and discuss possible consequence of this phenomenon on the adiabatic optimization paradigm.
Adiabatic quantum optimization has attracted a lot of attention because small scale simulations gave hope that it would allow to solve NP-complete problems efficiently. Later, negative results proved the existence of specifically designed hard instances where adiabatic optimization requires exponential time. In spite of this, there was still hope that this would not happen for random instances of NP-complete problems. This is an important issue since random instances are a good model for hard instances that can not be solved by current classical solvers, for which an efficient quantum algorithm would therefore be desirable. Here, we will show that because of a phenomenon similar to Anderson localization, an exponentially small eigenvalue gap appears in the spectrum of the adiabatic Hamiltonian for large random instances, very close to the end of the algorithm. This implies that unfortunately, adiabatic quantum optimization also fails for these instances by getting stuck in a local minimum, unless the computation is exponentially long.
It has been recently argued that adiabatic quantum optimization would fail in solving NP-complete problems because of the occurrence of exponentially small gaps due to crossing of local minima of the final Hamiltonian with its global minimum near the end of the adiabatic evolution. Using perturbation expansion, we analytically show that for the NP-hard problem of maximum independent set there always exist adiabatic paths along which no such crossings occur. Therefore, in order to prove that adiabatic quantum optimization fails for any NP-complete problem, one must prove that it is impossible to find any such path in polynomial time.
It has been recently argued that adiabatic quantum optimization would fail in solving NP-complete problems because of the occurrence of exponentially small gaps due to crossing of local minima of the final Hamiltonian with its global minimum near the end of the adiabatic evolution. Using perturbation expansion, we analytically show that for the NP-hard problem known as maximum independent set, there always exist adiabatic paths along which no such crossings occur. Therefore, in order to prove that adiabatic quantum optimization fails for any NP-complete problem, one must prove that it is impossible to find any such path in polynomial time.
We present a perturbative method to estimate the spectral gap for adiabatic quantum optimization, based on the structure of the energy levels in the problem Hamiltonian. We show that, for problems that have an exponentially large number of local minima close to the global minimum, the gap becomes exponentially small making the computation time exponentially long. The quantum advantage of adiabatic quantum computation may then be accessed only via the local adiabatic evolution, which requires phase coherence throughout the evolution and knowledge of the spectrum. Such problems, therefore, are not suitable for adiabatic quantum computation.
Two recent preprints [B. Altshuler, H. Krovi, and J. Roland, "Quantum adiabatic optimization fails for random instances of NP-complete problems", arXiv:0908.2782 and "Anderson localization casts clouds over adiabatic quantum optimization", arXiv:0912.0746] argue that random 4th order perturbative corrections to the energies of local minima of random instances of NP-complete problem lead to avoided crossings that cause the failure of quantum adiabatic algorithm (due to exponentially small gap) close to the end, for very small transverse field that scales as an inverse power of instance size N. The theoretical portion of this work does not to take into account the exponential degeneracy of the ground and excited states at zero field. A corrected analysis shows that unlike those in the middle of the spectrum, avoided crossings at the edge would require high [O(1)] transverse fields, at which point the perturbation theory may become divergent due to quantum phase transition. This effect manifests itself only in large instances [exp(0.02 N) >> 1], which might be the reason it had not been observed in the authors' numerical work. While we dispute the proposed mechanism of failure of quantum adiabatic algorithm, we cannot draw any conclusions on its ultimate complexity.