QAOA

QAOA is for combinatorial optimization. That means picking the best choice out of a huge number of yes-or-no combinations. Examples are MaxCut, scheduling, delivery routes, and choosing stocks. Think of seating guests at a wedding so that people who argue sit at different tables. With just 30 guests and two tables, there are over a billion ways to split them (2 multiplied by itself 30 times).

Here is MaxCut, the example on this page. You have dots joined by lines, called a graph. Color each dot one of two colors. You "cut" a line when its two ends get different colors. The goal is to cut as many lines as possible.

These problems are worth a lot of money, which explains why QAOA is popular. They are also NP-hard, meaning no one knows a fast method for the hardest cases. That sets the honest expectation: quantum computers are not expected to solve NP-hard problems quickly. There is no exponential speedup on offer here, even in theory.

The real question QAOA asks is smaller. Can a short quantum circuit find better rough answers, or find them faster, than normal shortcut methods? So far the answer on every published test is no. But the recipe is simple, fits current hardware well, and has been studied a lot.

Very good. Methods like simulated annealing, tabu search, and local search handle problems with millions of variables. Industrial solvers like Gurobi and CPLEX can prove they found the best answer on large real problems. For MaxCut in particular, the Goemans–Williamson algorithm always gets at least 87.8% of the best cut, and it runs quickly. Any quantum claim has to beat these methods, not just blind guessing. Marketing often forgets that bar.

You turn the problem's scoring rule into phases, so each bitstring's score becomes a turn of its phase. (A phase is like the angle of a clock hand on each amplitude. An amplitude is the number that sets how likely an answer is.) One QAOA layer has two steps:

• Cost step: for each line in the graph, a small circuit (here CX–RZ–CX) turns the phase of each bitstring based on its score. How far it turns depends on an adjustable angle, γ (gamma).
• Mixer step: RX turns on every qubit, by an angle β (beta). These make the phase differences interfere. That moves chance from some bitstrings to others.

Phases alone can't be seen by measuring (see amplitudes and phase). The mixer is what turns them into a lean you can measure. You stack p layers, take samples, and let a normal optimizer tune the 2p angles. With endless layers, the recipe can reach the exact best answer. At the small p that noise allows, it is a rule of thumb. How good its output is depends completely on the angles.

Think of tuning an old radio with two knobs. The radio itself does nothing clever. Everything depends on where you set the knobs.

• No proven advantage. After ten years of study, there is no optimization problem where QAOA beats the best normal method, in theory or in tests. Worse, theory shows that simple normal methods beat low-depth QAOA on known kinds of graphs.
• Finding the angles is hard too. The search for good angles has the same traps as VQE. These include barren plateaus (huge flat regions where the optimizer can't tell which way is better) and dead ends. In fact, QAOA is VQE with one specific circuit shape built from the cost function.
• Wiring cost. Every line in your graph needs a two-qubit gate. On chips where each qubit connects to only a few others, far-apart pairs need chains of SWAP gates. Those make the circuit deeper fast. See connectivity costs. Graphs with many lines are especially costly.
• Depth versus noise. Better answers need more layers p. But noise limits today's machines to small p. That is exactly where normal methods win. Those short circuits can often be simulated on a normal computer anyway.

QAOA runs often on real devices. One example is a 23-qubit MaxCut study on Google's Sycamore chip in 2020. Its results dropped sharply once the problem's graph stopped matching the chip's own wiring. More recent runs reach 100+ qubits on superconducting and trapped-ion hardware, using error mitigation (math tricks that reduce the effect of noise). These are real runs of the algorithm at a meaningful size. Check the machines on the hardware comparison.

What none of them show is an advantage. In every published comparison, normal solvers matched or beat the quantum result. They usually won by a wide margin, at a tiny part of the cost. Today QAOA is a research tool and a hardware test. Try both angle settings above in the lab. Watch how completely the chart depends on two numbers.