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

Abstract

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.

34 pages, 5 color figures. Significant changes compared to v1, including a new section about Anderson Localization

Cited by in corpus (15)

• Quantum phase transitions in transverse field spin models: from statistical physics to quantum information
• First order phase transition in the Quantum Adiabatic Algorithm
• Energy gaps in quantum first-order mean-field-like transitions: The problems that quantum annealing cannot solve
• The Power of Adiabatic Quantum Computation with No Sign Problem
• Period Finding with Adiabatic Quantum Computation
• On the relevance of avoided crossings away from quantum critical point to the complexity of quantum adiabatic algorithm
• Continuous-Time Quantum Algorithms for Unstructured Problems
• Adiabatic Quantum Optimization Fails to Solve the Knapsack Problem
• How Fast Can Quantum Annealers Count?
• Quantum ground state isoperimetric inequalities for the energy spectrum of local Hamiltonians
• Why adiabatic quantum annealing is unlikely to yield speed-up
• Anti-crossings and spectral gap during quantum adiabatic evolution
• Statistical mechanics of classical and quantum computational complexity
• On fixed-gap adiabatic quantum computation
• Hard combinatorial problems and minor embeddings on lattice graphs