Saturday, September 19, 2026

QAOA: Turning a Score into a Probability

The Quantum Approximate Optimization AlgorithmQAOA: a hybrid quantum-classical method that writes each candidate answer's score into quantum phase, then uses interference to make better answers more likely to be measured. writes the quality of each possible answer into quantum phaseThe angle associated with a quantum amplitude. Differences between these angles determine how amplitudes interfere., then uses interferenceThe addition of quantum amplitudes, which can reinforce or cancel one another depending on their relative phases. to make better answers more likely to appear.

The MaxCut problem

Suppose you have a network and want to divide its nodes into two groups so that as many connections as possible run between the groups. This is the MaxCutThe problem of splitting a network's nodes into two groups so that as many connections as possible run between the groups. problem. For any proposed division, calculating its score is easy; finding the best division is the hard part, because n nodes already give 2ⁿ possible answers. A quantum computer can begin with all those bit strings represented in one state:

|+⟩^⊗n

But this alone solves nothing. If every candidate has equal amplitudeThe complex number attached to each possible outcome of a quantum state. Its size sets the outcome probability and its angle is the phase., measuring the qubitsThe basic unit of a quantum computer. Like a 'bit' in a normal computer, but instead of being only 0 or 1 it can be 0, 1, or a blend of both at once. simply gives a random bit string, so QAOA needs a way to reshape those probabilities.

First, write the score into phase

Turn the optimization problem into a cost HamiltonianAn operator built so that each candidate answer, written as a bit string, has the answer's score as its value. H_C, constructed so that every computational basis stateOne definite bit string of a qubit register, such as 101. Any quantum state of the register is a combination of these. corresponds to one candidate solution and its eigenvalueOne of the possible outcomes associated with measuring an observable. For a Hamiltonian, its eigenvalues are the system's allowed energies. gives that solution’s score. QAOA applies¹

U_C(γ)  =  e^−iγH_C

Candidates with different scores accumulate different phases. Here is the important catch: phase is not probability. Immediately after this operation, measuring the qubits would still give the same probabilities as before. The cost layer has marked the answers, but it has not yet favored them.

Then make the phases interfere

QAOA next applies a mixerThe QAOA step that couples bit strings differing by one bit, letting their phases interfere and shift probability between them.:

U_B(β)  =  e^{−iβ ∑_iX_i}

The mixer couples bit strings that differ by one bit.² Because their amplitudes now carry different phases, they interfere: some contributions reinforce one another, others cancel. With suitable values of γ and β, that interference can move probability toward high-scoring solutions, following the chain score → phase → interference → probability.

The quantum computer is not examining every answer and selecting the best one. It is engineering an interference patternThe banded pattern that appears when waves overlap. Seeing one build up from single particles is the signature of superposition. so that some answers become more likely to appear when the qubits are measured.

What the circuit looks like

The circuit starts by applying a Hadamard gateA one-qubit operation that turns a definite 0 or 1 into a balanced quantum superposition. The standard way to create one. to every qubitThe basic unit of a quantum computer. Like a 'bit' in a normal computer, but instead of being only 0 or 1 it can be 0, 1, or a blend of both at once., preparing the equal superpositionA quantum state that combines multiple basis states, each with its own probability amplitude. |+⟩^⊗n. It then alternates a cost layer and a mixerThe QAOA step that couples bit strings differing by one bit, letting their phases interfere and shift probability between them. layer p times before measuring all qubits. For MaxCutThe problem of splitting a network's nodes into two groups so that as many connections as possible run between the groups. on an unweighted graph, a common cost HamiltonianAn operator built so that each candidate answer, written as a bit string, has the answer's score as its value. is³

H_C  =  ∑_(i,j)∈E (1 − Z_iZ_j) / 2

so each graph edge becomes a two-qubit ZZ-type phase interaction between the qubits representing its endpoints, and the graph determines which pairs interact. The mixer is simpler. Since H_B = ∑_i X_i, it becomes one X-rotation on every qubit: with the convention R_X(θ) = e^−iθX/2, layer k uses R_X(2β_k) on each qubit. The complete circuit therefore has the structure

H^⊗n  →  [U_C(γ_k) → U_B(β_k)]_{k = 1…p}  →  measurementA physical process that produces a classical outcome and updates the quantum state. In an ideal projective measurement, the state is left in an eigenstate associated with the observed outcome.

Each layer has its own pair of parameters (γ_k, β_k), giving 2p adjustable angles. One run produces one candidate bit string. Repeating the circuit estimates the resulting distribution, and a classical optimizer changes the angles to improve the average objective value.⁴ This is why QAOA is a hybrid quantum-classical algorithmA method split between two machines: the quantum computer runs and samples a circuit, and an ordinary computer adjusts the circuit settings to improve the result.: the quantum processor creates and samples the interference patternThe banded pattern that appears when waves overlap. Seeing one build up from single particles is the signature of superposition., while the classical computer searches for the parameters that make it useful.

What p buys you

Increasing p gives QAOA more opportunities to reshape the probability distribution. In an ideal noiseless calculation with perfect parameter optimization, the best achievable value cannot get worse as p increases, because an added layer can simply be set to do nothing.¹ Real hardware changes the bargain. Every extra layer adds more two-qubit interactions, more rotations and two more parameters to optimize, so more depth gives the algorithm more freedom, but also more noise and a harder classical search.⁵

What “approximate” really means

The word approximate is not merely an excuse for noisy hardware. At finite p, even a perfect QAOA circuit generally produces both good and bad solutions; the aim is to shape the distribution so that high-quality answers appear often enough to be useful.

For particular problems and depths, mathematical performance guarantees are known.¹ But there is no general result showing that practical QAOA outperforms the best classical optimization methods.⁵ QAOA therefore gives us a clear quantum mechanism for turning an optimization score into a biased probability distribution. Whether that mechanism ultimately produces a useful computational advantage is a separate question, and still an open one.

Sources

1. Farhi, E., Goldstone, J. & Gutmann, S. “A Quantum Approximate Optimization Algorithm.” Preprint: arXiv:1411.4028 (2014). ↩
2. Hadfield, S., Wang, Z., O’Gorman, B., Rieffel, E. G., Venturelli, D. & Biswas, R. “From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz.” Algorithms 12, 34 (2019). DOI: 10.3390/a12020034. Preprint: arXiv:1709.03489. ↩
3. Wang, Z., Hadfield, S., Jiang, Z. & Rieffel, E. G. “Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View.” Physical Review A 97, 022304 (2018). DOI: 10.1103/PhysRevA.97.022304. Preprint: arXiv:1706.02998. ↩
4. Zhou, L., Wang, S.-T., Choi, S., Pichler, H. & Lukin, M. D. “Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices.” Physical Review X 10, 021067 (2020). DOI: 10.1103/PhysRevX.10.021067. Preprint: arXiv:1812.01041. ↩
5. Willsch, M., Willsch, D., Jin, F., De Raedt, H. & Michielsen, K. “Benchmarking the Quantum Approximate Optimization Algorithm.” Quantum Information Processing 19, 197 (2020). DOI: 10.1007/s11128-020-02692-8. Preprint: arXiv:1907.02359. ↩