Quantum Approximate Optimization

Combinatorial optimization is the task of finding the configuration of discrete variables that minimizes (or maximizes) some objective function. Problems in this class, scheduling, graph partitioning, portfolio optimization, protein folding, logistics, appear throughout industry and science. Many are NP-hard, meaning no known classical algorithm solves all instances efficiently. Quantum approximate optimization is the study of hybrid quantum-classical algorithms that use parameterized quantum circuits to search for high-quality approximate solutions, aiming to harness quantum effects without requiring the overhead of full fault-tolerant computation.

The core idea

An optimization problem over $n$ binary variables can be encoded as a cost Hamiltonian $H_C$, a diagonal operator in the computational basis whose eigenvalues equal the cost function values. The ground state of $H_C$ is the optimal solution. Finding that ground state exactly is as hard as solving the original problem, but approximating it, finding a state whose expectation value $\langle H_C \rangle$ is close to the minimum, may be achievable with a shallow quantum circuit.

Quantum approximate optimization algorithms construct an ansatz state by alternating layers of two types of operators applied to an equal superposition:

1. Phase separation: $e^{-i\gamma H_C}$, which imprints phases on basis states proportional to their cost.
2. Mixing: $e^{-i\beta H_B}$, where $H_B$ is a mixing Hamiltonian (typically a sum of Pauli X operators) that spreads amplitude between basis states.

After $p$ rounds of alternation, the parameters $(\boldsymbol{\gamma}, \boldsymbol{\beta})$ are optimized classically to minimize the expected cost. The resulting state has amplitude concentrated on low-cost configurations, which are identified by measuring the circuit repeatedly.

Relationship to adiabatic quantum computing

Quantum approximate optimization with $p$ layers is a Trotterized approximation to adiabatic quantum computing: as $p \to \infty$ and the parameters are chosen to follow an adiabatic schedule, the algorithm converges to the exact ground state. Finite-$p$ algorithms therefore offer a spectrum of circuits from shallow (low fidelity, short coherence demand, NISQ-compatible) to deep (high fidelity, demanding fault-tolerant hardware). This tunability is one of the key practical advantages of the approach.

Performance guarantees and limitations

For the simplest case, $p = 1$ on the MaxCut problem on 3-regular graphs, Farhi, Goldstone, and Gutmann proved an approximation ratio of at least 0.6924, meaning the algorithm is guaranteed to find a cut with at least 69.24% of the maximum possible cut weight. Classical algorithms such as Goemans-Williamson achieve 0.878 on the same problem. Whether quantum approximate optimization can match or surpass the best classical approximation algorithms at any level of $p$ is an open research question.

At shallow depths ($p$ small), the circuit can only correlate qubits within a distance of $p$ hops in the problem graph, limiting its ability to exploit global structure. This locality constraint explains why shallow quantum approximate optimization can be outperformed by problem-specific classical heuristics on instances with long-range structure. As $p$ grows, the quantum advantage case becomes more plausible, but so does the circuit depth and the coherence requirement.

NISQ-era context

Quantum approximate optimization was one of the primary motivations for building NISQ devices. The circuits are shallow enough to run before decoherence dominates, the variational loop offloads exponentially hard optimization to a classical optimizer, and the output is a probability distribution over bit strings that can be sampled without quantum read-out of the full state. On current hardware with 50-500 qubits, researchers have demonstrated the algorithm on problems with tens of variables, but achieving solution quality competitive with classical solvers on practically sized problems has proven difficult due to barren plateau landscapes, noise-induced gradient corruption, and the local-optima problem in the classical parameter optimization.

Applications beyond MaxCut

The quantum approximate optimization framework extends to any optimization problem that can be encoded as a quadratic unconstrained binary optimization (QUBO) or as an Ising model Hamiltonian. Applications include portfolio optimization (encoding asset selection as a binary problem with a quadratic covariance term), vehicle routing (encoding routes as binary variables with constraint Hamiltonians), and satisfiability problems. Constraint satisfaction requires augmenting $H_C$ with penalty terms or using constraint-preserving mixing operators, both active areas of algorithm design.

Why it matters for learners

Quantum approximate optimization is the clearest concrete example of a near-term quantum algorithm with a well-defined classical problem to solve and a parameterized quantum circuit to execute. Studying it teaches the variational quantum algorithm workflow (circuit ansatz, parameter optimization, measurement), the relationship between quantum circuit depth and solution quality, and the practical challenges of running quantum algorithms on noisy hardware. It also illustrates why “quantum advantage” claims require careful qualification: the relevant comparison is not against exponential brute force, but against the best known classical approximation algorithm for the specific problem class.

See also

• QAOA
• Variational Quantum Eigensolver
• Adiabatic Quantum Computing
• Quantum Natural Gradient
• Quantum Speedup
• NISQ