The Minimum Gap

The single number that determines whether an adiabatic algorithm is fast or hopeless is the minimum spectral gap along the schedule. This lesson makes the relationship between gap and runtime concrete and computes the gap for the single-qubit model.

The gap controls the runtime

Recall the adiabatic condition: the runtime must satisfy

T \;\gg\; \frac{\max_{s}\,\|\partial_s \tilde{H}(s)\|}{\Delta_{\min}^2}, \qquad \Delta_{\min} = \min_{s \in [0,1]} \bigl(E_1(s) - E_0(s)\bigr).

The numerator depends only mildly on the problem; the denominator is the bottleneck. Because the gap enters squared, halving the minimum gap quadruples the required runtime. The whole game of designing an adiabatic algorithm is keeping $\Delta_{\min}$ from becoming exponentially small.

Computing the gap for the single qubit

For $H(s) = -(1-s)X - sZ$ write $a = 1-s$ , $b = s$ . The operator $aX + bZ$ is

aX + bZ = \begin{pmatrix} b & a \\ a & -b \end{pmatrix},

with eigenvalues $\pm\sqrt{a^2 + b^2}$ . The two energies of $H(s) = -(aX + bZ)$ are therefore $E_{0,1}(s) = \mp\sqrt{a^2 + b^2}$ , giving the gap

\Delta(s) = 2\sqrt{(1-s)^2 + s^2}.

Minimizing the quadratic $(1-s)^2 + s^2$ over $s$ : its derivative is $-2(1-s) + 2s = 4s - 2$ , which vanishes at $s = \tfrac12$ . There

\Delta_{\min} = 2\sqrt{\tfrac14 + \tfrac14} = 2\sqrt{\tfrac12} = \sqrt{2} \approx 1.414 .

Hard problems, small gaps

For NP-hard optimization problems encoded into $H_P$ , the minimum gap typically appears late in the schedule, near $s = 1$ , and can scale as $\Delta_{\min} \sim 2^{-c n}$ for some constant $c > 0$ . Then the runtime $T \sim 1/\Delta_{\min}^2$ grows exponentially in the number of qubits $n$ — the adiabatic counterpart of an exponential-time classical search. Locating and widening the minimum gap (through better schedules, catalysts, or reformulations) is an active research area.

Try it

Numerically find the minimum gap of the single-qubit schedule by scanning $s \in [0,1]$ and returning the smallest value of $\Delta(s) = 2\sqrt{(1-s)^2 + s^2}$ . The grader checks that your returned number equals $\sqrt{2}$ .

Run your code to see the quantum state.

A grid scan returns $\Delta_{\min} \approx 1.414 = \sqrt{2}$ , attained at $s = 0.5$ .