Anderson localization makes adiabatic quantum optimization fail

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

Full description

Saved in:
Bibliographic Details
Published in:Proceedings of the National Academy of Sciences - PNAS 2010-07, Vol.107 (28), p.12446-12450
Main Authors: Altshuler, Boris, Krovi, Hari, Roland, Jérémie, Halperin, Bertrand I.
Format: Article
Language:English
Subjects:
Algorithms
Computer science
Cost functions
Energy
Ground state
Optimization
Perturbation theory
Physical Sciences
Physics
Physiological Phenomena
Polynomials
Quantum computers
Quantum efficiency
Quantum physics
Time Factors
Trajectories
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0027-8424
1091-6490
DOI:10.1073/pnas.1002116107