  Quantum annealing is a heuristic optimization algorithm that exploits quantum
evolution to approximately find lowest energy states. Quantum annealers have
scaled up in recent years to tackle increasingly larger and more highly
connected discrete optimization and quantum simulation problems. Nevertheless,
despite numerous attempts, a computational quantum advantage in exact
optimization using quantum annealing hardware has so far remained elusive.
Here, we present evidence for a quantum annealing scaling advantage in
approximate optimization. The advantage is relative to the top classical
heuristic algorithm: parallel tempering with isoenergetic cluster moves
(PT-ICM). The setting is a family of 2D spin-glass problems with high-precision
spin-spin interactions. To achieve this advantage, we implement quantum
annealing correction (QAC): an embedding of a bit-flip error-correcting code
with energy penalties that leverages the properties of the D-Wave Advantage
quantum annealer to yield over 1,300 error-suppressed logical qubits on a
degree-5 interaction graph. We generate random spin-glass instances on this
graph and benchmark their time-to-epsilon, a generalization of the
time-to-solution metric for low-energy states. We demonstrate that with QAC,
quantum annealing exhibits a scaling advantage over PT-ICM at sampling low
energy states with an optimality gap of at least 1.0%. This amounts to the
first demonstration of an algorithmic quantum speedup in approximate
optimization.
