QAOA at 100 Qubits: Real Benchmarks from a Laptop CPU

QAOA, the Quantum Approximate Optimization Algorithm, is among the most widely run algorithms in quantum computing research and the standard testbed for claims about quantum optimization. One figure is worth stating plainly at the outset: a 100-qubit, depth-304 QAOA MaxCut circuit simulates in 5.9 seconds on a consumer laptop CPU, fully converged, with an accuracy statement attached.

No cluster and no GPU were involved. The GPU on the test machine was idle throughout.

What QAOA is

QAOA addresses combinatorial optimization by encoding the objective as a Hamiltonian whose ground state is the optimal solution, then preparing an approximation to that ground state with a fixed-depth circuit.

The construction alternates two operations. A cost layer applies exp(-i gamma H_C), where H_C is the problem Hamiltonian, phasing each basis state in proportion to its objective value. A mixer layer applies exp(-i beta H_B) with H_B the sum of X operators, driving transitions between basis states. Repeating this pair p times gives 2p variational parameters, tuned by a classical optimizer.

For MaxCut on a graph, H_C is a sum of ZZ terms over the edges, so the cost layer is a set of RZZ rotations and the mixer is an RX on every qubit. The p = 1 case has a known analytic performance guarantee on 3-regular graphs; beyond that the behaviour is studied numerically, which is why simulation carries the field.

Benchmark setup

The benchmark family is QAOA for MaxCut on ring graphs: n qubits, a layer of Hadamards, then p rounds of RZZ gates along the ring alternated with RX rotations. This is a canonical structured workload with meaningful entanglement, non-Clifford gates and realistic depth. At n = 100, p = 3, the circuit reaches 304 layers of depth as Qiskit counts it.

The engine is a matrix product state simulator built on the open-source quimb library, run at bond dimension 64 with a convergence check: every run is repeated at bond dimension 128 and the leading outcome probabilities compared.

Circuit                    Qubits  p   Wall time  Converged (deviation)
QAOA MaxCut ring             50    2   4.1 s      yes (0.0)
QAOA MaxCut ring             80    2   4.4 s      yes (0.0)
QAOA MaxCut ring            100    3   5.9 s      yes (0.0)
Exact reference (ansatz)     26    -   2.7 s      exact (ground truth)

The exact-reference row is the validation step. At sizes small enough for exact statevector simulation the approximate engine is required to agree with it, and does. A benchmark without such a row is measuring speed without establishing correctness.

Why the circuits compress

The reason a 100-qubit QAOA circuit is tractable is structural rather than incidental, and it generalises.

A ring graph is one-dimensional, so every RZZ gate acts between neighbours and the entanglement generated is local. Entanglement across any cut of the chain grows with the number of layers that have crossed it, which is bounded by p, so the required bond dimension grows with depth rather than with width. At p = 3 the state remains representable at bond dimension 64.

This has a consequence for how such results should be reported. The favourable case is low p on sparse, near-planar graphs. Dense graphs, or high p, produce entanglement that no bond dimension in reach can hold, and the same engine will report a wide bound rather than a fast answer. The 5.9-second figure is a statement about this circuit family, not a general claim about 100 qubits, and the distinction is developed in Tensor networks explained.

Interpreting the result

The result changes the economics of QAOA research. A 100-qubit, 1,000-shot QAOA job on a superconducting QPU costs roughly $0.725 in device fees before queue time, and returns results affected by two-qubit gate error rates near 1 percent across a depth-304 circuit, at which point the surviving signal is minimal. The equivalent simulation costs a fraction of a cent, returns a noise-free value, and carries a convergence record.

The comparison is more lopsided than the per-run figures suggest, because QAOA is a variational algorithm and one run is not the workload. Optimising 2p parameters takes hundreds of circuit evaluations. A 150-iteration SPSA run is 301 submissions, which is $352.29 on hardware and about thirty cents in simulation. The arithmetic is set out in What does it cost to rent a quantum computer?.

What this does not show

None of this makes QAOA on hardware pointless, and the honest statement of the position is narrower than either enthusiasts or sceptics usually give.

It relocates the interesting scientific question. Whether QAOA outperforms classical optimizers at problem sizes beyond classical simulation requires either substantially larger hardware or instances with entanglement dense enough that tensor-network methods stop converging. The second condition is detectable: the engine reports when its bound has widened past usefulness, and that report is the signal that a genuine hardware experiment is warranted.

It is also worth recording that classical approximation algorithms for MaxCut are strong. Goemans-Williamson guarantees a 0.878 approximation ratio in polynomial time, and QAOA at low p does not beat it on the instances where both have been compared. A quantum optimization result is interesting when it is measured against the best classical algorithm for the same problem, not against brute force.

Reproducing it

Every figure above states the circuit, the engine and the machine, so the run is specified precisely enough to be set up again rather than taken on trust. Each accuracy statement is exported as a public certificate that resolves without an account, and the validation data behind the convergence protocol is published with the protocol paper.

The circuit family is a dozen lines of Qiskit, and the useful exercise is to run it at increasing p and watch the reported deviation move off zero. The point at which it does is the point at which the method's assumptions stop holding, and knowing where that boundary sits for your own problem class is worth more than any single benchmark figure.