Introduction

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."

Anneal an Ising Model

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">A ring of <b>8 spins</b>, each up (+1) or down (−1). Each link has a coupling Jᵢ; the energy is E = −Σ Jᵢ·sᵢ·sᵢ₊₁. The best answer is the spin pattern with the <b>lowest energy</b> — its ground state. Press <b>Anneal</b> to cool the system, or <b>Brute force</b> to check all 2⁸ patterns for the true minimum.</p>
<div id="ring" class="ring"></div>
<div class="meters">
  <div>Energy: <b id="energy">0</b></div>
  <div>Temperature: <b id="temp">0</b></div>
</div>
<div class="status" id="status">Press Anneal to begin.</div>
<div class="btns">
  <button id="anneal" type="button">Anneal</button>
  <button id="brute" type="button">Brute force</button>
  <button id="reset" type="button" class="ghost">Randomize</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Quantum/simulated annealing on a 1D Ising ring of N spins s_i in {+1,-1}.
// Energy E = -sum_i J_i * s_i * s_{i+1}  (indices mod N).
// Annealing lowers a "temperature" T on a schedule; a flip that raises energy is accepted with probability exp(-dE/T) (Metropolis). Hot -> escapes ridges; cold -> settles into a valley. Brute force checks all 2^N patterns to verify.
const N = 8;
// Fixed positive couplings (a few stronger links) so the ground state is a single deep, well-defined valley that annealing can reliably reach.
const J = [2, 1, 1, 2, 1, 1, 2, 1];
let spins = [];

function energy(s){ let e = 0; for(let i=0;i<N;i++) e -= J[i]*s[i]*s[(i+1)%N]; return e; }
function randomize(){ spins = Array.from({length:N}, ()=> Math.random()<.5?1:-1); }

function render(){
  const box = document.getElementById('ring'); box.innerHTML='';
  const R = 110, cx = 130, cy = 130;
  for(let i=0;i<N;i++){
    const ang = (i/N)*2*Math.PI - Math.PI/2;
    const d = document.createElement('div');
    d.className = 'spin ' + (spins[i]===1?'up':'down');
    d.style.left = (cx + R*Math.cos(ang)) + 'px';
    d.style.top  = (cy + R*Math.sin(ang)) + 'px';
    d.textContent = spins[i]===1?'↑':'↓';
    box.appendChild(d);
  }
  document.getElementById('energy').textContent = energy(spins);
}
function setStatus(t,cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+cls; }
function setTemp(t){ document.getElementById('temp').textContent = t.toFixed(2); }

// Exhaustive search over all 2^N spin patterns: the ground-state energy.
function bruteMin(){
  let best = Infinity;
  for(let mask=0; mask<(1<<N); mask++){
    const s = []; for(let i=0;i<N;i++) s.push((mask>>i&1)?1:-1);
    const e = energy(s); if(e<best) best=e;
  }
  return best;
}

function setBusy(b){ ['anneal','brute','reset'].forEach(id=>document.getElementById(id).disabled=b); }

function anneal(){
  setBusy(true); setStatus('Cooling…','');
  let T = 4.0; const cool = 0.92; // geometric schedule
  const tick = ()=>{
    // sweep: attempt to flip each spin once at the current temperature
    for(let i=0;i<N;i++){
      const before = energy(spins);
      spins[i] *= -1;
      const dE = energy(spins) - before;
      if(dE>0 && Math.random() >= Math.exp(-dE/T)) spins[i] *= -1; // reject
    }
    render(); setTemp(T);
    T *= cool;
    if(T > 0.02){ setTimeout(tick, 90); }
    else {
      const e = energy(spins), gmin = bruteMin();
      if(e===gmin) setStatus(fmt('✓ Settled into the ground state (E = %e%).', { e: e }),'ok');
      else setStatus(fmt('Froze in a local minimum: E = %e% (ground state is %gmin%). Try again.', { e: e, gmin: gmin }),'bad');
      setBusy(false);
    }
  };
  tick();
}
function brute(){
  const gmin = bruteMin();
  setStatus(fmt('Brute force checked all %v% patterns — true minimum energy is %gmin%.', { v: 1<<N, gmin: gmin }),'ok');
  console.log('Ground-state energy:', gmin);
}

document.getElementById('anneal').addEventListener('click', anneal);
document.getElementById('brute').addEventListener('click', brute);
document.getElementById('reset').addEventListener('click', ()=>{ randomize(); render(); setTemp(0); setStatus('Randomized. Press Anneal.',''); });
randomize(); render(); setTemp(0);
Result
Console

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 2n2^{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.

The Real Complexity

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/gap2gap^{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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/quantum-annealing/Content licensed under CC BY-NC 4.0.