PSI says an unreleased Anthropic model produced a Lean-checked proof of a 2008 quantum conjecture
The Friday preprint says the Aaronson-Ambainis conjecture, open since 2008, is now a theorem. The repository says four Lean theorems have no placeholders and were replayed through two kernels. It also says a reader still has to confirm that the formal statement is the printed conjecture, and that the paper itself is not machine-checked. Anthropic did not answer Business Insider.
Feature4 minIn-depth
James Okonkwo4 min read
- PSI
- Anthropic
- Lean
- Quantum

Photo: PSISource page
Physical Superintelligence said on Friday that a research system it built, running instances of a non-public Anthropic model, found a proof of the Aaronson-Ambainis conjecture, and that Lean accepted it. The post is dated 6 November. The public repository, created the same day, calls the manuscript a preprint and releases a Lean 4 formalization under the Apache 2.0 license. The post’s first sentence is “The Aaronson-Ambainis conjecture is now a theorem.” The repository does not treat that sentence as something a machine has certified. It says a reader still has to confirm that the formal statement matches the conjecture as printed, and that the human-readable paper is not itself machine-checked.
The conjecture is from Scott Aaronson and Andris Ambainis. The repository identifies it as Conjecture 1.7 of their 2014 paper in Theory of Computing, which is Conjecture 6 of the arXiv version, and says it has been open since the work that began in 2008. It asks whether a quantum computer can answer a yes-or-no question about a random string of bits with exponentially fewer looks at that string than an ordinary computer. Aaronson and Ambainis reduced the question to a statement about polynomials: a polynomial of low degree, with values between 0 and 1, that is not almost constant, must have some input bit with a non-negligible influence. If that is true, an ordinary computer can imitate the quantum computer’s acceptance probability up to a small error on all but a small fraction of strings, with a number of looks that grows like a power of the quantum computer’s, not an exponential.
PSI says the system had a complete proof on the third day of a run on the company’s own infrastructure, that Lean accepted it, and that the system then improved the result twice. The proof, the post says, follows a plan of Shachar Lovett and Jiapeng Zhang and replaces an inequality they had left as a conjecture. David Turturean, a member of the technical staff, developed the system, chose the problem, ran it, prompted the model for a first draft of the paper, reviewed the draft, and “is responsible for the paper’s correctness.” Jim Halverson, an advisor, audited the proof. Phiala Shanahan, an advisor, commented on the Lean formalization. The repository says the mathematical statements, the first draft and the formalization were produced by AI models in a harness Turturean developed.
What Lean was asked to accept
The bound in the repository, for a polynomial of degree at most d whose values on the Boolean cube lie between 0 and 1 and whose variance is at least ε, is that some variable has influence at least (8√15 / (125 π⁴)) · ε^(5/2) / d^6, and that this is at least (ε/d)^7. The conjecture had asked for some fixed power of ε/d. A second form, on the cube of plus and minus one, carries a smaller constant. Four public theorems are named. The one called aaronson_ambainis is the (ε/d)^7 form. A fourth theorem, with a larger constant, assumes a result of Avantika Agarwal and Shalev Ben-David that the repository says is not formalized here. The main statement does not take that result as a hypothesis.
The repository’s trust note is specific about the checks and about what they leave out. A static audit found no sorry, no added axiom and no escape hatch around the kernel in the library sources. Printing the axioms behind each of the four theorems lists only the standard Lean principles propext, Classical.choice and Quot.sound. Declarations were replayed through Lean’s kernel with leanchecker, and the same replays were made with lean4lean, a separate implementation of the type checker. A sandboxed comparator, using the nanoda checker and a Lean kernel, accepted the four theorems on a GitHub-hosted machine. On a second machine it accepted one small correct solution and rejected four deliberately wrong ones. The note then lists what this does not cover: whether PrintedConjecture says what the conjecture says; the paper, which is for human readers; and Lean’s kernel and compiler, Mathlib’s definitions, and the machines the checks ran on. There is no description of review by a journal.
In August, Guy Blanc, Jordan Docter, Carmen Strassle and Li-Yang Tan at Stanford had proved a special case, for quantum algorithms that look at their input in a fixed number of parallel rounds. PSI says those four have been reading the new proof, have sent comments, and are writing a shorter exposition. The post quotes them: “This is a huge result. It resolves a decades-old conjecture with important implications for the nature of problems that admit quantum speedups.” The quote is PSI’s account of what they wrote. Kelsey Vlamis’s Business Insider story, timestamped 00:49 UTC on Saturday, reports the same quote as coming from PSI’s announcement. She writes that it is not clear which unreleased Anthropic model was used, and that Anthropic did not respond to a request for comment.


