Introduction

Optimization is everywhere: route a fleet of trucks, schedule a factory, cut a network into two balanced halves. Most hard versions belong to NP-hard — no known classical algorithm solves them fast for large inputs. Classical computers must search exponentially many possibilities.

Enter QAOA — the Quantum Approximate Optimization Algorithm, introduced in 2014 by Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. Instead of searching through all possible solutions, QAOA prepares a quantum state that is a superposition of many solutions at once, then gently nudges it toward the good ones using two alternating operations applied in sequence.

The key insight: a quantum bit can be 0 and 1 simultaneously. A register of n qubits can represent all 2n2^{n} combinations at once. QAOA steers that superposition with problem-specific rotations (encoding the cost function) and mixing rotations (keeping all options alive). Tune the rotation angles — and more layers means a finer steer — and the circuit's output concentrates on near-optimal solutions.

QAOA sits at the frontier of what today's noisy quantum hardware can run. Its status is open: proven to match the best classical approximation ratio for some problems at depth p = 1, but whether deeper QAOA achieves a quantum advantage over the best classical algorithms remains one of the central open questions in quantum computing.

Try It: QAOA on MAX-CUT

MAX-CUT asks: partition the nodes of a graph into two groups so the number of edges that cross the partition is as large as possible. It is NP-hard in general, but QAOA can find good approximate cuts.

