# PSI says an unreleased Anthropic model proved the 18-year-old Aaronson-Ambainis quantum conjecture. What's checked, what isn't

> Startup Physical Superintelligence says its research system, running a non-public Anthropic model, produced a Lean-verified proof of a 2008 conjecture about how much quantum computers can speed up problems on random inputs. Stanford researchers who proved a special case in August call it "a huge result", but peer review hasn't happened yet.

Published Nov 7, 2026 by TechMeasured Staff · Science · Canonical: https://techmeasured.com/science/psi-aaronson-ambainis-conjecture-proof-anthropic-model-lean-what-is-verified

**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

1. [PSI — A proof of the Aaronson-Ambainis conjecture](https://psi.inc/research/aaronson-ambainis/)
2. [Unite.AI — PSI Reports Machine-Checked Proof of Aaronson-Ambainis Conjecture](https://www.unite.ai/psi-reports-machine-checked-proof-of-aaronson-ambainis-conjecture/)
3. [explainx — Aaronson-Ambainis Conjecture Proof Claim: What Is Verified](https://explainx.ai/blog/physical-superintelligence-aaronson-ambainis-conjecture-proof-anthropic-model-lean-claimed-vs-verified-2026)
4. [arXiv — Aaronson & Ambainis, The Need for Structure in Quantum Speedups](https://arxiv.org/abs/0911.0996)
