Scaling Advantage in Approximate Optimization with Quantum Annealing

Quantum annealers have scaled up in recent years to tackle increasingly larger and more highly connected discrete optimization and quantum simulation problems. We present evidence for a quantum annealing scaling advantage in approximate optimization using the D-Wave Advantage quantum processing unit (QPU). The advantage is relative to the top classical heuristic algorithm: parallel tempering with isoenergetic cluster moves (PT-ICM) on a family of nonplanar 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™ QPU to yield over 1,300 error-suppressed logical qubits on a degree-5 interaction graph. Random spin-glass instances on this graph are benchmarked under their time-to-epsilon, a generalization of the time-to-solution metric for low-energy states, with quantum annealing exhibiting a scaling advantage over PT-ICM at sampling low-energy states with an optimality gap of at least 1.0%. Finally, we discuss the performance and scaling of natively connected spin-glass problems on the more recent D-Wave Advantage2™ QPU.