© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

arXiv:2411.05736 · Quantum

Unstructured Adiabatic Quantum Optimization: Optimality with Limitations

Arthur Braida, Shantanav Chakraborty, Alapan Chaudhuri, Joseph Cunningham, Rutvij Menavlikar, Leonardo Novo, Jérémie Roland

Published Jul 11, 2025• 2 citations

Abstract

In the circuit model of quantum computing, amplitude amplification techniques can be used to find solutions to NP-hard problems defined on n -bits in time poly(n)2n/2 . In this work, we investigate whether such general statements can be made for adiabatic quantum optimization, as provable results regarding its performance are mostly unknown. Although a lower bound of Ω(2n/2) has existed in such a setting for over a decade, a purely adiabatic algorithm with this running time has been absent. We show that adiabatic quantum optimization using an unstructured search approach results in a running time that matches this lower bound (up to a polylogarithmic factor) for a broad class of classical local spin Hamiltonians. For this, it is necessary to bound the spectral gap throughout the adiabatic evolution and compute beforehand the position of the avoided crossing with sufficient precision so as to adapt the adiabatic schedule accordingly. However, we show that the position of the avoided crossing is approximately given by a quantity that depends on the degeneracies and inverse gaps of the problem Hamiltonian and is NP-hard to compute even within a low additive precision. Furthermore, computing it exactly (or nearly exactly) is #P-hard. Our work indicates a possible limitation of adiabatic quantum optimization algorithms, leaving open the question of whether provable Grover-like speed-ups can be obtained for any optimization problem using this approach.

DOI: 10.22331/q-2025-07-11-1790

Related papers

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

On the efficiency of Hamiltonian–based quantum computation for low–rank matrices

Zhenwei Cao, Alexander Elgart

We present an extension of Adiabatic Quantum Computing (AQC) algorithm for the unstructured search to the case when the number of marked items is unknown. The algorithm maintains the optimal Grover speedup and includes a small counting subroutine. Our other results include a lower bound on the amount of time needed to perform a general Hamiltonian-based quantum search, a lower bound on the evolution time needed to perform a search that is valid in the presence of control error and a generic upper bound on the minimum eigenvalue gap for evolutions. In particular, we demonstrate that quantum speedup for the unstructured search using AQC type algorithms may only be achieved under very rigid control precision requirements.

•Jan 1, 2012•6 citations

On the efficiency of Hamiltonian-based quantum computation for low-rank matrices

Zhenwei Cao, Alexander Elgart

We present an extension of adiabatic quantum computing (AQC) algorithm for the unstructured search to the case when the number of marked items is unknown. The algorithm maintains the optimal Grover speedup and includes a small counting subroutine. Our other results include a lower bound on the amount of time needed to perform a general Hamiltonian-based quantum search, a lower bound on the evolution time needed to perform a search that is valid in the presence of control error and a generic upper bound on the minimum eigenvalue gap for evolutions. In particular, we demonstrate that quantum speedup for the unstructured search using AQC type algorithms may only be achieved under very rigid control precision requirements.

arXiv:1004.4911•Journal of Mathematical Physics•Mar 1, 2012•6 citations

ON THE GAP OF HAMILTONIANS FOR THE ADIABATIC SIMULATION OF QUANTUM CIRCUITS

Anand Ganti, Rolando D. Somma

The time or cost of simulating a quantum circuit by adiabatic evolution is determined by the spectral gap of the Hamiltonians involved in the simulation. In "standard" constructions based on Feynman's Hamiltonian, such a gap decreases polynomially with the number of gates in the circuit, L. Because a larger gap implies a smaller cost, we study the limits of spectral gap amplification in this context. We show that, under some assumptions on the ground states and the cost of evolving with the Hamiltonians (which apply to the standard constructions), an upper bound on the gap of the order 1/L follows. In addition, if the Hamiltonians satisfy a frustration-free property, the upper bound is of the order 1/L2. Our proofs use recent results on adiabatic state transformations, spectral gap amplification, and the simulation of continuous-time quantum query algorithms. They also consider a reduction from the unstructured search problem, whose lower bound in the oracle cost translates into the upper bounds in the gaps. The impact of our results is that improving the gap beyond that of standard constructions (i.e. 1/L2), if possible, is challenging.

arXiv:1307.4993•International Journal of Quantum Information•Oct 1, 2013•5 citations

Adiabatic quantum unstructured search in parallel

Sean A. Adamson, Petros Wallden

