The Spectral Gap Problem in Quantum Annealing
Quantum annealing promises quantum advantage, courtesy of quantum tunnelling. But a single, elusive quantity, the spectral gap, determines whether it works. And in almost all interesting cases, that gap is either vanishingly small, unknowable in advance, or both.
The mirage of milliseconds
Quantum annealing is often sold as magical: encode a hard optimization problem, let the hardware run for a few milliseconds, and the solution emerges.
The real bottleneck has nothing to do with how fast qubits oscillate. What matters is how the energy spectrum behaves during the evolution. If the gap between the ground and first excited states is exponentially small, the time required to remain in the ground state grows exponentially.
Let’s see why.
Optimization problems
Quantum annealing solves optimization problems by evolving a quantum system from an easy driver Hamiltonian \(H_{D}\) to one whose ground state encodes the solution, the problem Hamiltonian \(H_{P}\). A schedule parameter \(s\in[0,1]\) interpolates between the two Hamiltonians:
\[H(s) = (1 - s) H_{D} + s H_{P}.\]At \(s=0\), the system is in the ground state of the driver Hamiltonian. When the system evolves slowly (i.e. adiabatically), it remains in the ground state and reaches the ground state of the problem Hamiltonian at \(s=1\).
To define these Hamiltonians, we shall use the Pauli operators \(X=\sigma^{1}\), \(Y=\sigma^{2}\), and \(Z=\sigma^{3}\). In quantum computing, it is customary to use \(X,Y,Z\). These operators flip the qubits and their phases as follows:
\[\begin{alignedat}{5} \text{bit flip:}\quad & X\,|0\rangle &{}={}& & & &{}& |1\rangle \\ & X\,|1\rangle &{}={}& & & &{}& |0\rangle \\[6pt] \text{bit-phase flip:}\quad & Y\,|0\rangle &{}={}& & \phantom{-} & i\, &{}& |1\rangle \\ & Y\,|1\rangle &{}={}& & - & i\, &{}& |0\rangle \\[6pt] \text{phase flip:}\quad & Z\,|0\rangle &{}={}& & & &{}& |0\rangle \\ & Z\,|1\rangle &{}={}& & - & &{}& |1\rangle \end{alignedat}\]The ground state of the driver Hamiltonian with \(n\) qubits
\[H_{D} = -\sum_{i=1}^{n}{X_{i}}\]is trivial to prepare: it is a uniform superposition of all computational basis states. The single-spin flips generated by \(H_{D}\) make it possible to explore the search space.
The problem Hamiltonian encodes the cost function:
\[H_{P} = \sum_{i}{h_{i} Z_{i}} + \sum_{i<j} J_{ij}{Z_{i} Z_{j}}.\]Its ground state corresponds to the optimal solution of the problem we wish to solve. So, where does the cost function come from?
Encoding problems: from QUBO to Ising
Many problems are formulated as quadratic unconstrained binary optimization (QUBO) problems for \(x_{i}\in \mathbb{B}=\{0,1\}\):
\[\min_{\mathbf{x}\in\mathbb{B}^{n}}{f(\mathbf{x})} = \min_{\mathbf{x}\in\mathbb{B}^{n}}{\mathbf{x}^\top Q \mathbf{x}},\]where
\[f(\mathbf{x})=\sum_{i=1}^{n}{Q_{ii}x_{i}} + \sum_{i < j}{\left(Q_{ij}+Q_{ji}\right)x_{i}x_{j}}\]thanks to \(x_{i}^{2}=x_{i}\) for binary variables. So, for a symmetric matrix \(Q\), the coupling for \(x_{i}x_{j}\) is \(2Q_{ij}\). If we map these to classical Ising spins \(s_{i}=\{-1,+1\}\) with \(s_{i} = 1 - 2x_{i}\), we obtain the Ising energy of \(E(\mathbf{s}) = \sum_{i}{h_{i} s_{i}} + \sum_{i<j}{J_{ij} s_{i} s_{j}}\) modulo constants. Here,
\[h_{i} = -\frac{1}{2}Q_{ii} - \frac{1}{4}\sum_{j\neq i}{Q_{ij}+Q_{ji}}\]and
\[J_{ij} = \frac{1}{4}\left(Q_{ij}+Q_{ji}\right)\]for \(i<j\). The constant term is
\[\begin{aligned} c &= \frac{1}{2}\sum_{i=1}^{n}{Q_{ii}}+\frac{1}{4}\sum_{i<j}{Q_{ij}+Q_{ji}} \\ &= \frac{1}{2}\mathrm{Tr}(Q)+\frac{1}{4}\sum_{i<j}{Q_{ij}+Q_{ji}}. \end{aligned}\]We obtain the corresponding quantum Hamiltonian by replacing the classical spins \(s_{i}\) with Pauli operators \(Z_{i}\). That is how we map QUBO to quantum Hamiltonians using Pauli spin operators.
An example
Let’s pick \(f(x_{1},x_{2})=x_{1}+x_{2}-2x_{1}x_{2}\), so that \(Q=\begin{pmatrix}1&-1\\-1&1\end{pmatrix}\). We can calculate all combinations and thus the optima by brute force:
| \(x_{1}\) | \(x_{2}\) | \(f(x_{1},x_{2})\) |
|---|---|---|
| \(0\) | \(0\) | \(0\) |
| \(0\) | \(1\) | \(1\) |
| \(1\) | \(0\) | \(1\) |
| \(1\) | \(1\) | \(0\) |
The minima are therefore \((x_{1},x_{2}) = (0,0)\) and \((1,1)\). When we substitute the Ising mapping \(x_{i}\mapsto\left(1-s_{i}\right)/2\), we obtain the Ising energy \(E(\mathbf{s})=\frac{1}{2}-\frac{1}{2}s_{1}s_{2}\) after a little algebra. We can also obtain these from the expressions above:
\[\begin{aligned} h_{1} &= -\frac{1}{2}Q_{11} - \frac{1}{4}\left( Q_{12}+Q_{21} \right)\\ &= - \frac{1}{2}(1) - \frac{1}{4}\left(-1 -1\right)\\ &= 0, \end{aligned}\]similarly for \(h_{2}\), and
\[\begin{aligned} J_{12} &= \vphantom{-}\frac{1}{4}\left(Q_{12}+Q_{21}\right) \\ &= \vphantom{-}\frac{1}{4}\left(-1-1 \right) \\ &= -\frac{1}{2}. \end{aligned}\]The constant evaluates to \(\frac{1}{2}\). It is irrelevant to the minimization problem; it merely shifts the overall objective function up or down. In the Ising representation, we can also compute the energies:
| \(s_{1}\) | \(s_{2}\) | \(E(\mathbf{s})\) |
|---|---|---|
| \(-1\) | \(-1\) | \(0\) |
| \(-1\) | \(+1\) | \(1\) |
| \(+1\) | \(-1\) | \(1\) |
| \(+1\) | \(+1\) | \(0\) |
Both representations encode the same set of minima, as the binary variables \(x=0\) (\(x=1\)) map to \(s=1\) (\(s=-1\)). In the quantum version the ground states are \(|00\rangle\) and \(|11\rangle\) in the \(Z\) basis.
The adiabatic theorem and the spectral gap
The adiabatic theorem dates back to Born and Fock (1928) and has since been refined and applied to quantum computing. Consider a smooth interpolation \(H(s)\) with \(s = t/\tau \in [0,1]\), and assume the system begins in the ground state \(|\psi_\tau(0)\rangle = |\psi_0(0)\rangle\). If the evolution is slow, the physical state \(|\psi_\tau(s)\rangle\) tracks the ideal adiabatic state \(|\psi_{\text{ad}}(s)\rangle\). The parameter \(\tau\) is the total evolution time, which in the adiabatic limit goes to infinity.
The adiabatic theorem bounds the error amplitude
\[A(s) = \big\lVert|\psi_{\text{ad}}(s)\rangle - |\psi_{\tau}(s)\rangle\big\rVert = \mathcal{O}\left( \frac{\lVert\partial_s H\rVert}{g_{\min}^2\tau}\right),\]where the spectral gap is \(g(s)=E_1(s)-E_0(s)\) and \(g_{\min} = \min_{s\in[0,1]}{g(s)}\).
Terms involving higher-order derivatives of the Hamiltonian and higher powers of the spectral gap are omitted here. They leave the main dependence intact, which echoes Heisenberg’s idea that fast changes in the Hamiltonian induce transitions, whereas slowing the evolution suppresses them. The error amplitude therefore vanishes as \(1/\tau\) provided the gap remains finite. For smooth schedules, the adiabatic runtime scales as \(\tau \propto 1/g_{\min}^{2}\). As the spectral gap narrows, the time required grows quadratically.
Another example
Let’s take a single qubit: \(H(s) = -(1-s)X + s q Z\). In the computational basis \(\lbrace |0\rangle, |1\rangle\rbrace\), we have
\[X = \begin{pmatrix} 0 & 1 \\ 1 & 0\end{pmatrix}\quad\text{and}\quad Z = \begin{pmatrix} 1 & 0 \\ 0 & -1\end{pmatrix},\]so that we can write the Hamiltonian as
\[H(s)=\begin{pmatrix} s q & -(1 - s)\\ -(1 - s)& -s q\end{pmatrix}.\]Its eigenvalues are \(\pm \lambda(s)\) with \(\lambda(s) = \sqrt{(1-s)^2 + (sq)^2}\). From that we can compute that the spectral gap is \(g(s) = 2\lambda(s) = 2\sqrt{(1 - s)^2 + (s q)^2}\). Its minimum is \(g_{\min} = \frac{2|q|}{\sqrt{1 + q^2}}\). For extremely simple systems, we can calculate the spectral gap. For anything interesting, we cannot.
Quantum complexity
For a real quantum annealer, the spectral gap is always the difference between two eigenvalues of a finite Hermitian matrix. Nothing prevents anyone from diagonalizing that matrix with exponential brute force. The real question is whether there exists an algorithm that can estimate or bound the spectral gap using only polynomial resources. That leads us straight to the doorstep of quantum complexity.
BQP is the class of decision problems that a uniform family of quantum circuits can solve in polynomial time with a bounded error.
Think of it as the class of problems thought to be efficiently solvable by a quantum computer, such as Shor's and Grover's algorithms.
QMA is the analogue of NP: we can generate a proof with a polynomial-size quantum state that a quantum verifier accepts with high probability in polynomial time. A problem is said to be QMA-hard if any problem in QMA can be reduced to it in polynomial time. QMA-complete problems are both QMA-hard and in QMA, which is not necessarily the case for QMA-hard problems. The canonical example of a QMA-complete problem is the k-local Hamiltonian problem with k ≥ 2, in which the Hamiltonian is made of terms that each act on only k qubits. It asks whether the ground-state energy is above a certain threshold or below another in polynomial time. It is believed that QMA-complete problems are intractable even for quantum computers.
Why are QMA-hard problems not automatically in QMA and therefore QMA-complete? QMA-hard problems are at least as hard as QMA's hardest tasks, but unless they also admit efficiently checkable quantum proofs, they do not belong to QMA. Consider a mountain higher than anything anyone has climbed before. If there is no quick, reliable way to confirm whether someone actually reached the summit, then the mountain is not in QMA. Difficulty and verifiability are independent of each other.
Estimating the spectral gap for local Hamiltonians is at least QMA-hard. Nevertheless, it is not undecidable. Undecidability would imply that no algorithm can always halt with a correct yes/no answer. Undecidability is only reserved for the thermodynamic limit of infinite systems with translation invariance. Real quantum annealers never enter that regime as the number of qubits is finite, and therefore the Hilbert space remains finite-dimensional, too. Likewise, the matrix is a finite matrix that can be diagonalized; it may be prohibitively hard to do so, but it is ultimately a decidable problem.
Quantum annealers in practice
Adiabatic quantum computing is a theoretical model that assumes an isolated, coherent system evolving slowly enough to follow the ground state. Quantum annealing is the noisy, open-system relative that uses the same idea but operates outside of the conditions required for the adiabatic theorem to hold. That is why, in practice, no one computes the spectral gap.
The idea is to treat the quantum annealer as a noisy optimization heuristic and infer “good enough” runtimes from many runs. You simply pick a set of anneal times (\(\tau\)), run thousands of shots each, and plot the probability of seeing the best energy found so far. What we actually see in experiments is a rise, then a plateau, sometimes even a downturn as thermalization and control noise dominate.
Current superconducting quantum annealers operate with single-qubit coherence times on the order of tens of nanoseconds, whereas typical optimization runs use anneal times up to a few hundred microseconds. Multi-qubit tunnelling and environment-assisted relaxation can aid a problem. No experimental evidence suggests contemporary coherence times are sufficient to support adiabatic conditions for real optimization problems. If a contemporary quantum annealer happens to find the optimum, it is not because the prerequisites of the adiabatic theorem were satisfied, but rather because the problem had a favourable structure, beneficial thermalization, and the sampling was fortunate. In much simpler words: luck.