Skip to content

Quantum Approximate Optimization Algorithm (QAOA)

Recall the hybrid loop from VQE: prepare a trial state, measure something about it, let a classical optimizer propose a better set of parameters, repeat. The Quantum Approximate Optimization Algorithm (QAOA) follows the exact same pattern — the difference is what's being optimized. VQE searches for a state with the lowest possible energy. QAOA searches for a bitstring that's a good answer to a combinatorial optimization problem.

QAOA itself isn't tied to any one problem — it applies broadly to QUBO problems (Quadratic Unconstrained Binary Optimization: choosing a yes/no value for each variable to optimize some score that depends on pairs of those choices), which covers things like portfolio optimization (which assets to include) as well as graph problems. This page uses one specific, simple QUBO problem as a running example, because it's easy to visualize and easy to check by hand.

The Problem: MaxCut

That example is MaxCut: given a graph, split its nodes into two groups so that as many edges as possible have one endpoint in each group. Each edge that ends up with its two endpoints in different groups is "cut."

The example used on this page is a 4-node cycle:

1 —— 2
|    |
4 —— 3

with edges (1,2), (2,3), (3,4), (4,1). The best possible split here is clean: put nodes 1 and 3 in one group, and 2 and 4 in the other — every single edge gets cut.

Interactive: Try It By Hand

Before bringing in any quantum machinery, try the problem yourself. Click a node to move it between Group A (blue) and Group B (gray). An edge turns green when it's cut.

1 2 3 4

Cut edges: 0 / 4

All four nodes start in Group B. Click nodes to try to cut all 4 edges.

Encoding the Problem: Cost and Mixer

QAOA turns this into a quantum search using two ingredients:

  • A cost Hamiltonian that scores a grouping by how many edges it cuts — groupings that cut more edges get a higher value.
  • A mixer Hamiltonian that lets the circuit move between different groupings, instead of getting stuck evaluating just one.

The cost Hamiltonian plays the same role as VQE's \(H\) — it's what gets measured. The mixer doesn't have as clean a VQE analogue, though: VQE's single ansatz gate, \(RY(\theta)\), both encodes the trial state and creates superposition between \(|0\rangle\) and \(|1\rangle\) in the same step. QAOA splits that into two separate pieces — the cost layer only tags bitstrings with a phase (no mixing on its own), and the mixer is specifically what moves amplitude between them. What is the same in both algorithms is the classical optimizer's job: it searches between iterations — new \(\theta\) in VQE, new \(\gamma,\beta\) in QAOA — it doesn't do any of the mixing itself in either one.

Show the math →

Start classically. Give each node a binary decision variable \(x_i \in \{0,1\}\) (1 = Group A, 0 = Group B). An edge \((i,j)\) is cut exactly when \(x_i \neq x_j\), which the following expression captures — it's 1 when they differ and 0 when they agree:

\[ \text{cut}(i,j) = x_i + x_j - 2x_i x_j \]

The classical objective is just the sum of this over every edge: \(\sum_{(i,j)\in E} \text{cut}(i,j)\).

Switch to \(\pm1\) variables. Quantum operators like \(Z\) have eigenvalues \(\pm1\), not \(0\) and \(1\), so substitute \(x_i = \frac{1 - z_i}{2}\) with \(z_i \in \{-1,+1\}\). Plugging this into \(\text{cut}(i,j)\) and simplifying:

\[ \text{cut}(i,j) = \frac{1 - z_i z_j}{2} \]

Same expression, same values — just written in terms of variables that are now ±1 instead of 0/1.

Promote to operators. Replacing each classical \(z_i\) with the Pauli operator \(Z_i\) (whose eigenvalues on \(|0\rangle, |1\rangle\) are exactly \(+1, -1\)) turns the classical objective into the quantum cost Hamiltonian the circuit actually uses:

\[ C = \sum_{(i,j) \in E} \frac{1 - Z_i Z_j}{2} \]

Measuring \(C\) on a given bitstring reproduces exactly the classical cut count for that grouping — the Hamiltonian hasn't changed what's being counted, only how it's represented. The mixer Hamiltonian, by contrast, has no classical counterpart to build up this way — it's simply

\[ B = \sum_i X_i \]

which flips individual qubits and is what allows the circuit to move between different groupings at all.

The QAOA Circuit: p Layers of Cost + Mixer

Neither \(C\) nor \(B\) is itself a gate — they're Hamiltonians, and a circuit can't apply a Hamiltonian directly. The fix is the same trick physics uses to turn a Hamiltonian into time evolution: exponentiate it. For any Hamiltonian \(H\) and real angle \(\theta\), \(e^{-i\theta H}\) is unitary — a legitimate gate — so \(e^{-i\gamma C}\) and \(e^{-i\beta B}\) below are real, applicable operations, not just notation borrowed from \(C\) and \(B\).

The two behave differently once exponentiated, though. \(C\) is built from \(Z\) and \(Z_iZ_j\) terms, which are diagonal — so \(e^{-i\gamma C}\) doesn't change which bitstring you'd measure, it only tags each one with a phase tied to its cut value. \(B\) is built from \(X\) terms, which aren't diagonal — so \(e^{-i\beta B}\) actively redistributes amplitude between bitstrings. Applying them in sequence, over several rounds, is what turns those cost-dependent phase tags into an actual shift in the measured probabilities: the mixer repeatedly converts "tagged" phase differences into amplitude differences, which is the mechanism behind the probability bars you'll see shift in the next demo.

