Case Study: QAOA Against a Tuned Classical Heuristic

Executive Summary

The honest test of a heuristic is a head-to-head comparison at equal wall-clock against the best classical alternative on identical instances. QAOA is rarely subjected to it. Papers typically compare against brute force, against random sampling, or against no baseline at all.

This case study runs the comparison properly on MaxCut: same 24-node graphs, same time budget, QAOA at increasing $p$ against Goemans–Williamson and against a tuned tabu search. The result is a loss, and the shape of the loss — which resource runs out first, and why — is what transfers to other optimization proposals.

Skills applied

• Implementing QAOA for MaxCut and measuring approximation ratios (§20.7).
• Constructing a fair classical baseline (§20.14).
• Comparing at equal wall-clock rather than equal iteration count.
• Identifying the binding resource constraint.

Phase 1: The benchmark

Instances: 20 random 3-regular graphs on 24 nodes. 3-regular MaxCut is the standard QAOA benchmark and the case where theoretical bounds exist.

Metric: approximation ratio = (cut found) / (optimal cut). Optima computed exactly by branch-and-bound in under a second per instance.

Time budget: 60 seconds per instance per method.

Phase 2: The classical baselines

Goemans–Williamson. Solve the semidefinite relaxation, then randomly round the resulting vectors. Guarantees 0.878 in expectation.

import cvxpy as cp, numpy as np

def goemans_williamson(adj):
    n = adj.shape[0]
    X = cp.Variable((n, n), PSD=True)
    obj = cp.sum(cp.multiply(adj, 1 - X)) / 4
    prob = cp.Problem(cp.Maximize(obj), [cp.diag(X) == 1])
    prob.solve()
    L = np.linalg.cholesky(X.value + 1e-9 * np.eye(n))
    best = 0
    for _ in range(200):                        # random hyperplane rounding
        r = np.random.randn(n)
        cut = np.sign(L.T @ r)
        best = max(best, cut_value(adj, cut))
    return best

Runtime: ~1.8 s per instance including rounding.

Tabu search. Local search over single-node flips with a short-term memory forbidding recent moves.

Runtime: 60 s, as allotted.

Phase 3: QAOA

from qiskit.circuit.library import QAOAAnsatz
from qiskit.quantum_info import SparsePauliOp

def maxcut_hamiltonian(adj):
    n = adj.shape[0]
    terms = [("I"*i + "Z" + "I"*(j-i-1) + "Z" + "I"*(n-j-1), 0.5)
             for i in range(n) for j in range(i+1, n) if adj[i, j]]
    return SparsePauliOp.from_list(terms)

Run at $p = 1, 2, 3, 5, 8$, with parameters optimized by COBYLA warm-started from concentration-derived initial values, on a noiseless simulator first, then on hardware.

Phase 4: Results

Noiseless simulator (average approximation ratio over 20 instances):

Tabu search found the exact optimum on all 20 instances. GW at 0.923 beat every QAOA depth tested. QAOA at $p=8$, exceeding the time budget threefold, reached 0.862 — still below GW's guarantee.

On hardware ($\epsilon_{2q} = 7\times10^{-3}$, 24 qubits, SWAP overhead for the 3-regular graph on heavy-hex):

Ratio decreases with depth on hardware. Each additional layer adds more noise than optimization benefit. The hardware optimum is $p=1$, at 0.641 — worse than a random-plus-greedy classical baseline, and far below GW.

Phase 5: Which resource binds

Three constraints, and identifying the binding one matters:

Not qubit count. 24 qubits is unremarkable; devices have hundreds.

Not classical optimization. Parameter concentration means good $\gamma,\beta$ transfer between instances, so the classical loop is cheap.

Depth, decisively. Every 3-regular MaxCut layer needs one $ZZ$ rotation per edge — 36 edges → 36 $ZZ$ terms → 72 CNOTs per layer, before routing. On heavy-hex hardware SWAP networks roughly double it. So each layer costs ~120 two-qubit gates, and the fidelity budget at $7\times10^{-3}$ affords about 100 gates total.

Hardware affords $p \approx 1$. Theory needs $p \gtrsim 10$ to approach GW. That is an order of magnitude in depth, requiring roughly a 10× improvement in gate error before QAOA merely ties a 1994 classical algorithm on this problem.

The structural issue. QAOA's approximation ratio improves with $p$; its fidelity degrades with $p$. On current hardware the second effect dominates from $p=1$ onward, so the algorithm cannot be run in the regime where its theory predicts good performance.

Phase 6: What would change the verdict

Being fair to QAOA, the conditions under which this comparison would look different:

• 10–100× better gate fidelity, making $p \approx 10$–20 reachable.
• Problem structure matching hardware connectivity, eliminating SWAP overhead — which for MaxCut means graphs that are the coupling map, a severe restriction.
• An instance class where classical heuristics are weak. MaxCut is a poor showcase precisely because decades of classical work made it easy. Constraint families with no good classical heuristic would be a fairer test, though finding one that is also hardware-compatible is an open problem.
• A better theoretical bound at low $p$. Ongoing work; nothing yet changes the $p=1$ comparison.

Notably, none of these is "more qubits" — which is what hardware roadmaps mostly deliver.

Discussion Questions

1. Hardware approximation ratio fell with $p$ while simulator ratio rose. Explain and give the crossover condition.
2. Tabu search found every optimum in 60 s. Does that make MaxCut a bad benchmark, or QAOA a bad algorithm? Distinguish the claims.
3. Parameter concentration makes the classical loop cheap. Why does that not help?
4. Design the fairest possible QAOA benchmark. What would you need, and does such a problem class exist?

Your Turn: Extensions

• Reproduce this comparison on 16-node graphs; implement GW and tabu search yourself.
• Measure two-qubit gate count per QAOA layer for graphs of increasing density and confirm the depth scaling.
• Find, empirically, the gate error rate at which hardware ratio stops decreasing with $p$.
• Try a graph that matches your device's coupling map and quantify the SWAP saving.

Key Takeaways

• Compared fairly at equal wall-clock, QAOA lost to a 1994 classical algorithm and badly to tabu search, which found every optimum.
• On hardware the approximation ratio decreases with depth: added noise per layer exceeds the optimization gain from $p=1$ onward.
• The binding constraint is depth, not qubits or classical optimization — roughly 120 two-qubit gates per layer against a ~100-gate fidelity budget.
• Theory needs $p \gtrsim 10$ to match Goemans–Williamson; hardware affords $p \approx 1$, a 10× gate-fidelity gap.
• Benchmark against tuned classical heuristics at equal wall-clock on identical instances, or the comparison means nothing.