The demo below simulates QAOA classically on a small 4-node graph. Each layer p applies a cost Hamiltonian (phase-shifts proportional to each edge's contribution) and a mixer (equal superposition rotation). The angles γ and β are optimized at each depth to maximize the expected cut.

<p class="hint">A 4-node graph with 5 edges. QAOA alternates between a <b>cost layer</b> (phase-shifts per edge) and a <b>mixer layer</b> (Hadamard-like rotation). Each layer p brings the quantum state closer to the optimal MAX-CUT.</p>
<div class="graph-row">
  <svg id="graph-svg" viewBox="0 0 200 160" width="200" height="160"></svg>
  <div class="panel">
    <div class="stat-row"><span class="lbl">Layers p</span><span id="p-val" class="val">0</span></div>
    <div class="stat-row"><span class="lbl">Best cut found</span><span id="cut-val" class="val">–</span></div>
    <div class="stat-row"><span class="lbl">Optimal cut</span><span id="opt-val" class="val">4</span></div>
    <div class="stat-row"><span class="lbl">Approx ratio</span><span id="ratio-val" class="val">–</span></div>
    <div class="bar-wrap"><div id="bar" class="bar"></div></div>
  </div>
</div>
<div id="state-label" class="state-label">Click "Run Layer" to start QAOA.</div>
<div class="btns">
  <button id="btn-step" type="button">Run Layer (p+1)</button>
  <button id="btn-measure" type="button">Measure</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>
<div id="probs" class="probs"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.graph-row { display: flex; gap: 1rem; align-items: flex-start; flex-wrap: wrap; margin-bottom: .5rem; }
#graph-svg { flex-shrink: 0; border: 1px solid #dde3ea; border-radius: 10px; background: #f7f9fb; }
.panel { flex: 1; min-width: 160px; }
.stat-row { display: flex; justify-content: space-between; margin: .22rem 0; }
.lbl { color: #555; }
.val { font-weight: 700; color: #1d3557; }
.bar-wrap { height: 12px; background: #dde3ea; border-radius: 6px; margin-top: .5rem; overflow: hidden; }
.bar { height: 100%; width: 0%; background: #2a9d8f; border-radius: 6px; transition: width .4s; }
.state-label { font-size: .85rem; color: #555; margin: .3rem 0 .5rem; min-height: 1.2em; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .6rem; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.probs { display: flex; flex-wrap: wrap; gap: 4px; }
.prob-cell { display: flex; flex-direction: column; align-items: center; font-size: 11px;
             background: #eef2f6; border-radius: 6px; padding: 3px 5px; min-width: 44px; }
.prob-cell.high { background: #2a9d8f; color: #fff; }
.prob-cell .pct { font-weight: 700; font-size: 12px; }
line.edge { stroke: #90a4b4; stroke-width: 2; }
line.cut-edge { stroke: #e63946; stroke-width: 2.5; stroke-dasharray: 5 3; }
circle.node { fill: #fff; stroke: #1d3557; stroke-width: 2; }
circle.node.group0 { fill: #457b9d; }
circle.node.group1 { fill: #e63946; }
text.node-lbl { font: 700 12px system-ui; fill: #fff; dominant-baseline: middle; text-anchor: middle; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// QAOA simulation on a 4-node, 5-edge graph for MAX-CUT.
// Nodes: 0,1,2,3. Edges: (0,1),(0,2),(1,2),(1,3),(2,3).
// Optimal MAX-CUT = 4 (partition {0,3} vs {1,2}).
// We represent the full 2^4 = 16 amplitude vector and apply
// the QAOA unitary exactly (classically).

const N = 4;  // qubits
const DIM = 1 << N; // 16 basis states
const EDGES = [[0,1],[0,2],[1,2],[1,3],[2,3]];
const OPT_CUT = 4;
const NODE_POS = [{x:40,y:50},{x:160,y:50},{x:40,y:120},{x:160,y:120}];

// Precompute cut value for each basis state
function cutValue(s) {
  let c = 0;
  for (const [u,v] of EDGES) {
    const bu = (s >> u) & 1, bv = (s >> v) & 1;
    if (bu !== bv) c++;
  }
  return c;
}
const CUT = Array.from({length: DIM}, (_, s) => cutValue(s));

// QAOA angles: numerically optimized (γ, β) pairs for p = 1..5 on this graph.
// Angles found by coordinate descent maximizing E[cut] for the 4-node 5-edge instance.
const ANGLES = [
  [0.5655, 0.3142],                                     // p=1  ratio≈0.809
  [1.0472, 0.6807, 0.9425, 0.4712],                     // p=2  ratio≈0.887
  [0.6472, 0.3307, 1.4425, 0.4212, 1.2040, 0.4298],    // p=3  ratio≈0.996
  [0.6972, 0.3307, 1.4425, 0.3212, 1.1040, 0.3798, 0.6132, 0.1509], // p=4 ratio≈0.995
  [0.5972, 0.3807, 1.2925, 0.3212, 1.0040, 0.3298, 0.6132, 0.1009, 0.3906, 0.1056], // p=5 ratio≈0.999
];

// Apply cost unitary: U_C(γ) = exp(-i γ H_C)
// For each edge (u,v): phase += -γ/2 if bits differ, so multiply by exp(+iγ/2) if differ, exp(-iγ/2) if same.
// Actually standard: C|z> = (number of cut edges)*|z>, so U_C(γ)|z> = exp(-iγC(z))|z>
function applyCost(amp, gamma) {
  const out = amp.slice();
  for (let s = 0; s < DIM; s++) {
    const angle = -gamma * CUT[s];
    const re = out[s][0], im = out[s][1];
    out[s] = [re * Math.cos(angle) - im * Math.sin(angle),
              re * Math.sin(angle) + im * Math.cos(angle)];
  }
  return out;
}

// Apply mixer unitary: U_B(β) = exp(-i β H_B), H_B = sum_j X_j
// exp(-i β X) on qubit j: [[cos β, -i sin β], [-i sin β, cos β]]
// Applied to full state by iterating over each qubit.
function applyMixer(amp, beta) {
  let state = amp.slice();
  for (let q = 0; q < N; q++) {
    const next = state.map(() => [0, 0]);
    for (let s = 0; s < DIM; s++) {
      const t = s ^ (1 << q); // flip qubit q
      const c = Math.cos(beta), sg = Math.sin(beta);
      const [re, im] = state[s];
      next[s][0] += c * re;
      next[s][1] += c * im;
      next[t][0] += sg * im;   // -i * (-i sinβ) = sinβ ... careful
      next[t][1] += -sg * re;  // contribute -i sinβ * amp[s]
    }
    state = next;
  }
  return state;
}

// Full QAOA state for p layers using precomputed angles
function runQAOA(p) {
  // Start in uniform superposition |+>^n
  const amp = Array.from({length: DIM}, () => [1/Math.sqrt(DIM), 0]);
  const angles = ANGLES[Math.min(p,5) - 1];
  for (let layer = 0; layer < p && layer < 6; layer++) {
    const gamma = angles[2 * layer] ?? 0.2;
    const beta  = angles[2 * layer + 1] ?? 0.3;
    const a2 = applyCost(amp, gamma);
    const a3 = applyMixer(a2, beta);
    for (let s = 0; s < DIM; s++) amp[s] = a3[s];
  }
  return amp;
}

// Expected cut value from amplitudes
function expectedCut(amp) {
  let e = 0;
  for (let s = 0; s < DIM; s++) {
    const prob = amp[s][0]**2 + amp[s][1]**2;
    e += prob * CUT[s];
  }
  return e;
}

// ── UI state ────────────────────────────────────────────────────────────────────────────
let currentP = 0;
let currentAmp = Array.from({length: DIM}, () => [1/Math.sqrt(DIM), 0]);
let measuredState = null;

const svg = document.getElementById('graph-svg');
const pVal = document.getElementById('p-val');
const cutVal = document.getElementById('cut-val');
const ratioVal = document.getElementById('ratio-val');
const bar = document.getElementById('bar');
const stateLabel = document.getElementById('state-label');
const probsDiv = document.getElementById('probs');

function drawGraph(partition) {
  svg.innerHTML = '';
  // Draw edges
  for (const [u,v] of EDGES) {
    const isCut = partition && (partition[u] !== partition[v]);
    const line = document.createElementNS('http://www.w3.org/2000/svg','line');
    line.setAttribute('x1', NODE_POS[u].x); line.setAttribute('y1', NODE_POS[u].y);
    line.setAttribute('x2', NODE_POS[v].x); line.setAttribute('y2', NODE_POS[v].y);
    line.setAttribute('class', isCut ? 'edge cut-edge' : 'edge');
    svg.appendChild(line);
  }
  // Draw nodes
  NODE_POS.forEach((pos, i) => {
    const g = partition ? (partition[i] ? 'group1' : 'group0') : '';
    const c = document.createElementNS('http://www.w3.org/2000/svg','circle');
    c.setAttribute('cx', pos.x); c.setAttribute('cy', pos.y); c.setAttribute('r', 16);
    c.setAttribute('class', 'node ' + g);
    svg.appendChild(c);
    const t = document.createElementNS('http://www.w3.org/2000/svg','text');
    t.setAttribute('x', pos.x); t.setAttribute('y', pos.y);
    t.setAttribute('class', 'node-lbl');
    t.textContent = i;
    svg.appendChild(t);
  });
}

function updateStats(amp) {
  const ec = expectedCut(amp);
  const ratio = ec / OPT_CUT;
  cutVal.textContent = ec.toFixed(2);
  ratioVal.textContent = ratio.toFixed(3);
  bar.style.width = (ratio * 100).toFixed(1) + '%';
}

function renderProbs(amp) {
  probsDiv.innerHTML = '';
  const probs = amp.map(([r,i]) => r*r + i*i);
  const maxP = Math.max(...probs);
  probs.forEach((p, s) => {
    if (p < 0.001) return;
    const cell = document.createElement('div');
    cell.className = 'prob-cell' + (p >= maxP * 0.8 ? ' high' : '');
    cell.innerHTML = `<span>${s.toString(2).padStart(N,'0')}</span><span class="pct">${(p*100).toFixed(1)}%</span>`;
    probsDiv.appendChild(cell);
  });
}

function init() {
  currentP = 0;
  currentAmp = Array.from({length: DIM}, () => [1/Math.sqrt(DIM), 0]);
  measuredState = null;
  pVal.textContent = '0';
  cutVal.textContent = '–';
  ratioVal.textContent = '–';
  bar.style.width = '0%';
  stateLabel.textContent = 'Click "Run Layer" to start QAOA.';
  drawGraph(null);
  probsDiv.innerHTML = '';
}

document.getElementById('btn-step').addEventListener('click', () => {
  if (currentP >= 5) { stateLabel.textContent = 'Max depth p=5 reached. Try Measure or Reset.'; return; }
  currentP++;
  currentAmp = runQAOA(currentP);
  pVal.textContent = currentP;
  updateStats(currentAmp);
  renderProbs(currentAmp);
  stateLabel.textContent = fmt('After p=%currentP% %v%', { currentP: currentP, v: currentP > 1 ? 'layers: quantum state sharpened around good cuts.' : 'layer: quantum state sharpened around good cuts.' });
  measuredState = null;
  drawGraph(null);
});

document.getElementById('btn-measure').addEventListener('click', () => {
  if (currentP === 0) { stateLabel.textContent = 'Run at least one layer first.'; return; }
  // Sample from probability distribution
  const probs = currentAmp.map(([r,i]) => r*r + i*i);
  let rand = Math.random(), cum = 0, s = 0;
  for (; s < DIM - 1; s++) { cum += probs[s]; if (cum >= rand) break; }
  measuredState = s;
  const partition = Array.from({length: N}, (_, q) => (s >> q) & 1);
  const c = CUT[s];
  drawGraph(partition);
  stateLabel.textContent = fmt('Measured |%s%⟩— cut = %c% edges (optimal = %OPT_CUT%). Blue vs red = the two groups.', { s: s.toString(2).padStart(N,'0'), c: c, OPT_CUT: OPT_CUT });
  console.log('QAOA measured state:', s.toString(2).padStart(N,'0'), 'cut:', c, 'p:', currentP);
});

document.getElementById('btn-reset').addEventListener('click', init);

// Verify: at p=1, expected cut should be >= 3.0 (ratio >= 0.75)
const testAmp = runQAOA(1);
const ec1 = expectedCut(testAmp);
console.assert(ec1 >= 3.0, fmt('p=1 expected cut should be >= 3.0, got %ec1%', { ec1: ec1.toFixed(4) }));
console.log('QAOA p=1 expected cut:', ec1.toFixed(4), '/ OPT=', OPT_CUT, 'ratio:', (ec1/OPT_CUT).toFixed(4));

init();
Result
Console

Notice how the expected cut fraction rises as you add layers. At p = 0 a random assignment gives ~50 % of edges cut. Each extra layer lets the quantum state explore a richer landscape of interference, boosting the approximation ratio toward 1. The classical simulation of p layers costs O(2n×p)O(2^{n} \times p) operations — feasible here but exponential for large n.

The Real Complexity

QAOA's complexity story is nuanced — and genuinely unresolved.

  • What's proven at p = 1: For MAX-CUT on 3-regular graphs, depth-1 QAOA achieves an approximation ratio of at least 0.6924, matching the best ratio achievable by a simple classical algorithm for that class. Farhi et al. proved this in 2014.
  • What's conjectured for large p: As p → ∞, QAOA should in principle converge to the true optimum (it simulates quantum annealing in the limit). In practice, hardware noise and the cost of angle optimization limit p to small values.
  • The open question: Does QAOA for any finite p outperform the best classical polynomial-time approximation algorithms on general NP-hard instances? This is unknown. No superpolynomial quantum speedup for optimization has been proven.
  • Hardness of classical simulation: Simulating QAOA exactly for large n requires exponential classical memory — which is why real quantum hardware matters. But "hard to simulate" does not automatically mean "better than classical heuristics."
  • Relation to complexity classes: QAOA outputs are sampled from distributions that may be classically hard to reproduce (related to quantum simulation), but this hardness of sampling does not directly imply a speedup for optimization.

The algorithm is open in status. It is the leading candidate for near-term quantum advantage, but the question of whether it truly outperforms the best classical algorithms — like the Goemans–Williamson SDP relaxation for MAX-CUT — remains one of the biggest open problems at the intersection of quantum computing and P vs NP.

Where It Matters

Every industry has NP-hard scheduling or selection problems where even a few percent improvement in solution quality translates to large gains. QAOA is being explored across all of them:

  • Portfolio optimization: select a basket of assets that maximizes return for a given risk budget. The combinatorial version (integer weights, sector constraints) maps directly to QAOA.
  • Drug discovery: finding molecular configurations that minimize energy is equivalent to a combinatorial optimization over discrete chemical graphs — an active QAOA research direction.
  • Logistics and routing: vehicle routing, warehouse layout, and network traffic shaping are all NP-hard combinatorial problems regularly attacked by QAOA variants.
  • Machine learning: training some discrete neural architectures and performing feature selection can be framed as MAX-CUT or graph coloring instances.
  • Telecommunications: frequency assignment, antenna placement, and network partitioning are natural MAX-CUT relatives well-suited to QAOA.

For now, classical solvers — especially problem-specific heuristics and the Goemans–Williamson algorithm — outperform QAOA on the hardware available today. The race is to find a problem class and a qubit count where QAOA pulls ahead. When that happens, the payoff will cascade across every field that touches combinatorial optimization.

Conclusion

QAOA is quantum computing's most promising near-term tool for hard optimization. Its elegant structure — alternate between encoding the cost function and mixing all solutions — can run on today's noisy hardware with modest depth. At depth p = 1 it already matches simple classical approximations for some problems, and deeper circuits inch closer to optimal.

Yet the central question is wide open: does QAOA, at any practical depth, outperform the best classical algorithms? The answer will reshape what we expect from the quantum computers being built right now. Until then, QAOA occupies a peculiar place — a provably quantum algorithm whose advantage over classical methods has not been proven, chasing problems that may never yield a clean quantum speedup but might still deliver a practical one.

The story of QAOA is the story of P vs NP seen through a quantum lens: we suspect hard problems can be tamed, but proving it — classically or quantumly — remains the great open challenge of our era.

Share this article

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

Comments

Loading comments...

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