Adiabatic Quantum Optimization Reaches Grover-Like Speedup, With a Fundamental Catch 

Adiabatic Quantum Computation (AQC) is a physically motivated model of quantum computing where a system evolves slowly under a changing energy landscape. The system begins in the easily prepared ground state of a simple Hamiltonian and, over time, transforms into a complex problem Hamiltonian whose ground state encodes the solution to a computational task. If the evolution is slow enough, the quantum system remains in its ground state throughout, and the final measurement reveals the answer.

This continuous-time approach offers a natural way to solve optimization problems, especially NP-complete ones like SAT or MaxCut, by encoding them into classical Ising spin systems. Although it is unclear how much quantum speed-up can be obtained for optimization problems via the adiabatic approach, it is natural to expect that at least a provable quadratic speed-up over brute force classical search would be possible. Indeed, in the circuit model of quantum computation, we know that quantum computers can generically speed up brute-force search by a square root factor, thanks to Grover’s algorithm and its generalization, quantum amplitude amplification. For example, if a classical computer takes O(2^n) time to find the solution of some hard problem, a quantum one can do it in O(2^{n/2} poly(n)) time using amplitude amplification.

The main question we address in our work is thus the following: Can the adiabatic model provide this same generic quantum advantage? Since AQC is a universal model, any circuit-based algorithm can, in principle, be implemented adiabatically, it’s tempting to believe the answer is yes. Moreover, there is an adiabatic version of Grover’s algorithm that achieves the same running time as the circuit model version. In the more complex scenario of finding the minimum of a classical cost function, it has been known for over a decade that any adiabatic unstructured search algorithm would require at least 2^{n/2} time. However, no purely adiabatic algorithm was known to achieve this bound until now.

In this work, we show that unstructured adiabatic quantum optimization (AQO) can indeed match this lower bound, providing a generic quadratic quantum speedup over classical brute-force search for a wide class of classical Hamiltonians, including those encoding NP-hard or NP-complete problems. The key challenge lies in analyzing the spectral gap (the energy difference between the two lowest eigenstates) during the adiabatic evolution, which controls how slowly the system must evolve. In our case, the smallest gap appears at a critical point in the evolution called an avoided crossing. Identifying this point accurately is crucial because it determines how to adjust the rate of evolution, a faster pace where the gap is wide, and a slower one near the minimum gap. We rigorously analyze this process, tightly bounding the spectral gap throughout the adiabatic path and constructing an optimized local schedule that ensures the algorithm finishes in  O(2^{n/2} poly(n)) time, matching Grover-like performance in a fully adiabatic setting.

However, there is a fundamental limitation. We show that determining the location of the avoided crossing requires knowing a spectral quantity that depends on the degeneracies and energy gaps of the problem Hamiltonian. Unfortunately, approximating this quantity to even modest precision is NP-hard, and computing it exactly is #P-hard, as hard as counting the number of solutions to a SAT instance. This reveals a fundamental limitation of the unstructured adiabatic optimization algorithm we analyze: although it can, in principle, provide a generic quadratic speedup, doing so requires solving a classically intractable problem up front. By contrast, this bottleneck is absent in the gate-based model, using tools like amplitude amplification and quantum phase estimation without needing detailed spectral knowledge.

In summary, our work answers a long-standing open question in quantum computing. We show that generic quadratic speedups via adiabatic evolution are possible, but they come with significant caveats. This interplay between the power of AQC and the hardness of spectral analysis highlights both its promise and its limitations and opens exciting new avenues for overcoming these obstacles in future quantum algorithm design. 

Publication: A. Braida, S. Chakraborty, A. Chaudhuri, J. Cunningham, R. Menavlikar, L. Novo, and J. Roland, Unstructured Adiabatic Quantum Optimization: Optimality with Limitations,  Quantum 9, 1790 (2025). arXiv.