A decades-old, vastly influential conjecture about quantum computing has finally been proven – by AI. It confirms that a whole class of mathematical problems would not be more easily solved by quantum computers.
In 1999, of The University of Texas at Austin got stuck on a question about when exactly quantum computers could excel over their conventional counterparts.
At this time, researchers knew of at least one example of a problem where the quantum approach outshone all others: Shor’s algorithm for factoring numbers. But they suspected that this hinged on specific mathematical structure that underlies the factoring problem. Aaronson wondered whether quantum computers could also win in the opposite case, when the problem contained little to no structure and lots of randomness instead. In 2011, he and at the University of Latvia formally conjectured that in at least one case the answer was negative, but they could not prove it.
Advertisement
Now, at the start-up Physical Superintelligence (PSI) and his colleagues have used Anthropic’s Fable 5.2 model to . This eliminates a whole class of problems from the race to understand what quantum computers are best at.
“It’s a very crisp mathematical question that has consequences for quantum computing, and it has been very hard to solve to the degree that I had given up on it my myself,” says Ambainis. “This might be one of the [few] remaining long-standing open questions that are worth pursuing,” says Turturean.
The problem at the heart of the Aaronson-Ambainis (AA) conjecture requires a computer to answer a “yes” or “no” question after being fed a huge but random string of bits, or 1s and 0s. Could a quantum computer get an answer by looking at the string significantly fewer times than a conventional computer would have to? The researchers conjectured that a conventional computer could approximate the quantum computer’s performance for most strings and without having to take much longer. More simply, you could get away with not using a quantum computer at all.
Importantly, Aaronson and Ambainis translated the statement at the core of their conjecture into the language of polynomials, recasting it as a problem in a different field of pure mathematics. “We didn’t think it would catch on like it did. People who were powerhouses in their own fields and didn’t care about quantum computing got interested,” says Aaronson.
PSI’s breakthrough builds on the work of such mathematicians. Turturean says that it took about 4 days for Fable 5.2, which was not publicly available at the time, to complete the proof, improve and refine it twice, and verify the final version with the proof-checking software Lean. The PSI team then shared the proof with , , and at Stanford University in California, who studied it and wrote an exposition that unraveled its key ingredients.
In a joint statement to New Scientist, they wrote that the new proof meaningfully surpasses all studies that it draws upon. “The proofs are entirely different – and substantially more difficult. Everything is also woven together in a novel way,” they wrote.
at the University of California, San Diego, whose work was one of the key ingredients in the proof, says that this exposition reveals tricks that mathematicians can now learn from and reuse. “This helps us guide our research. What I think is going to come from these AI tools is that now we can maybe ask more ambitious questions,” he says.
But Lovett is cautious about the impact this new work might have on quantum computing, as it is more mathematical than practical, he says. In Aaronson’s view the weight of practical implications is also unclear. “This rules out a potential direction where you could look for quantum speedups, but it wasn’t a plausible direction anyway,” he says. The glaring question now is where to look for new problems that quantum computers are uniquely positioned to take on.
“This is far from the end of quantum speedups. Instead, it informs us on what types of problems we should consider,” wrote the Stanford team. A similar problem with a shorter or less random input string, or one for which the quantum computer does not give just a “yes” or “no” answer, could still benefit from the quantum approach, they wrote. This leaves tremendously many problems, including simulating industrially relevant molecules and some optimisation problems.
Aaronson says that many of the mathematically best posed questions related to quantum information science have already fallen to AI, so it’s time to formulate some new ones. at PSI says that he and his colleagues now also want to use AI exactly to explore new ideas instead of just knocking down famous problems. The future will show how successful this can be. “There is some major creative leap needed. I think that’s something where AI is not good yet,” says Ambainis.
