Researchers Find New Way to Test QAOA at Massive Scale

What if you needed to assess a quantum optimization algorithm’s performance on a massive problem, but faced an impossible challenge: the problem is too large for any existing quantum computer and too complex for a classical supercomputer to simulate. You’re staring down a massive hurdle, can’t run the algorithm, or even model its behavior.

A team from JPMorganChase and Argonne National Laboratory devised a solution. Their findings, published in Physical Review Letters after peer review, are also available as a preprint on arXiv from May 2025 for those interested in the full derivation. They discovered that, under specific mathematical limits, a particular quantum algorithm simplifies into a much more manageable physics problem that is possible to simulate. This simplified problem became their testing ground.

The Algorithm Everyone’s Watching, and Why It’s Hard to Grade

The algorithm in question is QAOA, the Quantum Approximate Optimization Algorithm. It’s a leading candidate for demonstrating quantum advantage in optimization tasks, which is the kind of “finding the best arrangement among countless possibilities” problems prevalent in fields from logistics to finance. QAOA operates by applying layers of operations to qubits; deeper circuits, with more layers, are expected to yield better results.

For small problems, QAOA has been successfully implemented. The difficulty arises when trying to determine if QAOA remains superior for large problems, as this is the scale where quantum advantage would be truly impactful. Unfortunately, this is precisely the regime where testing is impossible. Current quantum hardware is too noisy and limited in size. Meanwhile, classical simulation of large, deep quantum circuits becomes prohibitively expensive, and that’s the very reason quantum computing is appealing in the first place.

Thus, the team’s core question wasn’t “does QAOA win?” but actually “how would we even find out?” Jeffrey Larson, a computational mathematician at Argonne and coauthor, described the collaboration’s goal:

“We are asking how far quantum optimization algorithms can go, and we need advanced classical simulation, strong optimization tools and high-performance computing to understand what is really possible.”

One Quantum Spin Doing the Work of Infinite Qubits

The team selected the Sherrington-Kirkpatrick (SK) model as their test problem. Say there was a network where every variable interacts with every other, with each connection representing a random, conflicting force. It’s a notoriously challenging optimization target that physicists have studied for decades. 

This extensive history is key: in the limit of infinite size, the optimal solution to the SK model is already known, providing a clear benchmark. This allows researchers to precisely measure how closely QAOA approaches a definitive value.

The researchers proved that a deep QAOA circuit applied to the SK model, when the system size approaches infinity, simplifies dramatically. It collapses into a single quantum spin interacting with a bath of bosonic modes, a spin-boson system. This is a well-understood and frequently used model in physics.

Why is this so helpful?

Simulating a single spin interacting with some modes is significantly less computationally intensive than tracking millions of entangled qubits. The team employed matrix product states, a method for compactly storing quantum states that aren’t excessively entangled. Larson also developed a new optimization technique to identify the best QAOA parameters in this setup, which is the optimal “knob settings” for each layer. 

All computations were performed on DOE supercomputers at the Argonne Leadership Computing Facility and the National Energy Research Scientific Computing Center, under an INCITE grant. This aligns with the wider effort to integrate supercomputing with quantum research.

What the Scoreboard Actually Showed

As the QAOA depth increased in the large-system limit, the average approximation ratio, how close the algorithm’s answer came to the known optimum, climbed toward 1. A score of 1 represents perfect accuracy. This confirms that adding more layers does indeed yield better results, and now there’s a rigorous way to observe this without running the algorithm on hardware that doesn’t yet exist.

This marks a significant advancement for quantum optimization research. Previously, this area of the map was uncharted; it was impossible to grade QAOA at scale and determine if increasing depth continued to be beneficial or eventually hit a ceiling. Now, at least for this model, that assessment is possible.

What This Means, and What It Doesn’t

Let’s be clear about the boundaries. This is a classical study tool for understanding a quantum algorithm. No quantum computer executed QAOA here. The team simulated a simplified version of the problem on classical supercomputers, which is distinct from a hardware demonstration, as they would readily acknowledge.

Furthermore, this study doesn’t claim that QAOA is a definitive “winner.” Though it shows that the approximation ratio approaches 1 in an idealized, noiseless, infinite-size limit suggests the algorithm has potential, it doesn’t indicate whether real, noisy hardware can achieve that limit, or if a more efficient classical algorithm might get there first and at a lower cost. The mapping is also specific to the SK model, so this isn’t a universal grading rubric for every optimization problem. Larson succinctly articulated the takeaway: progress in quantum computing relies on improved algorithms and better classical tools for testing them, not solely on larger devices.

What’s real is a new method for measuring a quantum algorithm’s theoretical maximum potential. What remains aspirational is whether real machines will ever reach it. This work constructed the ruler, not the building.