Matematikai áttörést ért el egy MI-rendszer a kvantumszámításban

The Aaronson-Ambainis conjecture is now a theorem. Open since 2008, the conjecture of Scott Aaronson and Andris Ambainis concerns when quantum computers can be exponentially faster than ordinary ones. Now, a research system developed internally at Physical Superintelligence (PSI), running a non-public Anthropic model, found a proof for it, settling one of the most fundamental questions in quantum computing. In 1994, Peter Shor found a quantum algorithm that factors large numbers far faster than any known method for ordinary computers [1]. It works because the problem hides a repeating pattern, and the quantum computer finds how often it repeats. Like most dramatic quantum speedups known, Shor’s algorithm relies on structure: a promise that the input has a rare pattern. Whether quantum computers can be exponentially faster on random inputs, which almost never have such structure, was unknown. Aaronson and Ambainis found a way to settle this question using pure mathematics. They stated a conjecture about polynomials and showed that, if it is true, quantum computers are at most polynomially faster on random inputs. Researchers have counted the conjecture among the central open problems of quantum complexity theory [3, 4]. At PSI, we found the proof with a research system we developed internally, in a run on our own infrastructure. Instances of a non-public Anthropic model were used in the run. The system had a complete proof of the conjecture during the third day of the run, and Lean, a proof assistant in which a computer checks every step, accepted it. We then set the system to work on related open problems. Along the way, the system improved the result twice, and Lean accepted the final version. The proof builds on ideas of Shachar Lovett and Jiapeng Zhang, of David Reimer and of others [5, 6]. In August 2026, Guy Blanc, Jordan Docter, Carmen Strassle and Li-Yang Tan of Stanford University had settled the conjecture’s prediction in a special case, proving that there is no exponential speedup on random inputs for quantum algorithms that look at their input in a fixed number of parallel rounds [7]. They have since been reading our proof of the full conjecture, have sent us comments and are writing a shorter exposition of it for experts. They wrote to us: “This is a huge result. It resolves a decades-old conjecture with important implications for the nature of problems that admit quantum speedups. The proof draws on and extends several lines of work in the analysis of boolean functions and probabilistic combinatorics. Everything is brought together in a rather magical way.” Quantum computing still has plenty of mysteries, but now there is one fewer. Speedups like Shor’s can be measured in looks: how many times a computer has to read its input, a long string of 0s and 1s. With each look, an ordinary computer reads one bit of the string, while a quantum computer’s look can be spread in superposition over many positions. When the string is promised to repeat, as in Shor’s algorithm, a quantum computer needs exponentially fewer looks than any ordinary computer. Aaronson and Ambainis asked whether a quantum computer can answer a yes-or-no question about a random string with exponentially fewer looks than an ordinary computer. To show that it cannot, it is enough to show that an ordinary computer can imitate the quantum computer without many more looks. The quantum computer says yes with a probability that depends on the string, so imitating it means estimating that probability. Beals, Buhrman, Cleve, Mosca and de Wolf had shown that after T looks, this probability is a polynomial in the bits of the string, of degree at most 2T, with values between 0 and 1 [8]. So the ordinary computer has to predict the value of a polynomial of this kind while reading only a few bits of the string. Aaronson and Ambainis stated a conjecture about these polynomials, a statement of pure mathematics, and showed that if it is true, an ordinary co