Measuring and Decoding Solutions

At the end of a QAOA circuit the quantum state is a superposition of many bitstrings, each with some amplitude. Measurement in the computational basis collapses the state to a single bitstring, and the probability of obtaining bitstring $x$ is $|\langle x|\psi(\gamma,\beta)\rangle|^2$ by the Born rule. Repeating the circuit many times and collecting all outcomes yields a probability distribution over candidate solutions; the most frequent bitstrings are the best candidates.

What a measurement outcome means

Every bitstring read off a QAOA circuit corresponds to a concrete assignment of the original combinatorial variables. For a Max-Cut problem on $n$ vertices, a bitstring $x = x_0 x_1 \cdots x_{n-1}$ assigns vertex $i$ to partition 0 if $x_i = 0$ and to partition 1 if $x_i = 1$ . An edge $(i, j)$ is cut whenever $x_i \neq x_j$ , so the cost value for outcome $x$ is immediately computable without any further quantum processing.

This is a key structural feature of QAOA: because the cost Hamiltonian $H_C$ is diagonal in the computational basis, its eigenvalues are exactly the cost values of the corresponding bitstrings. Measuring in the computational basis therefore reads out cost values directly, with no additional basis rotation.

Decoding the best solution

In practice the procedure is:

Run the QAOA circuit with fixed angles $(\gamma, \beta)$ a large number of times (shots).
Record every bitstring and its count.
Evaluate the cost function $C(x)$ classically for each observed bitstring.
Return the bitstring with the highest cost as the candidate solution.

Step 3 is entirely classical and cheap: for Max-Cut, evaluating $C(x)$ for a bitstring of length $n$ takes $O(|E|)$ time on a classical computer.

Why optimal solutions peak in probability

When the variational angles $(\gamma, \beta)$ are well-chosen, QAOA constructively interferes the amplitudes of high-quality solutions and destructively interferes those of low-quality ones. For a $p$ -layer QAOA circuit on an $n$ -qubit system the state after the final layer is

$|\psi(\gamma,\beta)\rangle = U_B(\beta_p)\,U_C(\gamma_p) \cdots U_B(\beta_1)\,U_C(\gamma_1)\,|+\rangle^{\otimes n}.$

The probability of the optimal solution $x^*$ grows with the number of layers $p$ : Farhi, Goldstone and Gutmann (2014) showed that as $p \to \infty$ the distribution concentrates on optimal solutions. Even at small $p$ the most probable outcomes are typically near-optimal, so measuring a modest number of shots already reveals good candidate solutions.

The 2-node Max-Cut example

For the single-edge graph on vertices $\{0, 1\}$ , the two optimal cuts are the bitstrings $01$ and $10$ : each puts the two vertices in different partitions and achieves cost 1. A well-tuned QAOA circuit converges to equal probability $\tfrac{1}{2}$ on both. The state is

$|\psi\rangle = \tfrac{1}{\sqrt{2}}\bigl(|01\rangle + |10\rangle\bigr),$

which is maximally entangled across the two vertices. Measuring this state yields $01$ or $10$ each with probability $\tfrac{1}{2}$ , and both bitstrings represent the maximum cut.

Try it

Build a 2-qubit circuit that ends with equal probability on the Max-Cut solutions $|01\rangle$ and $|10\rangle$ , then measure. The grader checks the output distribution.

Run your code to see the quantum state.

After pressing Run you should see two equal-height bars at bitstrings 01 and 10. Both bitstrings cut the single edge $(0, 1)$ — they differ only in which vertex is labelled 0 vs 1 in each partition, so they represent the same cut up to a global relabelling.