QAOA for People Who Aren’t Physicists

If you write software, you have met the shape of this problem before. A set of discrete choices, a way to score any complete set of choices, and far too many possible sets to try them all. Which servers host which services. Which trucks take which routes. Which subset of features goes into the model. You reach for a heuristic, accept a good-enough answer, and move on.

The Quantum Approximate Optimization Algorithm, or QAOA, is a proposal for attacking that shape with a quantum computer. It was published in 2014 by Edward Farhi, Jeffrey Goldstone and Sam Gutmann (arXiv:1411.4028), and it has since become the algorithm people run first when they want to see what a new quantum processor can do on an optimization task.

This piece explains what QAOA actually does. Not the physics motivation, not the field’s hopes for it, but the mechanism: what goes into the circuit, what comes out, and what the classical half of the loop is doing while the quantum half runs. We assume you can read pseudocode and follow an algorithm. We assume nothing about quantum mechanics.

The problems QAOA targets

A combinatorial optimization problem is one where you choose values for a finite set of discrete variables and score the result. The scoring function is usually easy to evaluate. Finding the assignment that scores best is the hard part, because the number of assignments grows exponentially with the number of variables. One hundred binary variables gives you 2^100 possible assignments, which is roughly 10^30. Enumerating them is not a matter of waiting for faster hardware.

Many of these problems are NP-hard, which means no algorithm is known that solves every instance in time polynomial in the input size, and most computer scientists expect none exists. Travelling salesman, knapsack, graph colouring, job-shop scheduling, vehicle routing, maximum cut. In practice you use heuristics: simulated annealing, tabu search, branch-and-bound with good pruning, or a commercial solver like Gurobi that combines several of these. These heuristics solve most real-world instances well enough to ship. They are also, for the hardest instances, still exponential in the worst case.

QAOA doesn’t change that. It is a heuristic too. What it offers is a different mechanism for exploring the space of assignments, one that has no classical equivalent, and the open question is whether that mechanism buys anything at scales that matter.

The loop, in outline

QAOA is a loop with a quantum computer inside it. The loop looks like this:

1. A quantum circuit, controlled by a handful of numeric parameters, produces a probability distribution over candidate solutions.
2. You run the circuit many times and measure, collecting samples from that distribution.
3. You score the samples with your ordinary classical scoring function and average the scores.
4. A classical optimizer adjusts the parameters to push that average up.
5. Repeat until the average stops improving, then keep the best individual sample you saw.

Step 1 is the only unusual step. Steps 2 through 5 are a straightforward optimization loop of the kind you would write for tuning any black-box function with a small number of continuous parameters.

The circuit template with its adjustable parameters is called an ansatz, a word borrowed from German that in this context means a parameterised guess at the right form of the answer. The whole family of algorithms built this way, with a parameterised quantum circuit inside a classical optimization loop, is called variational. QAOA is the variational algorithm designed for discrete optimization.

The two operators

To build the circuit you need two ingredients. Both are described as Hamiltonians, which is a physics word that will not help you here, so translate it immediately: a Hamiltonian, for our purposes, is a scoring function over bitstrings, written in a form a quantum circuit can act on. A bitstring is just what it sounds like: an assignment of 0 or 1 to each of your n variables, one variable per qubit.

The cost Hamiltonian, written H_C, is your objective function. You take the score you would compute classically for a given bitstring and rewrite it as an operator on qubits. The rewriting is mechanical, and we will do it in full for one problem below. The important property is that H_C assigns a value to every possible bitstring, and you arrange the encoding so that better bitstrings score higher. That is the convention the Max-Cut construction below uses, and it matches step 4 of the loop, where the optimizer pushes the average value up. A minimization problem is handled by flipping the sign.

The mixer Hamiltonian, written H_M, is what lets the algorithm move between candidate solutions. The standard choice is the sum of bit-flip operations across all qubits. Without it, the circuit would sit wherever it started. The mixer is what turns a static starting state into a search.

These two operators do not commute, meaning applying them in one order gives a different result than applying them in the other. That non-commuting relationship is where the whole algorithm’s behaviour comes from. If they commuted, all p layers would reduce to one application of each operator, with angles equal to the sums of the individual angles, so adding layers would buy no expressivity beyond those sums.

The circuit

Here is the construction, step by step.

Start every qubit in an equal superposition of 0 and 1. You set each qubit to 0, then apply a Hadamard gate to each. A qubit after a Hadamard is in superposition: when you eventually measure it, you get 0 half the time and 1 half the time. Across n qubits, this means the circuit now holds all 2^n bitstrings with equal weight. No solution is preferred yet.

