Adiabatic Quantum Computing Spectral Gap

Short answer: In adiabatic quantum computing, a system starts in the ground state of a simple Hamiltonian and evolves slowly to one that encodes the answer. How slowly depends on the minimum spectral gap, the difference between the two lowest energy levels along the path. A 2004 paper showed the model is polynomially equivalent to standard quantum computation, a 2020 paper tightened the gap bound for that construction, and a 2023 paper gives a framework for runtime lower bounds that avoids computing the gap directly.

The role of the gap

A 2023 Physical Review Research paper describes how an adiabatic quantum algorithm runs: prepare the ground state of an initial Hamiltonian, then let the system evolve. The adiabatic theorem says the final state stays close to the instantaneous ground state of the problem Hamiltonian provided the evolution is slow enough. A typical sufficient condition is that the runtime scales polynomially with the inverse of the minimum spectral gap of the full Hamiltonian. The authors point out that analytical calculation of the gap is possible only for relatively simple Hamiltonians, and numerical calculation is limited to small systems.

A 2004 paper states the same idea for a straight-line path between an initial and a final Hamiltonian: the running time is set by the minimal gap over the path, and the computation is polynomial time if that gap is at least inverse polynomial. It defines the spectral gap as the difference between the lowest and second lowest eigenvalue.

Equivalence with the circuit model

The 2004 paper describes an efficient adiabatic simulation of any quantum algorithm and concludes that the adiabatic model is polynomially equivalent to the standard model of quantum computation, using 3-local Hamiltonians. It also says the result translates open questions about quantum algorithms into questions about spectral gaps of sparse matrices, making them accessible to readers from mathematical physics, expander theory and rapidly mixing Markov chains.

A 2020 Physical Review A paper revisits that mapping, which sends a circuit to an adiabatic evolution and then needs a proof that the minimum gap is at least inverse polynomial in the number of steps L. It gives two simplified proofs, one with an eigenstate ansatz and one using Weyl's theorem, both yielding the same bound for large L, which the authors say improves on previous bounds. They suggest the methods may help bound gaps for other Hamiltonians.

Lower bounds without the gap

The 2023 paper introduces a framework for lower bounds on the runtime of a broad class of adiabatic algorithms. The central formula computes the variance of the final Hamiltonian with respect to the initial state. The authors examine adiabatic versions of keystone circuit-based algorithms and then apply it to algorithms with undetermined speedup, obtaining analytic lower bounds for finding k-cliques in random graphs. For a particular class of Hamiltonians, they prove their framework is equivalent to the conventional spectral gap analysis.

What this does not tell you

These are theoretical results about runtime scaling. They do not say that an adiabatic device can beat a classical computer on a given problem, and lower bounds say how long an algorithm must run, not whether it is useful.

FAQ

What is the spectral gap?

The difference between the two lowest energy eigenvalues of the Hamiltonian.

Why does it matter?

The runtime of an adiabatic algorithm typically scales polynomially with the inverse of the minimum gap.

Is adiabatic computing as powerful as the circuit model?

A 2004 paper showed the two are polynomially equivalent.

Is the gap easy to compute?

Not usually. A 2023 paper says analytic calculation works only for simple Hamiltonians.

Is there a way around it?

The 2023 paper gives a variance-based framework for runtime lower bounds.