AI Proves 30-Year-Old Quantum Computing Conjecture

A mathematical puzzle that has stumped researchers for over two decades has finally been cracked, and the solver wasn’t a human mathematician but an AI model. Anthropic’s Claude 3.5 has successfully proven the Aaronson-Ambainis conjecture, a decades-old theory about the limits of quantum computing that could reshape how we think about where these machines actually excel.

Scott Aaronson of The University of Texas at Austin first grappled with this question back in 1999. At the time, researchers had identified at least one problem where quantum computers clearly dominated: Shor’s algorithm for factoring large numbers. But Aaronson wondered if quantum advantage required this kind of specific mathematical structure, or whether it could also work on completely random, unstructured problems. Together with Andris Ambainis at the University of Latvia, he formally proposed in 2011 that the answer was no. For over a decade, no one could prove it.

When Quantum Isn’t Better

The conjecture itself is elegantly simple to state, though fiendishly difficult to prove. Imagine a quantum computer trying to answer a yes-or-no question after scanning through a massive, completely random string of 1s and 0s. Could it do so by checking far fewer bits than a classical computer would need to examine? The Aaronson-Ambainis conjecture says no. A regular computer could match the quantum machine’s performance without needing significantly more time.

This matters because it eliminates an entire category of potential quantum advantages from consideration. If quantum computers can’t win when there’s no mathematical structure to exploit, that tells us something crucial about where their true strengths lie.

The breakthrough came from David Turturean and colleagues at the startup Physical Superintelligence, who deployed Anthropic’s model to tackle the problem. Remarkably, the AI took just four days to generate a complete proof, refine it twice, and verify it using the proof-checking software Lean. The AI and mathematics community has been watching similar developments with a mix of excitement and caution.

A Radically Different Approach

What makes this proof particularly striking is how different it is from previous work in the field. Aaronson and Ambainis had translated their conjecture into the language of polynomials, hoping to tap into centuries of mathematical theory. They succeeded in getting other mathematicians interested, but a proof remained elusive.

When researchers at Stanford University examined the AI-generated proof, they found something unexpected. “The proofs are entirely different and substantially more difficult,” they wrote. “Everything is also woven together in a novel way.” The AI didn’t just solve the problem using known techniques more efficiently. It created new connections between disparate areas of mathematics.

Shachar Lovett at UC San Diego, whose work formed part of the foundation for this proof, sees real value in how the AI approached the challenge. “This helps us guide our research,” he noted. “What I think is going to come from these AI tools is that now we can maybe ask more ambitious questions.”

Still More Mysteries Remain

But before quantum computing researchers pop the champagne, there’s an important caveat. This proof is deeply mathematical rather than immediately practical. Lovett warns against reading too much into real-world implications. Aaronson agrees, pointing out that this result “rules out a potential direction where you could look for quantum speedups, but it wasn’t a plausible direction anyway.”

The Stanford team emphasized that this is far from the end of quantum computing’s story. Problems with shorter input strings, non-binary outputs, or industrial applications like molecular simulation could still benefit from quantum approaches. The landscape of quantum advantage remains vast and largely unexplored.

What’s genuinely exciting is how AI could accelerate the formulation of new mathematical questions in quantum computing. Instead of just demolishing old conjectures, researchers now wonder if AI could help discover entirely new problems worth pursuing. Matthew Pines at PSI wants to use AI as a creative research partner, not just a proof-verification machine.

Ambainis offers a healthy reality check though. “There is some major creative leap needed,” he says. “I think that’s something where AI is not good yet.”

As we stand at this intersection of artificial intelligence and fundamental mathematics, the real question isn’t whether AI can prove old theorems, but whether it can help us ask better questions in the first place.

Source: New Scientist