QAOA vs Classical Heuristics

QAOA is a promising algorithm for combinatorial optimization, but its true competitive position is still being established. To decide when — and whether — to use it, you need to understand what classical heuristics already achieve and where quantum approaches might improve on them.

The classical baseline is strong

Combinatorial optimization has been studied for decades. For many NP-hard problems, classical heuristics deliver high-quality solutions extremely fast.

Simulated Annealing (SA) accepts moves that increase cost with probability $\exp(-\Delta C / T)$ , where $T$ is a "temperature" that decreases over time. This allows the algorithm to escape local minima and converge toward a good global solution without ever constructing a quantum circuit.

Greedy local search is often even simpler: repeatedly move to a better neighboring solution until no neighbor improves the cost. For Max-Cut on random 3-regular graphs, a simple greedy algorithm achieves an approximation ratio of at least $1/2$ in linear time.

Semi-definite programming (SDP) relaxations provide the best known polynomial-time guarantee for Max-Cut: the Goemans–Williamson algorithm achieves an approximation ratio of approximately $0.878$ for the general case — a result conditional on the Unique Games Conjecture not being improvable.

What QAOA guarantees

For $p = 1$ , Farhi et al. (arXiv:1411.4028) derive the exact expected cut fraction on unweighted 3-regular graphs by tracing through the one-layer circuit analytically. Each edge contribution depends only on its immediate neighborhood, and after summing over all edges the result is

F_1(\gamma,\beta) \;=\; \frac{1}{2} + \frac{1}{2}\sin(4\beta)\sin(\gamma)\cos^2(\gamma),

Optimizing over $(\gamma, \beta)$ yields the bound $\alpha_1 \geq 0.6924$ — beating random ( $0.5$ ) but below the Goemans–Williamson bound of $\approx 0.878$ .

As $p \to \infty$ the QAOA state converges to the ground state of the cost Hamiltonian, so $\alpha_p \to 1$ in the limit. The open question is: how does the rate of convergence compare to classical algorithms, and at what problem sizes and circuit depths does a quantum device win in practice?

The parameter optimization problem

QAOA is a variational algorithm: the angles $(\gamma_1, \beta_1, \ldots, \gamma_p, \beta_p)$ must be optimized classically by evaluating $\langle C \rangle$ on the quantum device for many angle candidates. This creates a feedback loop with two costs:

Quantum cost: each evaluation of $\langle C \rangle$ requires many shots (typically $10^3$ – $10^4$ ) to reduce sampling noise.
Classical cost: gradient-based or black-box optimizers may need hundreds to thousands of objective evaluations to converge in $2p$ dimensions.

Classical heuristics have no such overhead — they run a single pass over the problem instance.

The barren plateau problem

For deep circuits (large $p$ or many qubits), gradients of the objective landscape can become exponentially small in the number of qubits. This is known as the barren plateau phenomenon. In a barren plateau region,

\mathrm{Var}\!\left[\frac{\partial \langle C \rangle}{\partial \theta_k}\right] \;\sim\; 2^{-n},

so an exponential number of shots is needed just to estimate the gradient. Classical optimizers like SA do not suffer from an analogous exponential suppression of search signals.

Where QAOA may have an edge

Despite these challenges, QAOA retains theoretical and practical interest for several reasons:

Structured problems: For highly constrained problems with specific Hamiltonian structure, problem-specific angle schedules (without variational loops) can be precomputed, eliminating the optimization overhead.
Quantum-native encodings: Some problems encode more naturally as quantum Hamiltonians than as classical bit strings, potentially making quantum sampling more efficient than classical.
Fault-tolerant regime: On future fault-tolerant hardware, deep QAOA circuits become accessible, and the $p \to \infty$ convergence guarantee may translate to asymptotic advantage.
NISQ demonstrations: Even today, QAOA serves as a benchmark for near-term devices, and running it reveals noise thresholds and error patterns that guide hardware improvement.

A direct comparison summary

| Criterion | QAOA ( $p$ small) | Simulated Annealing | Goemans–Williamson | |---|---|---|---| | Max-Cut ratio (3-reg.) | $\geq 0.6924$ ( $p=1$ ) | $\sim 0.9$ (empirical) | $\geq 0.878$ (proven) | | Complexity per run | $O(p \cdot n)$ circuit depth | $O(n \cdot T_{\max})$ | $O(n^3)$ (SDP) | | Optimization overhead | Yes (variational) | No | No | | Scalability on NISQ | Limited by noise | Runs on any CPU | Runs on any CPU | | Asymptotic guarantee | Yes ( $p \to \infty$ ) | Heuristic only | Yes (poly-time) |

Reading the landscape

The most honest conclusion is that the quantum-classical competition is still open. QAOA is best understood today as a proof-of-concept architecture: it shows that quantum computers can formulate and partially solve optimization problems, and it provides a concrete target for hardware benchmarking. For practitioners, this means:

Establish a strong classical baseline (SA, greedy, SDP) before running QAOA.
Measure solution quality per unit time, not just approximation ratio.
Compare at realistic noise levels, not idealized statevector simulations.

As quantum hardware matures and fault-tolerant operation becomes possible, the comparison will be revisited — and the outcome may shift.