QAOA: Quantum Approximate Optimization Algorithm

QAOA is a hybrid quantum-classical algorithm designed to find approximate solutions to combinatorial optimization problems. It runs a parameterized quantum circuit on NISQ hardware and uses a classical optimizer to tune the parameters, targeting problems like MaxCut, portfolio optimization, and scheduling that are hard for classical solvers at large scale.

Two entangled qubits with orbital rings - the building block of QAOA quantum circuits

What is QAOA?

QAOA was introduced by Farhi, Goldstone, and Gutmann in 2014 as an algorithm for combinatorial optimization on near-term quantum hardware. The core idea is to encode an optimization problem as a cost Hamiltonian -- a quantum operator whose ground state (lowest-energy state) corresponds to the optimal solution -- and then use a parameterized quantum circuit to prepare an approximate ground state.

The algorithm is hybrid: the quantum computer prepares states and measures energies, while a classical optimizer tunes the circuit parameters to minimize the measured cost. This hybrid structure keeps the quantum circuits shallow enough to run on NISQ devices, at the cost of being approximate rather than exact.

How QAOA works

QAOA has a structured circuit architecture defined by a depth parameter p. Higher p means more circuit layers and a better approximation -- at the cost of deeper, noisier circuits.

1

Encode the problem as a cost Hamiltonian

The optimization problem is mapped to a cost Hamiltonian H_C whose lowest-energy state encodes the optimal solution. For MaxCut, this means assigning qubits to graph vertices and using ZZ interactions to represent the cut objective. The mapping is usually done via a QUBO (Quadratic Unconstrained Binary Optimization) formulation.

2

Prepare the initial state

All qubits are initialized in equal superposition using Hadamard gates. This state has equal probability of every possible assignment, giving QAOA a quantum starting point that explores the full solution space simultaneously.

3

Apply alternating cost and mixer unitaries

The QAOA circuit applies p rounds of two unitary operators: the cost unitary U(H_C, gamma) encodes the problem structure, and the mixer unitary U(H_B, beta) mixes the quantum state to explore the solution landscape. Each round has two tunable parameters (gamma and beta), giving 2p parameters total.

4

Classical optimizer loop

The quantum circuit is run and the expected value of the cost Hamiltonian is measured. A classical optimizer (COBYLA, SPSA, Nelder-Mead) updates the gamma and beta parameters to reduce the measured cost. This loop repeats until convergence. The final circuit parameters produce a quantum state that, when measured, yields a near-optimal solution with high probability.

QAOA applications

Any combinatorial optimization problem that can be expressed as a QUBO can be tackled with QAOA.

MaxCut

The canonical benchmark for QAOA. Given a graph, partition the vertices into two sets to maximize the number of edges crossing between them. This is NP-hard in general. QAOA can achieve a 0.6924 approximation ratio at p=1, matching classical algorithms for certain graph families.

Portfolio optimization

Choosing the optimal subset of assets to maximize expected return subject to risk constraints is a quadratic binary optimization problem. QAOA maps each asset to a qubit (hold or don't hold) and optimizes over the portfolio. See quantum finance courses for more.

Scheduling and routing

Job shop scheduling, vehicle routing, and network flow problems can be formulated as QUBOs and attacked with QAOA. These problems appear in logistics, manufacturing, and telecommunications, making them commercially relevant targets.

Satisfiability (SAT)

Boolean satisfiability problems -- finding assignments of variables that satisfy a conjunction of clauses -- map naturally to QAOA's cost Hamiltonian framework. 3-SAT is NP-complete and a common benchmark for testing whether QAOA can provide advantage over classical solvers.

QAOA vs classical optimization

It is important to be honest about where QAOA stands today. For most combinatorial optimization problems on current NISQ hardware, classical algorithms like simulated annealing, branch-and-bound, or semidefinite programming relaxations outperform QAOA implementations. The noise in current hardware limits p to small values (typically 1-3), which constrains approximation quality.

Theoretical results show QAOA performance improving with larger p, and some complexity-theoretic arguments suggest QAOA may eventually provide advantage for specific problem classes on fault-tolerant hardware. The honest current assessment: QAOA is a compelling research direction and an important algorithm to understand, but demonstrated quantum advantage over state-of-the-art classical optimization has not been achieved for practically relevant problem sizes.

Courses covering QAOA

Quantum computing courses that include QAOA in their curriculum, sorted by rating.

QAOA tutorials

Hands-on implementations in Qiskit and PennyLane, from MaxCut to portfolio optimization.

Frequently asked questions

What is QAOA used for?
QAOA (Quantum Approximate Optimization Algorithm) is designed for combinatorial optimization problems -- problems where you need to find the best assignment of discrete variables from an exponentially large search space. Current research applications include MaxCut (graph partitioning), portfolio optimization (choosing the optimal subset of assets), vehicle routing and scheduling, and satisfiability problems. QAOA produces approximate solutions, not guaranteed optimal ones, but for hard combinatorial problems an approximate solution is often sufficient.
How is QAOA different from VQE?
QAOA and VQE are both variational hybrid quantum-classical algorithms, but they target different problems. VQE is designed for quantum chemistry: it estimates the ground state energy of a molecular Hamiltonian. QAOA targets combinatorial optimization: it maps a discrete optimization problem to a cost Hamiltonian and finds an approximately optimal solution. QAOA has a fixed circuit structure (alternating cost and mixer unitaries) defined by the problem, while VQE's circuit (the ansatz) is more flexible and problem-dependent. Both use a classical optimizer to tune circuit parameters.
Does QAOA provide quantum advantage?
Not yet, on current hardware. Theoretical results suggest QAOA could outperform classical algorithms for specific problems at sufficient circuit depth (high p values), but on today's NISQ hardware, the noise and decoherence at large p makes this difficult to realize. For many combinatorial problems, classical algorithms like simulated annealing or branch-and-bound still outperform noisy QAOA implementations. The promise of QAOA is for fault-tolerant hardware where deep, low-noise circuits become feasible.
How do I implement QAOA in Qiskit?
Qiskit provides a QAOAAnsatz class and an optimization module (qiskit-optimization) with QAOA built in. The workflow is: define your optimization problem as a quadratic program, convert it to an Ising Hamiltonian using Qiskit's QuadraticProgramToQubo converter, build the QAOA circuit with the QAOAAnsatz, and run the variational loop with a classical optimizer like COBYLA or SPSA. The qaoa-maxcut-qiskit tutorial on this site walks through the full implementation for the MaxCut problem step by step.