Apply the cost operator for a duration γ. In circuit terms this means applying the unitary operation e^(-iγH_C). What it does is attach a phase to each bitstring in proportion to that bitstring’s score. Phase is not probability. Measuring right now would still give you a uniformly random bitstring. What the phase does is mark the good solutions in a way that a later operation can convert into probability. This step is sometimes called the phase separator, and γ is one of the tunable parameters.

Apply the mixer for a duration β. This is the unitary e^(-iβH_M), which for the standard mixer amounts to rotating each qubit partway between 0 and 1. This is the step that converts phase differences into probability differences. Bitstrings whose phases line up reinforce each other; bitstrings whose phases oppose cancel out. That reinforcement and cancellation is quantum interference, and it is the only mechanism in QAOA that a classical algorithm cannot straightforwardly copy.

Repeat those two steps p times, with fresh parameters each round. The layer count p is your depth. At p=1 you have two parameters, γ₁ and β₁. At p=3 you have six. More layers give the circuit more room to sculpt the distribution, and Farhi and colleagues showed that solution quality improves as p grows, approaching the optimum in the limit. More layers also mean a longer circuit, and on real hardware a longer circuit means more accumulated error. That tension sets the whole practical shape of the algorithm.

Measure. Every qubit collapses to 0 or 1 and you read off a bitstring. One run and measurement is called a shot. One shot gives you one candidate solution, drawn from the distribution the circuit built.

Estimate and optimize. Take a few thousand shots, score each resulting bitstring with your classical cost function, and average. That average is the expectation value of the cost, and it is the number your classical optimizer is trying to improve. Feed it to COBYLA, Nelder-Mead, gradient descent, or whatever black-box optimizer you like, get back a new set of γ and β values, and run the circuit again.

The quantum computer, in this arrangement, is a sampler. It produces candidate solutions from a distribution you can shape but cannot inspect directly. The classical computer does the learning.

Worked example: Max-Cut

Max-Cut is the problem QAOA was introduced with, and it remains the standard demonstration. The encoding step is where the abstraction becomes concrete, so here it is in full.

The problem: given a graph, split the vertices into two groups so that the number of edges running between the groups is as large as possible. Each edge may carry a weight, in which case you maximise total crossing weight rather than a count. Assign each vertex a bit, 0 or 1, indicating its group. An edge counts toward the cut exactly when its two endpoints have different bits.

Easy to state, NP-hard in general, and each vertex is already a binary variable. It maps onto qubits with no encoding overhead at all: one vertex, one qubit.

Building the cost operator

For a single edge between vertices i and j with weight w_ij, define a variable z_i for each vertex taking the value +1 or -1 rather than 0 or 1. This sign convention makes the arithmetic clean. Then:

C_ij = (w_ij / 2)(1 – z_i · z_j)

Check the two cases. If both endpoints are in the same group, z_i and z_j have the same sign, their product is +1, and the expression gives zero. If they are in different groups, the product is -1, and the expression gives w_ij. The edge contributes its weight exactly when it is cut. Sum over all edges and you have the total cut weight, which is the quantity you want as large as possible.

Now translate z_i into something a qubit understands. The Pauli Z operation returns +1 when a qubit reads 0 and -1 when it reads 1. That is precisely the ±1 variable we defined. Substituting:

H_C = Σ over edges (i,j) of (w_ij / 2)(I – Z_i · Z_j)

Here I is the identity operation, present so the expression evaluates to 0 for uncut edges and to w_ij for cut ones, matching the classical formula term for term. That is the cost Hamiltonian. It is the same objective function you would write in Python, rewritten in the operator notation the circuit consumes.

For the mixer, the Pauli X operation flips a qubit between 0 and 1, so H_M = Σ over all qubits of X_i is the standard choice. It lets any vertex move between groups.

What one layer does

Take a five-vertex graph. Apply Hadamard gates to all five qubits, giving you an equal superposition of all thirty-two possible partitions. Apply e^(-iγH_C). Because H_C evaluates to the cut score on each bitstring, this multiplies each partition by a phase proportional to how many edges that partition cuts. Partitions with high cut values now carry different phases from partitions with low cut values, but every partition is still equally likely to be measured.

Then apply e^(-iβΣX_i), which is a rotation of each qubit by angle β about the X axis. This is where the phases turn into probabilities. Partitions whose phases reinforce gain amplitude; partitions whose phases cancel lose it. Choose γ and β well and the good cuts come out heavy.

At the gate level, each edge term becomes a pair of CNOT gates with a single-qubit rotation between them, and the mixer becomes one X-rotation per qubit. The circuit depth is on the order of p times the number of edges in two-qubit gates, though edge terms acting on disjoint pairs can run in parallel where the hardware permits.

What one layer buys

