Quantum Approximate Optimization Algorithm (QAOA)

Overview

The quantum approximate optimization algorithm, or QAOA, is a hybrid method for finding good approximate solutions to combinatorial optimization problems such as MaxCut, scheduling, and routing. It alternates between two simple operations, one that encodes the cost of a candidate solution and one that mixes candidates, and a classical optimizer tunes the strength of each operation.

Like VQE it is designed for noisy near-term devices, and its depth is controlled by a single integer p, the number of alternating layers. With p equal to 1 the circuit is very shallow, and as p grows the algorithm can approach the exact optimum, in the limit connecting to adiabatic quantum computation.

The problem it solves

Approximately solving optimization problems like Max-Cut, scheduling, or routing — problems with many possible solutions and no easy way to find the best one.

History and background

Farhi, Goldstone, and Gutmann posted the algorithm in November 2014. They showed that on MaxCut for three-regular graphs, the p = 1 circuit guarantees an approximation ratio of at least 0.6924. That was weaker than the 0.878 ratio from the classical Goemans-Williamson algorithm, but they also proved that classical algorithms could not easily simulate the circuit, which generated interest.

Later work refined the picture. In 2019 Hadfield and colleagues generalized the method into the quantum alternating operator ansatz, allowing constraint-preserving mixers. In 2020 Farhi and collaborators proved that low-depth QAOA cannot beat classical algorithms on some random problems, because of the overlap gap property. Google implemented QAOA on up to 23 qubits in 2021, and in 2024 researchers at JPMorgan Chase and Quantinuum reported evidence of a scaling advantage over some classical solvers on a hard problem called low autocorrelation binary sequences, a claim that is still being examined.

How it works

Alternates between quantum operations that explore the solution space and classical optimization that tunes parameters, gradually converging on better solutions.

Encode the problem as a cost function over bit strings, and associate a Hamiltonian H sub C whose energy on each basis state equals the cost. Start in an equal superposition of all bit strings, which is the lowest-energy state of a simple mixing Hamiltonian H sub B, typically a sum of Pauli X operators.

Then alternate two kinds of evolution: apply e to the minus i gamma times H sub C, which puts a phase on each bit string that depends on its cost, and apply e to the minus i beta times H sub B, which mixes amplitude between bit strings that differ by one bit. After p rounds the state is a function of 2p angles. The expected cost is measured, and a classical optimizer chooses angles that minimize it.

The intuition comes from adiabatic computing: a slow, smooth change from the mixer to the cost Hamiltonian ends in the optimal solution. QAOA replaces the slow ramp with a few large discrete steps whose sizes are optimized, which makes the circuit shorter at the cost of an optimization problem over the angles.

Step by step

1. Express the problem as minimizing a cost function over n bits, and convert it to a Hamiltonian H sub C acting on n qubits, often a sum of ZZ terms for graph problems.
2. Prepare all qubits in the equal superposition state by applying Hadamard gates.
3. Apply the cost layer e to the minus i gamma sub k H sub C, which usually consists of two-qubit ZZ rotations along the edges of the graph.
4. Apply the mixer layer e to the minus i beta sub k H sub B, which is a single-qubit X rotation on each qubit.
5. Repeat steps 3 and 4 for p layers with parameters gamma sub 1 through gamma sub p and beta sub 1 through beta sub p.
6. Measure the qubits to obtain bit strings, compute their costs, and estimate the average cost. Use a classical optimizer to update the 2p parameters, and repeat until convergence.
7. Report the best bit string seen across all measurements.

A worked example

Consider MaxCut on a triangle graph with three nodes. The best cut separates one node from the other two and cuts two edges. QAOA with p = 1 assigns two parameters, gamma and beta. After preparing the state, applying one cost layer and one mixer layer, the expected number of cut edges can be computed for each choice of the angles, and the best choice yields an expected cut slightly above the average of 1.5 edges, with the best bit strings corresponding to the optimal cut sampled more often than chance.

For larger graphs, each increase in p adds a pair of angles and typically improves the expected cut. The cost of the extra depth is more noise on hardware, so the best p on a real device is a balance between expressiveness and error.

Complexity and resources

What hardware it needs

• Qubits connected according to the problem graph, or swap gates to emulate the connectivity, which increases depth.
• Moderate gate fidelity, with error mitigation, because depth grows with p.
• Thousands of shots per parameter setting for energy estimation.

Applications

• MaxCut, graph partitioning, and independent set problems.
• Scheduling, portfolio optimization, and routing formulated as quadratic unconstrained binary optimization.
• Benchmarking hardware on structured circuits that resemble real workloads.
• Exploring quantum advantage candidates for hard combinatorial problems.

Limitations and caveats

• A proven advantage over the best classical algorithms has not been established, and some theory results limit low-depth performance.
• The parameter landscape is rough and optimization is hard, with barren plateaus at larger sizes.
• Noise limits the useful depth, and swap overhead on sparse hardware increases circuit size.
• Constrained problems need special mixers or penalty terms that complicate implementation.

Common misconceptions

• QAOA is not guaranteed to find the optimal solution. It finds good approximate solutions with some probability.
• It does not solve NP-hard problems in polynomial time. No quantum algorithm is known to do that.
• A good result on a 20-node graph does not imply advantage, since classical solvers handle much larger graphs.

How it compares

• Quantum annealing runs a continuous analog protocol on specialized hardware, while QAOA is a gate-based, discretized version.
• VQE uses the same hybrid loop for energy minimization instead of combinatorial optimization.
• Grover-based search offers a provable quadratic speedup but needs deep circuits, whereas QAOA offers heuristic improvements with shallow circuits.

Real-world impact

Explored for portfolio optimization, logistics routing, and scheduling problems; whether it offers genuine advantage over the best classical heuristics remains an active research question.

Why it matters

QAOA is the leading gate-based candidate for near-term quantum advantage in optimization, a field with large commercial interest. Its structure, which is simple enough to run today yet rich enough to resist easy simulation, makes it the standard benchmark for optimization on quantum hardware.

It is also a good test of claims. Studying QAOA teaches readers to ask about classical baselines, scaling with problem size, and whether advertised speedups survive better classical algorithms.

Frequently asked questions

Keep learning

• Related algorithm: Quantum Annealing
• Related algorithm: Variational Quantum Eigensolver (VQE)
• Related algorithm: Max-Cut with Quantum Algorithms (QAOA and Quantum Max-Cut)
• Related algorithm: Adiabatic Quantum Computation

This page is written for educational purposes. Complexity statements describe the best known results at the time of review (September 30, 2026), and research in this area moves quickly, so check recent papers before relying on a specific bound.

← Back to Algorithms Database