Source-linked AI summary
Anderson localization casts clouds over adiabatic quantum optimization
Boris Altshuler, Hari Krovi, Jeremie Roland
TL;DR
AQO faces fundamental difficulties in solving NP-complete problems. This paper examines ground-state anti-crossings and reports that minimal gaps for large random instances decay faster than exponentially, making wrong solutions likely.
Problem
AQO faces fundamental difficulties in using quantum computation to solve NP-complete problems.
Method
The paper analyzes anti-crossings between the ground state and excited states in AQO.
Results
As N →∞, the typical minimal gap for random instances decays faster than exponentially, and AQO becomes likely to yield a wrong solution.
Takeaways & Limitations
The reported gap scaling limits AQO's ability to solve random NP-complete instances in polynomial time.
Takeaways & Limitations
The analysis adopts the most conservative limitation on the solution of the problem in polynomial time using AQO for random instances.
Abstract
from arXiv · showhide
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 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.