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:1010.0009

Unstructured Randomness, Small Gaps and Localization

Edward Farhi, Jeffrey Goldstone, David Gosset, Sam Gutmann, Peter W. Shor

Published Sep 30, 2010• 0 citations
arXivHTMLPDF

Abstract

We study the Hamiltonian associated with the quantum adiabatic algorithm with a random cost function. Because the cost function lacks structure we can prove results about the ground state. We find the ground state energy as the number of bits goes to infinity, show that the minimum gap goes to zero exponentially quickly, and we see a localization transition. We prove that there are no levels approaching the ground state near the end of the evolution. We do not know which features of this model are shared by a quantum adiabatic algorithm applied to random instances of satisfiability since despite being random they do have bit structure.

DOI
10.48550/arxiv.1010.0009

Related papers

Unstructured randomness, small gaps and localization

Edward Farhi, Jeffrey Goldstone, David Gosset +2 more

We study the Hamiltonian associated with the quantum adiabatic algorithm with a random cost function. Because the cost function lacks structure we can prove results about the ground state. We find the ground state energy as the number of bits goes to infinity, show that the minimum gap goes to zero exponentially quickly, and we see a localization transition. We prove that there are no levels approaching the ground state near the end of the evolution. We do not know which features of this model are shared by a quantum adiabatic algorithm applied to random instances of satisfiability since despite being random they do have bit structure.

Quantum Information and Computation•Sep 1, 2011•15 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

Adiabatic quantum computing for random satisfiability problems

Tad Hogg

The discrete formulation of adiabatic quantum computing is compared with other search methods, classical and quantum, for random satisfiability (SAT) problems. With the number of steps growing only as the cube of the number of variables, the adiabatic method gives solution probabilities close to 1 for problem sizes feasible to evaluate via simulation on current computers. However, for these sizes the minimum energy gaps of most instances are fairly large, so the good performance scaling seen for small problems may not reflect asymptotic behavior where costs are dominated by tiny gaps. Moreover, the resulting search costs are much higher than for other methods. Variants of the quantum algorithm that do not match the adiabatic limit give lower costs, on average, and slower growth than the conventional GSAT heuristic method.

arXiv:quant-ph/0206059•Physical Review A•Feb 28, 2003•95 citations

Eigenlevel statistics of the quantum adiabatic algorithm

Marko Žnidarič

We study the eigenlevel spectrum of quantum adiabatic algorithm for 3-satisfiability problem, focusing on single-solution instances. The properties of the ground state and the associated gap, crucial for determining the running time of the algorithm, are found to be far from the predictions of random matrix theory. The distribution of gaps between the ground and the first excited state shows an abundance of small gaps. Eigenstates from the central part of the spectrum are, on the other hand, well described by random matrix theory.

arXiv:quant-ph/0512018•Physical Review A•Nov 30, 2005•2 citations

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

The quantum adiabatic optimization algorithm and local minima

Ben W. Reichardt

The quantum adiabatic optimization algorithm uses the adiabatic theorem from quantum physics to minimize a function by interpolation between two Hamiltonians. The quantum wave function can sometimes tunnel through significant obstacles. However it can also sometimes get stuck in local minima, even for fairly simple problems. An initial Hamiltonian which insufficiently mixes computational basis states is analogous to a poorly mixing Markov transition rule. We study a physical system -- the Ising quantum chain with alternating sector interaction defects, but constant transverse field -- which is equivalent to applying the quantum adiabatic algorithm to a particular SAT problem. We prove that for a constant range of values for the transverse field, the spectral gap is exponentially small in the sector length. Indeed, we prove that there are exponentially many eigenvalues all exponentially close to the ground state energy. Applying the adiabatic theorem therefore takes exponential time, even for this simple problem.

ACM Symposium on Theory of Computing (STOC)•Jun 13, 2004•110 citations
We study the Hamiltonian associated with the quantum adiabatic algorithm with a random cost function. Because the cost function lacks structure we can prove results about the ground state. We find the ground state energy as the number of bits goes to infinity, show that the minimum gap goes to zero exponentially quickly, and we see a localization transition. We prove that there are no levels approaching the ground state near the end of the evolution. We do not know which features of this model are shared by a quantum adiabatic algorithm applied to random instances of satisfiability since despite being random they do have bit structure.
We study the Hamiltonian associated with the quantum adiabatic algorithm with a random cost function. Because the cost function lacks structure we can prove results about the ground state. We find the ground state energy as the number of bits goes to infinity, show that the minimum gap goes to zero exponentially quickly, and we see a localization transition. We prove that there are no levels approaching the ground state near the end of the evolution. We do not know which features of this model are shared by a quantum adiabatic algorithm applied to random instances of satisfiability since despite being random they do have bit structure.
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.
The discrete formulation of adiabatic quantum computing is compared with other search methods, classical and quantum, for random satisfiability (SAT) problems. With the number of steps growing only as the cube of the number of variables, the adiabatic method gives solution probabilities close to 1 for problem sizes feasible to evaluate via simulation on current computers. However, for these sizes the minimum energy gaps of most instances are fairly large, so the good performance scaling seen for small problems may not reflect asymptotic behavior where costs are dominated by tiny gaps. Moreover, the resulting search costs are much higher than for other methods. Variants of the quantum algorithm that do not match the adiabatic limit give lower costs, on average, and slower growth than the conventional GSAT heuristic method.
We study the eigenlevel spectrum of quantum adiabatic algorithm for 3-satisfiability problem, focusing on single-solution instances. The properties of the ground state and the associated gap, crucial for determining the running time of the algorithm, are found to be far from the predictions of random matrix theory. The distribution of gaps between the ground and the first excited state shows an abundance of small gaps. Eigenstates from the central part of the spectrum are, on the other hand, well described by random matrix theory.
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.
The quantum adiabatic optimization algorithm uses the adiabatic theorem from quantum physics to minimize a function by interpolation between two Hamiltonians. The quantum wave function can sometimes tunnel through significant obstacles. However it can also sometimes get stuck in local minima, even for fairly simple problems. An initial Hamiltonian which insufficiently mixes computational basis states is analogous to a poorly mixing Markov transition rule. We study a physical system -- the Ising quantum chain with alternating sector interaction defects, but constant transverse field -- which is equivalent to applying the quantum adiabatic algorithm to a particular SAT problem. We prove that for a constant range of values for the transverse field, the spectral gap is exponentially small in the sector length. Indeed, we prove that there are exponentially many eigenvalues all exponentially close to the ground state energy. Applying the adiabatic theorem therefore takes exponential time, even for this simple problem.