We present an optimized adiabatic quantum schedule for unstructured search building on the original approach of Roland and Cerf [Phys. Rev. A 65, 042308 (2002)]. Our schedule adiabatically varies the Hamiltonian even more rapidly at the endpoints of its evolution, preserving Grover's well-known quadratic quantum speedup. In the errorless adiabatic limit, the probability of successfully obtaining the marked state from a measurement increases directly proportional to time, suggesting efficient parallelization. Numerical simulations of an appropriate reduced two-dimensional Schrödinger system confirm adiabaticity while demonstrating superior performance in terms of probability compared to existing adiabatic algorithms and Grover's algorithm, benefiting applications with possible premature termination. We introduce a protocol that ensures a marked-state probability at least $p$ in time of order $\sqrt{N}(1+p/\varepsilon)$, and analyze its implications for realistic bounded-resource scenarios. Our findings suggest that quantum advantage may still be achievable under constrained coherence times (where other algorithms fail), provided the hardware allows for them to be sufficiently long.

arXiv:2502.08594•Feb 12, 2025•0 citations

In the circuit model of quantum computing, amplitude amplification techniques can be used to find solutions to NP-hard problems defined on n -bits in time poly(n)2n/2 . In this work, we investigate whether such general statements can be made for adiabatic quantum optimization, as provable results regarding its performance are mostly unknown. Although a lower bound of Ω(2n/2) has existed in such a setting for over a decade, a purely adiabatic algorithm with this running time has been absent. We show that adiabatic quantum optimization using an unstructured search approach results in a running time that matches this lower bound (up to a polylogarithmic factor) for a broad class of classical local spin Hamiltonians. For this, it is necessary to bound the spectral gap throughout the adiabatic evolution and compute beforehand the position of the avoided crossing with sufficient precision so as to adapt the adiabatic schedule accordingly. However, we show that the position of the avoided crossing is approximately given by a quantity that depends on the degeneracies and inverse gaps of the problem Hamiltonian and is NP-hard to compute even within a low additive precision. Furthermore, computing it exactly (or nearly exactly) is #P-hard. Our work indicates a possible limitation of adiabatic quantum optimization algorithms, leaving open the question of whether provable Grover-like speed-ups can be obtained for any optimization problem using this approach.

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.

We present an extension of Adiabatic Quantum Computing (AQC) algorithm for the unstructured search to the case when the number of marked items is unknown. The algorithm maintains the optimal Grover speedup and includes a small counting subroutine. Our other results include a lower bound on the amount of time needed to perform a general Hamiltonian-based quantum search, a lower bound on the evolution time needed to perform a search that is valid in the presence of control error and a generic upper bound on the minimum eigenvalue gap for evolutions. In particular, we demonstrate that quantum speedup for the unstructured search using AQC type algorithms may only be achieved under very rigid control precision requirements.

We present an extension of adiabatic quantum computing (AQC) algorithm for the unstructured search to the case when the number of marked items is unknown. The algorithm maintains the optimal Grover speedup and includes a small counting subroutine. Our other results include a lower bound on the amount of time needed to perform a general Hamiltonian-based quantum search, a lower bound on the evolution time needed to perform a search that is valid in the presence of control error and a generic upper bound on the minimum eigenvalue gap for evolutions. In particular, we demonstrate that quantum speedup for the unstructured search using AQC type algorithms may only be achieved under very rigid control precision requirements.

The time or cost of simulating a quantum circuit by adiabatic evolution is determined by the spectral gap of the Hamiltonians involved in the simulation. In "standard" constructions based on Feynman's Hamiltonian, such a gap decreases polynomially with the number of gates in the circuit, L. Because a larger gap implies a smaller cost, we study the limits of spectral gap amplification in this context. We show that, under some assumptions on the ground states and the cost of evolving with the Hamiltonians (which apply to the standard constructions), an upper bound on the gap of the order 1/L follows. In addition, if the Hamiltonians satisfy a frustration-free property, the upper bound is of the order 1/L2. Our proofs use recent results on adiabatic state transformations, spectral gap amplification, and the simulation of continuous-time quantum query algorithms. They also consider a reduction from the unstructured search problem, whose lower bound in the oracle cost translates into the upper bounds in the gaps. The impact of our results is that improving the gap beyond that of standard constructions (i.e. 1/L2), if possible, is challenging.

We present an optimized adiabatic quantum schedule for unstructured search building on the original approach of Roland and Cerf [Phys. Rev. A 65, 042308 (2002)]. Our schedule adiabatically varies the Hamiltonian even more rapidly at the endpoints of its evolution, preserving Grover's well-known quadratic quantum speedup. In the errorless adiabatic limit, the probability of successfully obtaining the marked state from a measurement increases directly proportional to time, suggesting efficient parallelization. Numerical simulations of an appropriate reduced two-dimensional Schrödinger system confirm adiabaticity while demonstrating superior performance in terms of probability compared to existing adiabatic algorithms and Grover's algorithm, benefiting applications with possible premature termination. We introduce a protocol that ensures a marked-state probability at least

p

in time of order

\sqrt{N}(1+p/\varepsilon)

, and analyze its implications for realistic bounded-resource scenarios. Our findings suggest that quantum advantage may still be achievable under constrained coherence times (where other algorithms fail), provided the hardware allows for them to be sufficiently long.