Two parameters is not much control, and on a large graph a single layer will not find the optimum. It will beat random guessing, which is the relevant baseline. Farhi and colleagues proved that on 3-regular graphs, meaning graphs where every vertex has exactly three edges, p=1 QAOA guarantees a cut of at least 0.6924 times the optimum. The approximation ratio here is exactly what it sounds like: achieved score divided by optimal score.

That result briefly matched or exceeded the best known classical guarantee for that specific graph class. Classical researchers then improved their side, as they generally do. The episode is a pattern worth remembering: classical algorithms are not a stationary target, and a quantum result that wins on Tuesday can lose by Friday to a better rounding scheme in a classical approximation algorithm.

Increase p and you get more parameters and more chances for interference to concentrate probability on good partitions. In the limit of large p, QAOA can in principle reach the optimum. How fast p must grow with problem size to keep that promise is one of the open questions.

What else fits the template

The algorithm’s structure never changes. What changes between problems is H_C. Everything else, the Hadamards, the mixer, the loop, the classical optimizer, stays as it is.

This is possible because there is an established translation layer. A QUBO, or Quadratic Unconstrained Binary Optimization, is a way of writing an objective as a sum of terms involving one or two binary variables each. An Ising model is the same thing in the ±1 variable convention we used above; the two are interconvertible by simple substitution. Decades of work in operations research and statistical physics has already produced QUBO formulations for a long list of problems: graph colouring, maximum independent set, set cover, portfolio selection under cardinality constraints, job-shop scheduling, and travelling salesman, though the TSP encoding is expensive in qubits.

If your problem has a QUBO formulation, it has a cost Hamiltonian, and it can be fed to QAOA. That is the strongest practical thing about the algorithm: it is not one solver, it is a template with a wide input format.

Two caveats matter for anyone planning to try this. First, qubit cost varies enormously by encoding. Max-Cut needs one qubit per vertex. Travelling salesman in the standard encoding needs roughly n² qubits for n cities, which puts even a twelve-city instance out of reach of most current machines. Second, hard constraints do not encode cleanly. If your problem requires exactly k variables set to 1, the standard mixer will happily produce bitstrings that violate that, and you either add a penalty term to H_C, which wastes optimization effort on ruling out invalid answers, or you design a constraint-preserving mixer that only moves between valid states. The latter is better and harder.

Where the shape comes from

QAOA’s alternating structure didn’t come from nowhere. There is an older idea called the adiabatic algorithm: start a quantum system in the easily-prepared ground state of a simple Hamiltonian, then change the Hamiltonian slowly toward the one that encodes your problem. If you go slowly enough, the system stays in its ground state throughout and you finish holding the answer. The catch is “slowly enough”, which for hard problems can mean impractically long.

QAOA is what you get when you stop trying to be slow and smooth. Instead of a continuous sweep, you alternate between the two Hamiltonians in discrete bursts, and you let a classical optimizer decide how long each burst should be. Nothing guarantees this works, and it isn’t adiabatic in any strict sense. It just turns out that a short, jagged, well-tuned sequence often does most of what the long smooth one would have done, in a circuit shallow enough to run on hardware that exists.

That is why the algorithm’s depth is measured in layers rather than in time, and why p is the number you argue about.

Why the depth stays small

Present-day quantum processors are described as NISQ, for Noisy Intermediate-Scale Quantum: enough qubits to be interesting, not enough error correction to protect a long computation. Every gate introduces a small chance of error, and the errors compound. Vendors publish two-qubit gate error rates for each processor, and on current machines those rates are high enough that a QAOA circuit with several hundred two-qubit gates produces a noticeably corrupted distribution.

Connectivity makes this worse. Most superconducting chips let a qubit interact only with its immediate neighbours on the chip. Your problem graph almost certainly doesn’t match the chip’s wiring graph. The compiler bridges the gap by inserting SWAP gates, which move a qubit’s state to a neighbouring qubit so that two logically connected variables become physically adjacent. Each SWAP costs several two-qubit gates. A dense problem graph on a sparse chip can more than double your gate count before any useful work happens. Trapped-ion machines offer all-to-all connectivity and avoid this entirely, at the cost of much slower gates.

What this produces in practice is a ceiling on p. Adding layers improves the ideal circuit and degrades the real one, and somewhere the two cross. Google’s 2021 Sycamore experiment, published in Nature Physics (arXiv:2004.04197), is the clearest published illustration: on problem instances that matched the chip’s native connectivity, solution quality improved as they went from p=1 to p=3, which was a genuinely encouraging result, since it showed a quantum algorithm on real hardware getting better rather than worse with depth. On instances requiring heavy SWAP overhead, performance degraded as problems grew, though even circuits with several thousand gates still beat random guessing.

