QAOA

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

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">{{hint_text}}</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">{{lbl_layers}}</span><span id="p-val" class="val">0</span></div>
    <div class="stat-row"><span class="lbl">{{lbl_best_cut}}</span><span id="cut-val" class="val">–</span></div>
    <div class="stat-row"><span class="lbl">{{lbl_optimal}}</span><span id="opt-val" class="val">4</span></div>
    <div class="stat-row"><span class="lbl">{{lbl_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">{{msg_click_to_start}}</div>
<div class="btns">
  <button id="btn-step" type="button">{{btn_step}}</button>
  <button id="btn-measure" type="button">{{btn_measure}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_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; }

// Code not found

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(2^{n} \times p)$ operations — feasible here but exponential for large n.

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.

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.

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.