One qubit and a few springs: How a strange equivalence unlocks quantum speedups for real-world optimization

Some problems with enormous solution spaces are deceptively easy: sorting a million items means choosing among a staggering number of permutations, yet efficient algorithms handle it in a fraction of a second. Combinatorial optimization is fundamentally different. When a bank constructs a portfolio from thousands of assets, or a logistics company routes 10,000 packages across 500 trucks, the variables are so tightly coupled that improving one part of a solution can worsen another. No known algorithm can reliably navigate to the optimum without paying a steep computational price. From telecoms designing networks, to manufacturers scheduling factory floors, to hospitals assigning staff to shifts, organizations across industries settle for "good enough" because the best answer remains, after decades of research, prohibitively expensive to find.

For small instances, a computer can simply try every option. But as the number of variables grows, exhaustive search quickly becomes impossible, and classical algorithms face a stubborn tradeoff: improving solution quality demands disproportionately more computation. In a new joint paper with Argonne National Laboratory, accepted in Physical Review Letters, we present evidence that quantum algorithms may break through this barrier.

The Quantum Approximate Optimization Algorithm (QAOA) is the leading candidate for realizing this advantage. Starting with a superposition of every possible solution, it works by repeatedly applying two quantum operations in alternating layers: one encodes the problem's objective, and the other explores the space of possible solutions. With each added layer, the algorithm searches more thoroughly, and its solution quality only improves. But a central question has remained: does QAOA outperform the best classical algorithms as problems grow large?

Answering this requires studying QAOA's behavior on large problems with deep circuits, a regime too costly to simulate on classical computers and beyond the reach of current quantum hardware. We established a surprising duality that made this calculation possible.

We focused on a well-studied problem called the Sherrington-Kirkpatrick (SK) model. The SK model is a type of disordered system with random interactions between every pair of variables. Many real-world business problems have similar interactions, from portfolio construction to network design. What makes the SK model especially powerful as a testing ground is that, in the limit of infinitely large problem sizes, its optimal value is known exactly. This value, called the Parisi value, gave us a precise yardstick against which to measure QAOA.

We discovered a duality between the task of computing QAOA's performance on large instances of the SK model and the simulation a simple physical system: a single quantum bit (qubit) coupled to a set of quantum harmonic oscillators (think vibrating springs). By translating the problem into this "spin-boson" system, we replaced the exponentially costly calculation with a simulation that can be performed using a technique from many-body physics called matrix product states (MPS). Together, the mapping and the MPS simulation meant that the cost grew only modestly with circuit depth.

We provide the strongest evidence to date that QAOA efficiently solves the SK model in the average case. These findings were only possible because of the spin-boson simulation technique we developed, which overcame the computational barrier that had limited prior work. We remark that our technique lets us evaluate the expected solution quality of QAOA without running it end to end. Actually executing QAOA and sampling solutions still requires a quantum computer. What we have shown is that when such hardware becomes available, there is strong evidence it will outperform classical approaches on this class of problems.

Importantly, the mapping we discover is not limited to this single problem; it extends naturally to a broader class of optimization problems. As quantum hardware matures, these results point toward a future where quantum computers tackle the combinatorial challenges that businesses face every day.

For more details, see the full paper in Physical Review Letters: https://doi.org/10.1103/2w94-rymn. A preprint is available at https://arxiv.org/abs/2505.07929