Quantum Mathematics Learning Guide 20: Adiabatic Quantum Evolution, Spectral Gaps and Optimisation

Adiabatic quantum computation encodes a desired answer into the low-energy structure of a final Hamiltonian and attempts to reach it by changing the Hamiltonian slowly enough that the evolving state follows the corresponding instantaneous eigenspace.

The word “slowly” is not a universal clock setting. The allowed speed depends on how rapidly the Hamiltonian changes, how close the relevant energy levels come, and which adiabatic theorem and error criterion are being used. Spectral gaps are therefore central to both the mathematics and the computational cost.

This guide develops that structure from a two-level model to optimisation Hamiltonians. It explains what an avoided crossing is, why a small gap is dangerous, how a local schedule can spend more time where the gap is narrow, and why an adiabatic algorithm is not guaranteed to solve an arbitrary optimisation problem efficiently.

Easy initial ground state → interpolating Hamiltonian → spectral gap → controlled schedule → final low-energy state → measurement.

1. Define a path of Hamiltonians

Let s run from 0 to 1 and define a family H(s). A common interpolation is

H(s)=(1-s)H_0+sH_1.

H₀ is chosen so that an initial ground state is easy to prepare. H₁ is chosen so that its ground state, or ground-space structure, encodes the desired answer.

The physical time schedule specifies s=s(t), with s(0)=0 and s(T)=1. The evolving state obeys the time-dependent Schrödinger equation with Hamiltonian H(s(t)).

2. Instantaneous eigenstates

For each fixed s, solve

H(s)|E_j(s)⟩=E_j(s)|E_j(s)⟩.

These are instantaneous eigenstates. If the lowest eigenvalue E₀(s) is non-degenerate, the ground state is |E₀(s)⟩. The first excitation energy is E₁(s).

The spectral gap relevant to simple ground-state adiabatic evolution is

g(s)=E_1(s)-E_0(s).

The minimum gap along the path is g_min=min_s g(s).

3. What the adiabatic idea says

Roughly: if the system starts in the ground state and the Hamiltonian changes sufficiently slowly compared with the relevant spectral separations, then the state remains close to the evolving ground state up to phase.

Rigorous theorems make “sufficiently slowly” precise under stated smoothness and gap assumptions. The dependence can involve derivatives of H, inverse powers of the gap, total runtime and endpoint conditions. There is no single gap-only formula that should be quoted without its theorem assumptions. [1]

This matters pedagogically. Saying “runtime is one over gap squared” may be a useful heuristic in a simple two-level derivation but is not a universal adiabatic theorem.

4. Why a small gap is dangerous

When the ground and first excited energies approach one another, the corresponding eigenspaces become easier to mix under a changing Hamiltonian. To suppress transitions, the schedule generally has to slow down near that narrow gap.

A tiny minimum gap can therefore dominate the runtime. Far from the minimum gap, the same schedule may be unnecessarily slow.

This is analogous to numerical conditioning: a difficult local spectral feature can control the global resource requirement.

5. Worked two-level Hamiltonian

Consider

H(s)=-(1-s)X-sZ.

This interpolates between −X, whose ground state is |+⟩, and −Z, whose ground state is |0⟩.

Using the Pauli-vector form, the eigenvalues are

E_±(s)=±√((1-s)^2+s^2).

The gap is therefore

g(s)=2√((1-s)^2+s^2).

It is smallest at s=1/2, where g_min=√2. The gap never closes, so this interpolation avoids a true level crossing.

6. The ground state rotates on the Bloch sphere

The effective field vector is ((1−s),0,s). The ground state aligns with that direction in the appropriate sign convention. As s increases, the ground-state Bloch vector rotates from the +X direction toward +Z.

The adiabatic task is therefore geometrically simple: rotate the Hamiltonian axis slowly enough that the state tracks the moving eigenvector instead of lagging into the excited direction.

This two-level picture becomes an avoided-crossing model for much larger optimisation problems when symmetry or perturbation theory reduces the relevant dynamics to two nearly resonant states.

7. True crossing versus avoided crossing

A true level crossing occurs when two eigenvalues become exactly equal and symmetry prevents them from coupling. An avoided crossing occurs when a coupling turns the crossing into a narrow but nonzero gap.

Near an avoided crossing, the character of the ground and excited eigenstates can exchange rapidly. This is often where the schedule must be slowest.

Not every small gap arises from the same mechanism. Symmetry sectors, first-order quantum phase transitions, tunnelling barriers and local excitations can produce different gap structures.

8. Matrix element matters as well as gap

A common local adiabatic condition involves the transition matrix element

|⟨E_1(s)|dH/dt|E_0(s)⟩|

relative to powers of the gap.

If dH/dt has little ability to couple the two eigenspaces, a small gap can be less damaging than a gap-only heuristic suggests. Conversely, rapid motion in a strongly coupled direction can create transitions even when the gap is not extremely small.

A careful analysis therefore examines both spectral separation and how the Hamiltonian path moves through operator space.

