Key points
- PSI says its system found a proof using an Anthropic model
- IonQ, Rigetti, and D-Wave aren't in PSI's announcement
- The proof passed a computer check, and expert review has begun
Physical Superintelligence, known as PSI, says its research system has proved the Aaronson-Ambainis conjecture, a question in quantum computing theory that has been open since 2008. The system used a non-public model from Anthropic (ANT), PSI said on Nov. 6.
The conjecture is a mathematical statement about polynomials. Its importance for quantum computing is what follows from it: if PSI's proof holds, an ordinary computer can estimate a quantum algorithm's probability of answering yes, on most inputs and within a fixed margin of error, without exponentially more reads of the input.
That result concerns the number of reads, or queries, rather than total running time. It doesn't rule out exponential speedups for structured problems or say when today's quantum machines will become useful.
PSI says the proof passed checks in Lean, a proof assistant. The paper remains a preprint.
PSI launched in September with $58 million in seed funding. It hasn't identified the Anthropic model, and Anthropic didn't respond to Business Insider's request for comment.
The conjecture sets a limit on quantum speedups
Quantum algorithms are often measured by queries, or the number of times they read their input. Aaronson and Ambainis asked whether a quantum computer can answer a yes-or-no question with exponentially fewer queries when the input is random. Here are the terms that come up:
| Term | What it means |
|---|---|
| Query | One read of the input. An ordinary computer reads one bit, while a quantum query can spread across many positions at once |
| Structure | A rare pattern in the input, such as the repeating pattern Shor's factoring algorithm finds |
| Exponential speedup | The ordinary computer needs exponentially more queries than the quantum computer |
| Polynomial speedup | The ordinary computer needs more queries, but the count grows only by a fixed power |
| Influence | The average squared change in a polynomial's value when one input bit is flipped. Squaring keeps positive and negative changes from canceling out |
Earlier research showed that a quantum computer's chance of answering yes after a set number of queries can be written as a polynomial with values between 0 and 1. Aaronson and Ambainis conjectured that if such a low-degree polynomial varies enough, at least one input variable must have a substantial influence. The bound depends on the polynomial's degree and variance.
That gives an ordinary computer a way to estimate the quantum algorithm's chance of answering yes. It reads the most influential bits, one after another, until that value barely depends on the remaining bits.
PSI's paper says that method works on most inputs. For a fixed margin of error and fraction of exceptions, the paper's upper bound on the ordinary computer's queries is proportional to the eighth power of the quantum query count. That's polynomial growth rather than exponential.
The proof leaves Shor's algorithm and quantum hardware alone
The result doesn't rule out exponential speedups for problems with structure. Shor's 1994 algorithm for factoring large numbers relies on that kind of pattern. PSI's paper says faster-than-polynomial speedups in the query model require structure, such as a promise about the inputs.
If the proof holds, it confirms what researchers already expected. Aaronson and Ambainis described the underlying belief as folklore, and Business Insider said the limits had long been suspected.
The theorem counts queries, which aren't the same as total running time. It says nothing about qubit counts, error rates, or when a machine will be useful.
The distinction matters for holders of IonQ (IONQ), Rigetti Computing (RGTI), and D-Wave Quantum (QBTS). PSI's announcement names none of the three companies, and the result doesn't establish a change in their hardware capabilities or commercial prospects. Our comparison lays out how the three differ.
PSI's proof passed a computer check, and expert review has begun
PSI said the system had a complete proof during the third day of its run. Lean, a proof assistant in which a computer checks every step, accepted it. The system then improved the result twice, and Lean accepted the final version.
PSI's public repository says the proof, the paper, and the Lean formalization were produced by AI models. David Turturean, who built the research system, reviewed the paper and is responsible for its correctness, the repository says. PSI said its advisers also weighed in: Jim Halverson audited the proof, and Phiala Shanahan commented on the Lean formalization.
Those checks have limits, which the repository spells out. A reader still has to confirm that the Lean statement matches the printed conjecture, and the paper itself isn't machine-checked. The paper also notes that an earlier announced attempt at the conjecture was later withdrawn.
Four Stanford University researchers who settled a special case in August have been reading the proof, PSI said, and are writing a shorter version for experts. "This is a huge result," they wrote in a statement published by PSI. Their statement is an early expert reaction to a paper that's still a preprint.
That shorter version is the next test. PSI's claim follows the release of 722 AI-written math manuscripts by OpenAI in October.
