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:1108.3303 · Physical Review A

Algorithmic approach to adiabatic quantum optimization

Neil G. Dickson, M. H. S. Amin

Published Mar 5, 2012• 40 citations
arXivHTMLPDF

Abstract

It is believed that the presence of anticrossings with exponentially small gaps between the lowest two energy levels of the system Hamiltonian can render adiabatic quantum optimization inefficient. Here, we present a simple adiabatic quantum algorithm designed to eliminate exponentially small gaps caused by anticrossings between eigenstates that correspond with the local and global minima of the problem Hamiltonian. In each iteration of the algorithm, information is gathered about the local minima that are reached after passing the anticrossing nonadiabatically. This information is then used to penalize pathways to the corresponding local minima by adjusting the initial Hamiltonian. This is repeated for multiple clusters of local minima as needed. We generate 64-qubit random instances of the maximum independent set problem, skewed to be extremely hard, with between ${10}^{5}$ and ${10}^{6}$ highly degenerate local minima. Using quantum Monte Carlo simulations, it is found that the algorithm can trivially solve all of the instances in $\ensuremath{\sim}$10 iterations.

DOI
10.1103/physreva.85.032303

Related papers

Elimination of perturbative crossings in adiabatic quantum optimization

Neil G. Dickson

It was recently shown that, for solving NP-complete problems, adiabatic paths always exist without finite-order perturbative crossings between local and global minima, which could lead to anticrossings with exponentially small energy gaps if present. However, it was not shown whether such a path could be found easily. Here, we give a simple construction that deterministically eliminates all such anticrossings in polynomial time, space and energy, for any Ising models with polynomial final gap. Thus, in order for adiabatic quantum optimization to require exponential time to solve any NP-complete problem, some quality other than this type of anticrossing must be unavoidable and necessitate exponentially long runtimes.

arXiv:1104.2349•New Journal of Physics•Jul 11, 2011•20 citations

Does Adiabatic Quantum Optimization Fail for NP-hard problems?

Neil G. Dickson, M. H. S. Amin

It has been recently argued that adiabatic quantum optimization would fail in solving NP-complete problems because of the occurrence of exponentially small gaps due to crossing of local minima of the final Hamiltonian with its global minimum near the end of the adiabatic evolution. Using perturbation expansion, we analytically show that for the NP-hard problem of maximum independent set there always exist adiabatic paths along which no such crossings occur. Therefore, in order to prove that adiabatic quantum optimization fails for any NP-complete problem, one must prove that it is impossible to find any such path in polynomial time.

•Oct 4, 2010•0 citations

Does Adiabatic Quantum Optimization Fail for NP-Complete Problems?

Neil G. Dickson, M. H. S. Amin

It has been recently argued that adiabatic quantum optimization would fail in solving NP-complete problems because of the occurrence of exponentially small gaps due to crossing of local minima of the final Hamiltonian with its global minimum near the end of the adiabatic evolution. Using perturbation expansion, we analytically show that for the NP-hard problem known as maximum independent set, there always exist adiabatic paths along which no such crossings occur. Therefore, in order to prove that adiabatic quantum optimization fails for any NP-complete problem, one must prove that it is impossible to find any such path in polynomial time.

arXiv:1010.0669•Physical Review Letters•Feb 2, 2011•64 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

Effect of Local Minima on Adiabatic Quantum Optimization

M. H. S. Amin

We present a perturbative method to estimate the spectral gap for adiabatic quantum optimization, based on the structure of the energy levels in the problem Hamiltonian. We show that, for problems that have an exponentially large number of local minima close to the global minimum, the gap becomes exponentially small making the computation time exponentially long. The quantum advantage of adiabatic quantum computation may then be accessed only via the local adiabatic evolution, which requires phase coherence throughout the evolution and knowledge of the spectrum. Such problems, therefore, are not suitable for adiabatic quantum computation.

arXiv:0709.0528•Physical Review Letters•Apr 4, 2008•36 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
It is believed that the presence of anticrossings with exponentially small gaps between the lowest two energy levels of the system Hamiltonian can render adiabatic quantum optimization inefficient. Here, we present a simple adiabatic quantum algorithm designed to eliminate exponentially small gaps caused by anticrossings between eigenstates that correspond with the local and global minima of the problem Hamiltonian. In each iteration of the algorithm, information is gathered about the local minima that are reached after passing the anticrossing nonadiabatically. This information is then used to penalize pathways to the corresponding local minima by adjusting the initial Hamiltonian. This is repeated for multiple clusters of local minima as needed. We generate 64-qubit random instances of the maximum independent set problem, skewed to be extremely hard, with between 105{10}^{5}105 and 106{10}^{6}106 highly degenerate local minima. Using quantum Monte Carlo simulations, it is found that the algorithm can trivially solve all of the instances in \ensuremath∼\ensuremath{\sim}\ensuremath∼10 iterations.
It was recently shown that, for solving NP-complete problems, adiabatic paths always exist without finite-order perturbative crossings between local and global minima, which could lead to anticrossings with exponentially small energy gaps if present. However, it was not shown whether such a path could be found easily. Here, we give a simple construction that deterministically eliminates all such anticrossings in polynomial time, space and energy, for any Ising models with polynomial final gap. Thus, in order for adiabatic quantum optimization to require exponential time to solve any NP-complete problem, some quality other than this type of anticrossing must be unavoidable and necessitate exponentially long runtimes.
It has been recently argued that adiabatic quantum optimization would fail in solving NP-complete problems because of the occurrence of exponentially small gaps due to crossing of local minima of the final Hamiltonian with its global minimum near the end of the adiabatic evolution. Using perturbation expansion, we analytically show that for the NP-hard problem of maximum independent set there always exist adiabatic paths along which no such crossings occur. Therefore, in order to prove that adiabatic quantum optimization fails for any NP-complete problem, one must prove that it is impossible to find any such path in polynomial time.
It has been recently argued that adiabatic quantum optimization would fail in solving NP-complete problems because of the occurrence of exponentially small gaps due to crossing of local minima of the final Hamiltonian with its global minimum near the end of the adiabatic evolution. Using perturbation expansion, we analytically show that for the NP-hard problem known as maximum independent set, there always exist adiabatic paths along which no such crossings occur. Therefore, in order to prove that adiabatic quantum optimization fails for any NP-complete problem, one must prove that it is impossible to find any such path in polynomial time.
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.
We present a perturbative method to estimate the spectral gap for adiabatic quantum optimization, based on the structure of the energy levels in the problem Hamiltonian. We show that, for problems that have an exponentially large number of local minima close to the global minimum, the gap becomes exponentially small making the computation time exponentially long. The quantum advantage of adiabatic quantum computation may then be accessed only via the local adiabatic evolution, which requires phase coherence throughout the evolution and knowledge of the spectrum. Such problems, therefore, are not suitable for adiabatic quantum computation.
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.