With that, the full ansatz starts every qubit in an equal superposition — representing all possible groupings at once — then alternates a cost layer and a mixer layer, \(p\) times:

\[ |\psi(\beta,\gamma)\rangle = \underbrace{e^{-i\beta_p B} e^{-i\gamma_p C} \cdots e^{-i\beta_1 B} e^{-i\gamma_1 C}}_{p \text{ layers}} |+\rangle^{\otimes n} \]

Each layer has its own pair of angles, \(\gamma\) (cost) and \(\beta\) (mixer) — these are the parameters the classical optimizer tunes, the same role \(\theta\) played in VQE. More layers generally means a better approximation to the true MaxCut, at the cost of a longer, noisier circuit.

Interactive: Run the Optimizer Loop (p = 1)

At \(p=1\) there are only two angles to find, \(\gamma_1\) and \(\beta_1\), so it's the simplest place to see the loop itself. It runs exactly like VQE's loop, with the cost Hamiltonian \(C\) standing in for \(H\):

  1. The quantum computer prepares \(|+\rangle^{\otimes 4}\) with H gates, then applies \(e^{-i\beta_1 B} e^{-i\gamma_1 C}\) using the current guess for \(\gamma_1,\beta_1\).
  2. That circuit is run (and measured) a fixed number of times — not once. Each run just gives one bitstring, so what you actually get back is a distribution over bitstrings, not a number.
  3. The classical side evaluates the ordinary cut-count formula on every sampled bitstring and averages the results, which is how \(\langle C \rangle\) is calculated — it's a classical computation performed on quantum measurement outcomes, not something read directly off the hardware.
  4. The classical optimizer looks at that estimated \(\langle C \rangle\) and proposes new angles expected to raise it. (Raise, not lower — QAOA maximizes a cut count, where VQE minimized an energy, so the optimizer's direction flips, but the loop structure is identical.)
  5. Repeat.

Before any tuning at all (\(\gamma_1=\beta_1=0\)), no cost or mixer layer has actually done anything yet — the state is still the plain equal superposition, so \(\langle C \rangle\) is just the average cut over all 16 groupings, exactly \(2.00\). Watch that number move as the loop runs.

Quantum Processor
idle
—
—
Classical Optimizer
idle

Iteration: 0

Click Prepare to begin the first iteration.

This loop is what actually finds \(\gamma_1,\beta_1\) — nothing about adding more layers changes this picture, it just means running the same kind of loop again, searching over twice as many angles for \(p=2\), three times as many for \(p=3\), and so on. The demo below skips ahead to the converged result for each \(p\), so the focus stays on how the outcome changes with more layers rather than re-running the loop every time.

Interactive: p Layers of Cost + Mixer

All four qubits start in the equal superposition \(|+\rangle^{\otimes 4}\), prepared by the H gates at the left of the circuit below — that's the input state the first cost layer acts on. Each layer after that adds its own pair of angles, \(\gamma\) (cost) and \(\beta\) (mixer); finding good values for those angles, for whatever \(p\) you pick, requires a full run of the loop above, not just a longer circuit. Toggling \(p\) alone doesn't improve anything; the bars below assume that loop has already converged for that \(p\). Use the Untuned angles toggle to see what happens when it hasn't.

q₁ q₂ q₃ q₄ H H H H Cost γ₁ Mixer β₁ M M M M

0101 (cut = 4)
1010 (cut = 4)
0011 (cut = 2)
0000 (cut = 0)

Reading Out an Answer

The optimizer loop doesn't produce a bitstring by itself — every run inside that loop only ever produces an estimated \(\langle C \rangle\), used purely to decide which angles to try next. QAOA isn't finished once that loop converges; there's one more step. Using the best angles the loop found, the circuit is run again — many times over — and this final batch of samples is the actual output: a distribution over bitstrings, the kind shown in the demo above. The answer is whichever bitstring (or small handful of bitstrings) came up with the highest probability in that distribution. Nothing about this final sampling step feeds back into the optimizer; the search is already done by the time it happens.

QAOA's whole job, across every piece covered so far, is to bias that final distribution toward good groupings, the way the bars above concentrate more as \(p\) grows — it doesn't guarantee the optimal one shows up, especially at low \(p\), which is exactly why you're reading off a probability, not a certainty.

This is a different kind of output than VQE's. VQE gives you a number: an estimated ground-state energy. QAOA gives you a bitstring: a candidate solution you can check directly (just count its cut edges).

QAOA vs. VQE

VQE QAOA
Output A number (estimated ground-state energy) A bitstring (a candidate solution)
Problem type Continuous optimization Combinatorial / discrete optimization
Classical counterpart Diagonalizing a Hamiltonian Brute-force search over groupings
  • ✓ Same NISQ-friendly philosophy as VQE — short circuits, classical optimizer does the iterative work
  • ✓ More layers (\(p\)) generally improves solution quality
  • ✗ Not guaranteed to find the true optimal cut, especially at low \(p\)
  • ✗ More layers means a longer, noisier circuit — a real tradeoff, not a free improvement

Takeaway

Run p layers of cost + mixer Sample, estimate ⟨C⟩ Classical optimizer updates β, γ repeat once converged Sample again — best cut found

VQE and QAOA are two instances of the same hybrid variational pattern — prepare, measure, let a classical optimizer adjust, repeat — aimed at two very different kinds of problems: a continuous energy to minimize, and a discrete choice to search over. The same pattern extends further still: a Variational Quantum Classifier applies it to machine learning, and techniques like SQD apply it in other ways, though neither has its own lesson here yet.

Back to Module 06 Overview →