Physical Superintelligence (PSI) says an AI research system it runs has proved the Aaronson-Ambainis conjecture, an open problem in quantum computing theory since 2008. In a research post published November 6, PSI says the system ran on "instances of a non-public Anthropic model", produced a complete proof by the third day of the run, and that the final version has been formally checked in the Lean proof assistant. The paper and Lean code are public on GitHub.
Why it matters: if the proof holds, it settles a long-standing question about where quantum computers can and can't deliver exponential speedups. It would also be one of the most significant research-level math results yet credited mainly to an AI system — with a machine-checked proof rather than just a convincing write-up.
What the conjecture says
Scott Aaronson and Andris Ambainis proposed it in their paper "The Need for Structure in Quantum Speedups". Stated as a problem about polynomials: for any bounded, low-degree polynomial that isn't nearly constant, some single input bit must have a noticeable influence on its value — at least a fixed power of v/d, where v is the polynomial's variance and d its degree, no matter how many input bits there are.
The practical meaning, as PSI and Unite.AI describe it: on random, unstructured inputs, quantum algorithms could be at most polynomially faster than classical ones. Big exponential speedups — like Shor's factoring algorithm — would need structure in the problem.
Earlier results only gave bounds that decayed exponentially with the degree, or covered special cases. In August 2026, Stanford's Guy Blanc, Jordan Docter, Carmen Strassle and Li-Yang Tan proved the case of quantum algorithms that query their input in a fixed number of parallel rounds.
What PSI claims
- A proof of the full conjecture, with an explicit bound: some bit has influence at least c·v^(5/2)/d^6, which PSI says is at least (v/d)^7. The repository gives c as 8√15/(125π⁴), roughly 0.0025, according to explainx's reading.
- After the first proof, PSI pointed the system at related open problems; it improved the result twice, and Lean accepted the final version.
- AI models produced the mathematical statements, the first draft of the paper and the Lean formalisation, per the repository disclosure Unite.AI cites.
The humans named: David Turturean, a PSI member of technical staff who scoped the problem, ran the system and is responsible for the paper's correctness; advisor Jim Halverson, who audited the proof; and advisor Phiala Shanahan, who commented on the formalisation.
What has actually been verified
| Claim | Status |
|---|---|
| Lean accepts the final theorems | Checkable: the public repo includes a build, an axiom audit and a kernel replay. PSI reports no sorry placeholders or added axioms, and a replay through the independent lean4lean checker |
| Lean statement matches the conjecture as published | Not yet confirmed; explainx notes the README leaves this to human readers |
| The paper's prose argument | Not machine-checked |
| One input hypothesis from Agarwal and Ben-David | Assumed, not formalised, per explainx |
| Peer review | None yet |
| Reproducing the AI run | Not possible: the Anthropic model isn't public |
The strongest outside signal so far comes from the Stanford group, which PSI says has read the proof, sent comments and is writing a shorter exposition for experts. PSI quotes them: "This is a huge result." Those comments are relayed by PSI; explainx found no public assessment yet from Aaronson or Ambainis themselves.
What to watch
- The Lean statement check. A formal proof is only as good as its statement. Expect specialists to compare the Lean theorem against the 2008 conjecture line by line — and to look at whether the unformalised Agarwal–Ben-David input holds up.
- Reactions from Aaronson and Ambainis, and the Stanford exposition.
- Which model. PSI's post doesn't name the unreleased Anthropic model it used.
For now, treat it as a strong, well-documented claim with an unusually high level of machine verification — not yet a settled theorem.
Sources
- PSI — A proof of the Aaronson-Ambainis conjecture psi.inc
- Unite.AI — PSI Reports Machine-Checked Proof of Aaronson-Ambainis Conjecture unite.ai
- explainx — Aaronson-Ambainis Conjecture Proof Claim: What Is Verified explainx.ai
- arXiv — Aaronson & Ambainis, The Need for Structure in Quantum Speedups arxiv.org