In a major milestone for quantum computing, researchers Humberto Muñoz-Bauza and Daniel Lidar have demonstrated the first clear scaling advantage of quantum annealing in approximate optimization—a critical task in fields like logistics, finance, and machine learning. Published in Physical Review Letters, the study reveals that quantum annealing can outperform the best-known classical heuristic method in solving complex optimization problems, provided certain conditions are met.

The Challenge: Optimization at Scale

Many real-world problems—from routing delivery trucks to portfolio optimization—boil down to finding the best configuration among a massive number of possibilities. These problems often involve “spin glasses,” which are notoriously difficult to solve. Quantum annealing, a method that leverages quantum mechanics to search for low-energy (optimal) configurations, has long been a candidate for outperforming classical algorithms in these scenarios.

But until now, no study had definitively shown a scaling advantage—meaning that as problem size increases, quantum annealers solve problems more efficiently than classical methods in a measurable way.

Quantum Annealing Correction (QAC): A Key Innovation

The study’s breakthrough lies in the use of Quantum Annealing Correction (QAC), a method that applies error suppression by embedding error-correcting codes directly into the quantum annealer's architecture. QAC leverages a majority-voting scheme among physical qubits to protect logical qubit states, effectively reducing the impact of hardware noise and analog errors.

Using QAC, the researchers implemented a highly error-tolerant system on the D-Wave Advantage quantum annealer. They tested it on large-scale spin-glass problems using up to 1,322 logical, error-corrected qubits—the largest such demonstration to date.

The Benchmark: Outperforming the Best Classical Heuristic

The quantum system was pitted against parallel tempering with isoenergetic cluster moves (PT-ICM), a top-tier classical algorithm. The key metric was time-to-epsilon (TTε), which measures how quickly a solver finds solutions within a certain percentage (ε) of the optimal answer.

• At an optimality gap of 1% or higher, quantum annealing with QAC consistently outscaled PT-ICM, providing faster approximate solutions as problem sizes grew.

• Even without error correction (a method called C3), quantum annealers showed some advantage, though QAC clearly performed best.

This scaling advantage was not just a one-time performance win—it persisted across varying problem sizes and noise levels, and the improvement grew stronger with larger optimality gaps.

Key Findings

• QAC shows better scaling than classical methods at approximate solutions (ε ≥ 1.0%), which could translate to real-world speedups in tasks like machine learning or supply chain management.

• Error correction is critical—without QAC, performance drops noticeably.

• Fast annealing schedules (coherent regimes) do not necessarily improve scaling and may be more susceptible to thermal errors.

• Quantum tunneling is suspected to play a role in this speedup, offering a potential mechanism behind the improved performance.

Why This Matters

This research marks a turning point in quantum optimization, providing the first evidence that quantum annealers can surpass classical algorithms not just in runtime but in how they scale with increasing problem complexity.

While this is an early-stage result confined to synthetic spin-glass problems, it opens the door to applying quantum advantage in real-world use cases, particularly where high-precision, approximate answers are acceptable or even preferred.

What’s Next?

The next challenge is to:

• Extend these findings to more complex, application-specific problems with dense connectivity.

• Optimize hardware schedules and error-suppression techniques for broader use.

• Continue refining metrics like TTε to evaluate future quantum and hybrid solvers.

Bottom Line:
Quantum computing has taken a significant leap from theory to tangible performance gains. Thanks to innovations like QAC and improved benchmarking, we now have credible evidence that quantum annealing isn’t just a niche tool—but a competitive and scalable approach for solving some of the world’s hardest computational problems.

Citation: Muñoz-Bauza, H., & Lidar, D. (2025). Scaling Advantage in Approximate Optimization with Quantum Annealing. Physical Review Letters, 134(16), 160601. https://doi.org/10.1103/PhysRevLett.134.160601