9. Linear schedule versus local schedule

A linear schedule uses s=t/T. It spends equal physical time per unit s regardless of the local spectral difficulty.

A local adiabatic schedule chooses ds/dt smaller near narrow gaps and larger where the gap is generous, while satisfying a chosen local adiabatic criterion.

This can improve constant factors or even scaling in structured problems. But designing the schedule may require prior information about g(s), which can itself be difficult to obtain.

10. Optimisation through a problem Hamiltonian

Suppose a classical cost function C(z) is defined on bit strings z. Construct a diagonal Hamiltonian H_P whose computational-basis eigenvalue for |z⟩ is C(z).

The minimum-cost bit strings are then ground states of H_P. Choose an initial Hamiltonian H_B with an easy ground state, often a transverse-field Hamiltonian whose ground state is a uniform superposition.

Adiabatic optimisation interpolates from H_B to H_P. The original proposal by Farhi, Goldstone, Gutmann and Sipser framed quantum computation through this kind of continuous Hamiltonian evolution and emphasised the role of the minimum energy gap. [2]

11. Worked cost-Hamiltonian example

Let one binary variable z∈{0,1} have cost C(0)=1 and C(1)=0. The problem Hamiltonian is

H_P=|0⟩⟨0|=(I+Z)/2.

Its ground state is |1⟩ with energy zero. An initial choice H_B=−X has ground state |+⟩.

Interpolating between these Hamiltonians rotates the low-energy direction from an equal superposition toward the optimal computational-basis assignment.

This toy example is easy because there is only one qubit. Large combinatorial problems create many-body spectra with many avoided crossings and potentially very small gaps.

12. Ising encodings

Binary optimisation problems are often mapped into Ising-type Hamiltonians built from Z_i and Z_iZ_j terms. A binary variable can be represented using z=(1−s)/2 with spin s∈{+1,−1}, or the opposite convention if declared consistently.

Quadratic costs then become local fields and pairwise couplings. Higher-order constraints may require auxiliary variables or higher-body terms.

The encoding can change the energy scale, degeneracy and gap structure. Two algebraically equivalent cost functions need not produce equally convenient physical Hamiltonians.

13. Penalty weights create a modelling trade-off

Constraints are often enforced by adding penalties. If a penalty is too small, an infeasible state may remain energetically competitive. If it is excessively large, the energy scales can become badly separated and may compress the relative spectral structure important to hardware precision or scheduling.

The penalty should be large enough to enforce the logical constraint, but not treated as an arbitrary “bigger is safer” parameter.

As in numerical optimisation, modelling choices affect conditioning and computational difficulty.

14. Degenerate ground spaces

If several bit strings have the same optimal cost, the final ground space is degenerate. The correct target may then be the whole ground subspace rather than one unique vector.

Adiabatic theorems for degenerate subspaces require more careful statements. Evolution can remain inside a separated low-energy subspace while rotating within it.

For optimisation, this can be acceptable: measuring any state supported on optimal basis assignments can return a valid solution.

15. Runtime is not determined by problem size alone

Two N-variable optimisation instances can have radically different interpolation spectra. One may maintain a polynomially large gap; another may develop an exponentially small avoided crossing.

Therefore “adiabatic optimisation uses N qubits” is not a runtime analysis. The path H(s), its derivatives, its gap structure and the implementation cost of each Hamiltonian all matter.

The original adiabatic-computation proposal explicitly noted that the required time depends on the minimum gap and that this gap is difficult to estimate in general. [2]

16. Gap estimation can itself be difficult

To design a near-optimal local schedule, one would like to know g(s). But computing the lowest two eigenvalues of a large many-body Hamiltonian across many s values can be computationally hard.

Small-instance diagonalisation, perturbation theory, symmetry reduction, variational estimates and physical insight can help. Yet an unknown exponentially small gap may remain hidden until the system size becomes large.

This is an example of a meta-cost: the information needed to tune the algorithm may itself require substantial computation.

17. Diabatic transitions are not automatically useless

Leaving the instantaneous ground state is called diabatic behaviour. In a strict adiabatic algorithm, such transitions are an error.

However, some protocols deliberately exploit controlled non-adiabatic transitions or optimise finite-time schedules. The broader field of quantum annealing and analog optimisation includes behaviours outside the ideal adiabatic limit.

Consequently, experimental success at finite runtime does not prove that the device operated adiabatically throughout. The mechanism should be diagnosed rather than inferred from the final answer alone.

18. Thermal effects

Ideal adiabatic evolution is usually described as closed and coherent. Real analog devices interact with an environment. If thermal energy is comparable to a small gap, excitation into higher-energy states can occur.

Cooling, relaxation and open-system dynamics can therefore interact with the schedule. Sometimes relaxation may help return population toward low-energy states; sometimes noise destroys useful coherence or freezes an incorrect distribution.

Guide 6 on quantum channels and decoherence provides the mathematical language for this open-system layer.