The Google team suggested a secondary use for the algorithm that has stuck: QAOA as a hardware benchmark. It exercises the full stack, many layers of two-qubit gates, a real compilation problem, a measurement-heavy readout loop, and produces a single number you can compare across machines.

Where it stops

Being clear about the limits isn’t pessimism, it is the only way to decide whether learning this is worth your time.

Nobody has beaten a classical solver with QAOA on a problem of practical size. Not once, on hardware. The demonstrations are small, the classical baseline solves the same instances in microseconds, and the point of the experiments is to learn how the algorithm behaves rather than to win a race. Anyone telling you otherwise is selling something.

Finding good parameters is itself hard. The 2p angles have to come from somewhere, and the space they live in is high-dimensional, non-convex, and full of local optima. Choosing them optimally in the general case is NP-hard, which is an uncomfortable thing to discover inside your solver for an NP-hard problem. Two workarounds have real traction. Parameter concentration is the empirical observation that, within a family of similar problem instances, the optimal angles do not vary much with instance size. That permits parameter transfer: optimize the angles on a small instance you can afford to tune carefully, then reuse them on larger instances as a starting point, or directly. Both effects show up most reliably at p=1, in simulation and in small hardware runs.

Flat regions can stall the optimizer. A barren plateau is a region of parameter space where the gradient of the cost is close to zero across a large volume, so the optimizer has no direction to move in. It afflicts variational quantum algorithms generally. QAOA’s rigid structure gives it some protection at low depth, and it does not suffer as badly as an unstructured deep circuit would, but the protection weakens as p grows. Noise makes it worse: hardware noise flattens the cost surface independently of anything in the algorithm’s design.

Measurement cost is a real budget line. Every parameter update needs a fresh expectation estimate, and every estimate needs thousands of shots. A single QAOA run is not one circuit execution, it is tens of thousands of them across hundreds of optimizer iterations. On metered cloud quantum hardware, this is the cost that surprises people.

Theory suggests some hard instances may resist shallow QAOA. The Overlap Gap Property, studied by David Gamarnik, is a structural feature of certain random optimization problems: the near-optimal solutions cluster into groups that are far apart from each other, with nothing in between. Chou, Love, Sandhu and Shi showed that local algorithms, including fixed-depth QAOA, struggle on such solution spaces, and that depth may need to grow with problem size to overcome it. Growing depth is exactly what NISQ hardware cannot afford. Whether this rules out an advantage or merely relocates it to error-corrected machines is unsettled.

Against all that: the research is active and the variants are getting better. Warm-start QAOA initialises the circuit from a classical heuristic’s solution rather than a uniform superposition, so the quantum part refines instead of searching from scratch. Recursive QAOA runs the algorithm, fixes the variables it is most confident about, shrinks the problem, and runs again. Multi-angle QAOA gives each term in the cost Hamiltonian its own angle, trading a harder classical optimization for a more expressive circuit. Constraint-preserving mixers handle problems where the standard mixer wastes effort on invalid states.

Why a developer should still learn it

QAOA is a well-understood algorithm without a demonstrated advantage, running on hardware not yet good enough to settle the question. That’s a strange thing to recommend studying. Three reasons it is worth the time anyway.

It is the cheapest complete tour of quantum algorithm design available. Superposition, phase, interference, measurement statistics, and a hybrid classical loop, all in a circuit you can write out on one page and simulate on a laptop for a dozen qubits. Understanding QAOA properly means understanding most of the mental furniture the rest of the field uses.

The encoding skill transfers regardless of which algorithm wins. Turning a business problem into a QUBO, counting the qubits it costs, and recognising when an encoding is wasteful is the part of the job that doesn’t depend on the hardware or the algorithm. Quantum annealers take the same input. So do several algorithms that are not QAOA.

And it is the standard testbed. When a hardware vendor publishes a new processor result on optimization, it is usually a QAOA result, and reading those papers critically requires knowing what p means, why the connectivity mattered, and what the shot count was hiding. That skill has value now, whatever happens to the algorithm.

Where to go next

If you want to go from reading about QAOA to building and running one, the natural next step is hands-on circuit construction: encoding a problem, laying out the layers, running the hybrid loop against a simulator, and then against real hardware with all the compilation and noise consequences that brings.

Quantum Academy’s programming and algorithms track covers exactly that progression, from gate-level circuit construction through the variational algorithms and their classical optimization loops, aimed at developers rather than physicists. You can review the full program list and the prerequisites for each at quantumacademy.com/.

For deeper technical treatment of quantum algorithms and where they sit against classical baselines, PostQuantum.com carries the longer-form analysis. And if you are weighing whether quantum software development is a direction worth taking, QuantumCareers.com maps the roles and the skills each one actually requires.