Quantum Annealing

Imagine a hilly landscape in the dark, and you want the lowest valley. Walk downhill and you might get stuck in the first dip you find — a local minimum — while a far deeper valley sits just over the next ridge. An enormous number of real problems have exactly this shape: scheduling, routing, folding, portfolio choice. Encode the problem so that lower energy means a better answer, and "solve it" becomes "find the bottom."

Classical simulated annealing mimics cooling metal: start hot, jiggle randomly enough to hop over ridges, then cool slowly so you settle into a deep valley. Quantum annealing swaps the jiggling for a quantum trick — the system can tunnel through a ridge instead of climbing over it, and quantum superposition lets it feel many configurations at once.

The promise is seductive: set up the right energy function, cool slowly enough, and the laws of physics carry you to the optimum. The catch — as always on this site — is hidden in the words "slowly enough."

Below is a tiny Ising problem: a ring of spins, each either up (+1) or down (−1). Neighboring spins have a coupling that prefers them to agree or disagree, and the total energy is the sum of those preferences. The best answer is the spin pattern with the lowest energy — its ground state.

<p class="hint">{{hint}}</p>
<div id="ring" class="ring"></div>
<div class="meters">
  <div>{{label_energy}}: <b id="energy">0</b></div>
  <div>{{label_temp}}: <b id="temp">0</b></div>
</div>
<div class="status" id="status">{{status_initial}}</div>
<div class="btns">
  <button id="anneal" type="button">{{btn_anneal}}</button>
  <button id="brute" type="button">{{btn_brute}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.ring { position: relative; width: 260px; height: 260px; margin: .4rem auto; }
.spin { position: absolute; width: 40px; height: 40px; margin: -20px 0 0 -20px;
        display: flex; align-items: center; justify-content: center;
        font: 700 20px ui-monospace, monospace; border-radius: 50%;
        border: 2px solid #adb1b8; transition: all .12s; }
.spin.up { background: #457b9d; color: #fff; border-color: #2f5d77; }
.spin.down { background: #e8eef3; color: #1d3557; border-color: #cdd9e3; }
.meters { display: flex; gap: 1.4rem; justify-content: center; font-size: .95rem; margin: .3rem 0; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; text-align: center; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; justify-content: center; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .5; cursor: default; }

// Code not found

Press Anneal and watch the temperature fall on its schedule. While hot, spins flip freely and the energy bounces around; as it cools, the system stops accepting bad moves and slides into a valley. Compare the result against Brute force, which checks all $2^{n}$ configurations to find the true minimum. Cool too fast and you may freeze into a local minimum instead of the global one — exactly the failure mode that makes the schedule matter. Related ideas live in Non-convex optimization.

So is quantum annealing a free pass to the optimum? Not quite — and the reason is precise.

• The adiabatic theorem. Start the system in the easy-to-prepare ground state of a simple Hamiltonian, then slowly morph it into the Hamiltonian whose ground state encodes your answer. If you change slowly enough, the system stays in the ground state the whole way. This is the basis of adiabatic quantum computation (Farhi, Goldstone, Gutmann, Sipser, 2000), which is polynomially equivalent to the standard gate model (Aharonov et al., 2007).
• How slow is "slowly"? The required runtime scales roughly as 1/$gap^{2}$, where the spectral gap is the energy distance between the ground state and the first excited state at the worst moment of the schedule.
• The gap can collapse. For hard instances the minimum gap can shrink exponentially in the problem size, so "slow enough" becomes exponentially long. Quantum annealing does not make NP-hard problems easy.
• Status: not a proven speedup. Encoding an optimization problem as an Ising ground state is itself NP-hard in general (Barahona, 1982). Whether quantum annealing beats the best classical methods on real instances remains open and hardware-dependent — there is no general proof of advantage.

The honest picture: quantum annealing is a beautiful heuristic backed by a real theorem, but the theorem's fine print — the spectral gap — is exactly where the hardness of problems like P vs NP reappears.

The reason annealing draws so much attention is that an astonishing range of problems can be rewritten as "minimize this energy" — usually in the QUBO / Ising form that annealers eat directly:

• Logistics and routing: delivery schedules and traffic flow become spin couplings to minimize.
• Finance: portfolio selection under risk and budget constraints maps cleanly to an Ising energy.
• Machine learning: training certain models and feature selection can be cast as energy minimization.
• Chip and protein design: placement and folding are searches for low-energy configurations by their physical nature.

Commercial annealers (notably D-Wave, which has built machines with thousands of qubits) target exactly these. The recurring discipline is the modeling step: turning your problem into couplings, the same craft behind SAT reductions and other non-convex optimization work.

Quantum annealing is one of computing's most elegant ideas: write your problem as an energy landscape, prepare a simple state, and let a quantum system drift into the optimum while the adiabatic theorem keeps it in the ground state. The demo shows the intuition in miniature — cool slowly and you find the valley; cool too fast and you freeze early.

But elegance is not a shortcut. The runtime hides in the spectral gap, and for genuinely hard instances that gap can close exponentially. So quantum annealing is best understood not as a way around the limits of computation, but as a new and physical way of running into them — the same wall behind P vs NP, now made out of energy.