19. Adiabatic computation and circuit computation

Adiabatic quantum computation is computationally powerful enough to reproduce the circuit model under suitable constructions. This does not mean that every analog interpolation is automatically efficient or fault tolerant.

The equivalence is a statement about computational models under specified encodings and resource scaling. Practical architectures still differ in control, calibration, noise and error-correction requirements.

20. Relation to variational optimisation

VQE searches a parameterised state family by repeated measurements and classical updates. Adiabatic evolution instead chooses a Hamiltonian path and lets Schrödinger dynamics transport the state along that path.

Both are variationally connected to low-energy structure, but their control variables differ. VQE optimises circuit parameters. Adiabatic computation optimises or specifies an interpolation and runtime.

Neither method guarantees an efficient solution to every hard optimisation problem.

21. Common misconception: slower is always better

In the ideal closed adiabatic theorem, increasing runtime can reduce non-adiabatic error under suitable conditions. On real hardware, longer runtime also increases exposure to decoherence and thermal processes. The total experimental error can therefore have an optimum rather than decrease forever.

22. Common misconception: a nonzero gap guarantees efficiency

A gap can be nonzero yet exponentially small in problem size. Efficiency depends on how the minimum gap and other Hamiltonian quantities scale with the instance size.

23. Common misconception: the final Hamiltonian alone determines difficulty

The interpolation path matters. Two paths with the same H₀ and H₁ can have different intermediate spectra. A poor path may introduce an avoidable small gap.

24. Worked synthesis problem

Consider again H(s)=−(1−s)X−sZ.

Step 1: Spectrum. The eigenvalues are ±r(s), with r(s)=√((1−s)^2+s^2).

Step 2: Gap. g(s)=2r(s).

Step 3: Minimum. Minimise r²=1−2s+2s². Its derivative is −2+4s, so s=1/2. Then r²=1/2 and g_min=√2.

Step 4: Interpretation. The path contains an avoided crossing but no closing gap. The ground state rotates smoothly from |+⟩ to |0⟩.

Step 5: Scheduling. A local adiabatic strategy would devote more time around s=1/2 than near the endpoints because the gap is smallest there.

25. Practice set

1. Define an interpolating Hamiltonian H(s).
2. What is the instantaneous spectral gap?
3. Why can a small minimum gap increase runtime?
4. For H(s)=−(1−s)X−sZ, where is the gap smallest?
5. What is the minimum gap in that example?
6. What is an avoided crossing?
7. Why can a local schedule improve over a linear schedule?
8. How does a classical cost function become a problem Hamiltonian?
9. Why do penalty weights require care?
10. What changes when the final ground space is degenerate?
11. Why does a nonzero gap not prove polynomial runtime?
12. Give two differences between ideal adiabatic evolution and a noisy experimental annealer.

Answers

1. A parameterised family connecting an initial and final Hamiltonian.
2. The energy separation between the relevant eigenspace and the nearest competing energy level, commonly E₁−E₀ for a nondegenerate ground state.
3. Nearby levels are easier to mix under a changing Hamiltonian.
4. At s=1/2.
5. √2 in units of the Hamiltonian coefficients used here.
6. A near encounter of eigenvalues that remain separated because coupling prevents an exact crossing.
7. It spends time preferentially where the local spectral difficulty is greatest.
8. Make computational-basis states eigenstates with eigenvalues equal to their costs.
9. Too-small penalties fail to enforce constraints; excessive penalties can create poor energy scaling and implementation difficulties.
10. The target becomes a separated low-energy subspace rather than one unique vector.
11. The gap may shrink exponentially with system size and other derivative factors also matter.
12. Real devices experience decoherence/thermalisation and finite control errors; ideal adiabatic theory assumes a specified coherent Hamiltonian path.

Sources and further study

[1] Sabine Jansen, Mary-Beth Ruskai and Ruedi Seiler, Bounds for the adiabatic approximation with applications to quantum computation. A rigorous treatment with explicit gap dependence and smoothness assumptions.

[2] Edward Farhi, Jeffrey Goldstone, Sam Gutmann and Michael Sipser, Quantum Computation by Adiabatic Evolution. The foundational optimisation-oriented adiabatic-computation proposal, explicitly linking runtime to the minimum energy gap.

[3] Dorit Aharonov and colleagues, Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation. A computational equivalence result under suitable constructions.

Batch 05 series navigation

• Guide 17: Quantum Walks, Graph Spectra and Search
• Guide 18: Block Encodings, Singular Value Transformation and Polynomial Approximation
• Guide 19: Quantum Linear Systems, HHL, Condition Numbers and Solution States
• Guide 20: Adiabatic Quantum Evolution, Spectral Gaps and Optimisation
• Return to the BTT Mathematics Learning Hub

Educational note: adiabatic-runtime claims are theorem- and model-dependent. Spectral gap, Hamiltonian smoothness, noise model, control precision and resource accounting must be stated before translating a mathematical scaling into an experimental performance claim.