Anderson localization makes adiabatic quantum optimization fail
- 24 June 2010
- journal article
- Published by Proceedings of the National Academy of Sciences in Proceedings of the National Academy of Sciences of the United States of America
- Vol. 107 (28), 12446-12450
- https://doi.org/10.1073/pnas.1002116107
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.Keywords
This publication has 18 references indexed in Scilit:
- First-order quantum phase transition in adiabatic quantum computationPhysical Review A, 2009
- Size Dependence of the Minimum Excitation Gap in the Quantum Adiabatic AlgorithmPhysical Review Letters, 2008
- Simple Glass Models and Their Quantum AnnealingPhysical Review Letters, 2008
- HOW TO MAKE THE QUANTUM ADIABATIC ALGORITHM FAILInternational Journal of Quantum Information, 2008
- Adiabatic Quantum Computation is Equivalent to Standard Quantum ComputationSIAM Journal on Computing, 2007
- Simulation of many-qubit quantum computation with matrix product statesPhysical Review A, 2006
- Exponential complexity of an adiabatic algorithm for an NP-complete problemPhysical Review A, 2006
- Adiabatic quantum computing for random satisfiability problemsPhysical Review A, 2003
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum ComputerSIAM Journal on Computing, 1997
- Absence of Diffusion in Certain Random LatticesPhysical Review B, 1958