Anthropic's mysterious model cracks a major conjecture in quantum computing, solving a problem that has baffled the mathematics world for nearly 20 years

Beating AI News Flash: AI research company Physical Superintelligence (PSI) announced that, with the help of an unreleased Anthropic model, it proved the Aaronson–Ambainis conjecture, which has puzzled the mathematics community for nearly 20 years. The AI found the complete proof on the third day of operation, and it passed verification by the Lean mathematical verification tool.

This conjecture was proposed by two scientists in 2008 and studies just how large the speed advantage of quantum computers really is.

Quantum computers may be hundreds of millions of times faster than ordinary computers when handling certain problems. For example, factoring a particularly large integer could take an extremely long time on an ordinary computer using known algorithms, while a quantum computer is expected to greatly shorten the computation time. But this huge advantage usually depends on some mathematical regularity inherent in the problem itself.

This time, the AI proved that if the input data is completely random and has no special regularity to exploit, then for problems that only require answering "yes" or "no," quantum computers cannot achieve an exponential advantage in the number of data reads.

For example, to determine a result from a massive set of random numbers, a quantum computer can use quantum superposition so that one query involves multiple positions. Although an ordinary computer can read only one position at a time, as long as it knows the decision rule of the quantum algorithm, it can prioritize checking the numbers that most affect the result and, with a relatively limited number of queries, approximately predict the quantum computer's answer.

Previously, mathematicians already knew that this could be done in certain special cases, but they had been unable to prove that this rule holds universally. PSI has now completed the full proof and also solved a theoretical problem that has lasted for nearly 20 years.

After the news spread, University of Washington professor Pedro Domingos even argued that the dream of quantum computing advantage has been shattered.

Scott Aaronson, one of the proposers of the conjecture, subsequently pointed out that this understanding is wrong. The research only limits how many data queries a quantum computer can save in specific problems, and does not deny the actual computational speed advantage of quantum computers. Shor's algorithm for factoring large integers, as well as simulations in quantum physics and chemistry, are all unaffected.

Aaronson said that he has not yet fully understood the proof, but Lean has completed its check and other mathematicians have also reviewed it, so he believes the result is correct. He also joked that although he is happy that his conjecture has finally been proved, he is also somewhat disappointed that humanity ultimately failed to solve it before AI.