Evidence for quantum optimization advantage

Short answer: Published studies give a mixed picture on quantum advantage for optimization. A paper comparing QAOA with the classical solvers Gurobi and MQLib on MaxCut finds that classical heuristics are hard to beat on large 3-regular graphs, while a numerical study on the LABS problem reports better runtime scaling than exact classical solvers in noiseless simulations of up to 40 qubits. Hardware results are limited to small experiments.

Classical Solvers and MaxCut Constraints

Researchers comparing the Quantum Approximate Optimization Algorithm (QAOA) with classical solvers Gurobi and MQLib on 3-regular graphs found that classical heuristics produce high-quality approximate solutions in linear time complexity. To match this quality for large graph sizes, the authors say a quantum device must support depth p greater than 11. They also report potential for advantage on hundreds of qubits at moderate depth with a sampling frequency of 10 kHz. They report that multi-shot QAOA with depth up to 11 does not scale with graph size, and say these results limit achieving quantum advantage for QAOA MaxCut on 3-regular graphs. The authors note that other problems, such as different graphs, weighted MaxCut or 3-SAT, may be better suited for demonstrating advantage on current hardware.

Scaling Behavior in Intractable Problems

A separate numerical investigation focused on the low autocorrelation binary sequences (LABS) problem, which is classically intractable even for moderately sized instances. Noiseless simulations with up to 40 qubits showed that the runtime of QAOA with fixed parameters scales better than branch-and-bound solvers, which are state-of-the-art exact solvers for LABS. When QAOA is combined with quantum minimum finding, it exhibits the best empirical scaling of any algorithm for this specific problem. The authors say this supports the utility of QAOA as an algorithmic component for quantum speedups, and that the simulations are noiseless. The simulations were enabled by custom GPU simulators executed on supercomputers, allowing for precise evaluation of scaling behavior without noise.

Reachability Deficits and Problem Density

Research into the fundamental limitations of QAOA revealed strong dependence on the constraint-to-variable ratio, or problem density. This density places a limiting restriction on the algorithm’s capacity to minimize the objective function. These reachability deficits persist even in the absence of barren plateaus and are distinct from previously reported level-1 QAOA limitations. For 3-SAT instances, the average overlap required to achieve a high-quality solution increases with clause density. The minimum depth required to achieve an average overlap of 0.95 grows as the problem becomes denser. The authors describe these findings as among the first to determine strong limitations on variational quantum approximate optimization.

Experimental Progress and Simulation Methods

Experimental progress has been demonstrated in executing QAOA for the LABS problem using an algorithm-specific error detection scheme on Quantinuum trapped-ion processors. The authors call this experimental progress. The scaling claims for larger sizes rest on noiseless simulations. The simulations used to establish scaling advantages rely on exact simulations of fixed schedules, which are computationally intensive but necessary to isolate algorithmic performance from hardware noise. The hardware work covers small instances, and the papers do not report the simulated scaling advantage on hardware at larger sizes.

FAQ

Does QAOA currently outperform classical solvers on MaxCut?

Not on the 3-regular graphs studied. The authors say classical heuristics give high-quality approximate solutions in linear time, and matching them on large graphs needs depth p above 11.

Is quantum advantage proven for all optimization problems?

No. The results depend on the problem. QAOA shows better scaling on LABS in noiseless simulation, but a separate paper reports reachability deficits that grow with problem density, and the MaxCut comparison limits advantage on large 3-regular graphs.

What role does problem density play in QAOA performance?

Problem density, defined by the constraint-to-variable ratio, creates reachability deficits. Higher density limits the algorithm’s ability to minimize the objective function, requiring greater circuit depth to achieve acceptable solution quality.

Have these scaling advantages been validated on hardware?

Experimental progress has been shown for small LABS instances using error detection on trapped-ion processors. However, the papers do not report the simulated scaling advantage on hardware for larger problems.

Are these results indicative of commercial deployment?

No. The papers are numerical studies and small experiments. None reports a deployed optimization advantage.