QAOA: Quantum Approximate Optimization Algorithm

Why Combinatorial Optimization Is Hard

Combinatorial optimization problems ask you to find the best arrangement among a huge number of discrete possibilities, such as the best way to split a network's nodes into two groups to cut the most connections (the Max-Cut problem). The trouble is that the number of possible arrangements grows exponentially with problem size, so checking every option becomes impossible even for modest inputs. Many of these problems are classified as NP-hard, meaning no known classical algorithm can solve every instance quickly, forcing reliance on approximations and heuristics. This is exactly the kind of exponential haystack where quantum computers, which can represent many possibilities simultaneously, might offer a genuine edge.

Alternating Cost and Mixer Layers

QAOA, introduced by Farhi, Goldstone, and Gutmann in 2014, encodes a candidate solution to an optimization problem as a state of qubits, then repeatedly applies two alternating quantum operations. The cost unitary applies phase shifts that reward qubit configurations corresponding to good solutions, while the mixer unitary spreads amplitude between configurations, letting the algorithm explore neighboring solutions. Repeating this cost-then-mixer pattern for p layers builds up interference that constructively reinforces high-quality solutions and destructively cancels poor ones. Measuring the final state then yields a bitstring that, with reasonably high probability, represents a good — though not guaranteed optimal — answer to the original problem.

Tuning the Angles in a Hybrid Loop

Each layer of QAOA has two adjustable parameters, conventionally called beta and gamma, which control how strongly the mixer and cost operations act during that round. Because there is no simple formula for the best angles, QAOA runs as a hybrid quantum-classical algorithm: the quantum computer prepares the state and measures an average cost, and a classical optimizer on a regular computer adjusts the angles to improve that cost. This loop repeats, with the quantum processor and classical optimizer trading information back and forth, gradually steering the angles toward values that make the measured solutions as good as possible. This division of labor lets QAOA exploit quantum effects for exploration while leaning on mature classical optimization methods for the tuning itself.

Real-World Use and Current Limits

QAOA is most often studied on graph problems like Max-Cut, and more broadly on any task that can be reformulated as minimizing a cost function over discrete variables, including abstract versions of scheduling, routing, and portfolio-style combinatorial selection problems. It is a leading candidate algorithm for today's NISQ (noisy intermediate-scale quantum) hardware because it uses relatively shallow circuits that can tolerate some noise. That said, QAOA has not yet demonstrated a proven quantum advantage over the best classical algorithms on any practically important problem, and its performance depends heavily on circuit depth, angle optimization quality, and hardware noise levels, so it remains an active and still-unsettled area of quantum computing research.

Frequently asked questions

Does QAOA guarantee the optimal solution?

No. QAOA is an approximate, heuristic algorithm — it produces a probability distribution over candidate solutions biased toward good ones, not a certified optimum. Running it and taking the best sampled result across many shots typically gives a strong approximate answer, and increasing the number of layers p generally improves solution quality, though at the cost of a deeper, noisier circuit.

What does the letter p mean in QAOA?

p is the number of alternating cost-mixer layers applied in the circuit. In principle, as p grows toward infinity, QAOA can be shown to converge toward adiabatic quantum optimization and find the true optimal solution. In practice, current hardware noise and gate errors limit how large p can usefully be, so real implementations typically use small values like p=1 to p=10.

Is QAOA the same as quantum annealing?

They are related but distinct. Quantum annealing, used by hardware like D-Wave systems, continuously evolves a quantum state along a physical annealing schedule on specialized hardware. QAOA instead runs on gate-based universal quantum computers as a discrete circuit with a fixed number of tunable layers, making it a digital, more flexible approximation of the same underlying adiabatic idea.

Try it live

Everything above runs in your browser — open QAOA: Quantum Approximate Optimization Algorithm and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.

▶ Open QAOA: Quantum Approximate Optimization Algorithm simulation