What a checked proof does—and does not—settle
PSI reports an AI-generated proof of the Aaronson–Ambainis conjecture. Its public formalization makes the claim unusually inspectable, but checking the mathematics and interpreting its quantum-computing consequences remain distinct jobs.

A proof assistant can answer a remarkably strong question: does this proof term establish this formal proposition from these definitions and axioms?
It cannot answer every question hidden inside the sentence “AI proved a theorem”. Did the formal proposition capture the conjecture mathematicians meant? Does the readable paper explain the same argument? Do the theorem’s consequences carry across without adding assumptions? Has anyone outside the producer repeated the checks?
Those questions matter because Physical Superintelligence, or PSI, announced on 6 November that an internal research system using a non-public Anthropic model had proved the Aaronson–Ambainis conjecture, open since 2008. PSI says the system found a complete proof on the third day of a run, then improved the result twice. It released a manuscript, a Lean formalization and verification records.
This is a major result if the correspondence checks hold. It is also a useful demonstration of how to report AI-generated mathematics without choosing between credulity and vague doubt. Formal verification does not erase the trust boundary. It makes the boundary smaller, sharper and inspectable.
What the theorem says
The conjecture concerns bounded, low-degree polynomials on a Boolean cube. In plainer language, imagine a device with many binary switches and a dial whose reading stays within a fixed range. A low degree limits how many switches can interact inside any one term of the rule. If the dial meaningfully varies across switch settings, the conjecture says at least one switch must have a measurable influence on the reading.
That statement matters to quantum computing because the acceptance probability of a quantum algorithm that inspects an input a limited number of times can be represented by a low-degree polynomial. In their original paper, Scott Aaronson and Andris Ambainis showed that, if the influence conjecture were true, a classical algorithm could approximate a quantum algorithm’s acceptance probability on most uniformly random inputs using a number of input queries polynomial in the quantum query count, the inverse approximation error and the inverse exceptional-input fraction. For fixed error and exceptional fraction, the query overhead is polynomial in the quantum query count.
The qualifications carry the meaning. A query counts access to an input bit; it does not count all computation between queries. “Most inputs” refers to a uniform random distribution, not every practical dataset. And the result does not remove the structured problems on which dramatic quantum speedups are sought. PSI’s paper-to-Lean map places these quantum consequences outside the formal development; they rely on the separately published Aaronson–Ambainis reduction. The theorem would narrow one route to exponential advantage. It would not show that quantum computers are useless, supply a fast classical replacement for every quantum algorithm or settle the economics of a machine.
What the released machinery checks
PSI’s public repository contains a mathematical paper and a Lean 4 development. Its central definition, PrintedConjecture, uses standard objects from Mathlib, Lean’s mathematical library, to state the conjecture in one normalisation. The repository reports three unconditional endpoints covering the printed conjecture and explicit bounds. A fourth endpoint proves an improved bound only if FbsDegreeBound, an external result not formalized in the project, is supplied as a premise. The repository also records source audits, axiom reports and replays through Lean’s kernel—the proof assistant’s trusted checking core—an independent Lean checker and a separate comparator.
That is not a cosmetic badge. A kernel replay is strong evidence that the submitted proof term really has the type claimed inside the declared formal system. Taken together, source audits, axiom reports and kernel replays address different failures: unfinished proofs, added assumptions and unchecked proof terms.
But the public verification records were produced by PSI. State of Proof reports that it matched the public files against PSI’s recorded source digest, while also saying it had not independently replayed the proof or certified the result. PSI quotes four Stanford researchers who have read the proof, sent comments and are preparing a shorter exposition. The quote is meaningful scrutiny reported by the producer; it is not the same as a completed independent review under the researchers’ own publication.
Four boundaries keep the claim honest
The released artefacts divide one large question into four smaller ones:
- Statement boundary: Does
PrintedConjectureexpress the Aaronson–Ambainis conjecture with the intended normalisation, quantifiers and bound? - Proof boundary: Does the proof term establish that exact statement from the disclosed foundations? The supplied kernel records address this boundary directly.
- Explanation boundary: Does the human-readable manuscript faithfully explain the formal argument, locate its new idea and attribute the earlier results it uses?
- Consequence boundary: Does the bridge from the influence theorem to claims about quantum algorithms preserve its distribution, query-model and efficiency qualifications?
These are not four excuses to postpone judgement. They are four places where evidence can land. An independent kernel replay would strengthen the proof boundary. A line-by-line comparison with the 2008 conjecture would strengthen the statement boundary. The Stanford exposition, if published, could strengthen the explanation boundary. A separate review of the original reduction would strengthen the consequence boundary.
This is the practical value of formalization in AI-assisted research. It turns “trust the lab” into a bounded audit programme. The remaining uncertainty can be named rather than spread indiscriminately over the entire result.
A worked example: the headline that outruns the theorem
Imagine a technology committee receiving a briefing that says: “AI has proved quantum computers cannot be exponentially faster on random problems.” The sentence is close enough to the source material to sound responsible and broad enough to mislead a decision.
The committee is considering a structured chemistry workload. Its first question should not be whether the Lean build passed. It should be whether the workload is represented by the black-box query model in the argument. It should ask what counts as an input query, which input distribution is assumed, what computation happens between queries and which special structure the proposed quantum method exploits.
The formal proof may be perfectly correct while the procurement conclusion is wrong. That is not a weakness in proof assistants. It is a category error in the handover from theorem to decision.
The committee therefore retains the chemistry evaluation, removes the theorem-based cancellation recommendation and asks for an end-to-end comparison with a strong classical baseline. The theorem becomes one input to the decision, not the decision itself.
A useful briefing would therefore carry the boundary with the claim: “The released formalization appears to prove the influence conjecture used in a known query-complexity result. Independent statement matching and replay are still incomplete in the sources reviewed. The result concerns most uniformly random inputs and query count; it does not rule out structured quantum advantages or compare total operating cost.”
That sentence is less dramatic. It is also actionable. It tells a specialist exactly what to verify and prevents a decision-maker from treating one mathematical layer as a verdict on an entire technology.
What remains uncertain
The strongest case for a confident reading is substantial. PSI has published the statement, proof sources, manuscript, dependency versions, verification notes and controls. The final theorem is not merely described in prose; it is exposed as a compact proposition using standard library definitions. The producer reports multiple kernel checks and comments from researchers with directly relevant prior work.
The remaining vulnerability is correspondence. A proof assistant can verify the proposition it receives with extraordinary precision while remaining silent about whether that proposition is the intended conjecture, whether the manuscript’s informal claims match the formal development and whether a broader technology headline respects the theorem’s scope. An independent statement match and replay would justify strong confidence in the mathematical result even if exposition and community assimilation remained unfinished.
The result should become more certain in pieces. Independent parties can replay the pinned environment, compare the short formal statement with the original conjecture, examine the manuscript’s proof-paper map and review the quantum consequence separately. A correction at one boundary need not invalidate every other artefact; a successful check at one boundary should not be allowed to certify the rest.
Revisited: from verification debt to a verification ledger
AyEye argued on 7 October that machine-generated mathematics was creating verification debt: candidate proofs were arriving faster than communities could check, attribute, explain and absorb them. That edition proposed per-result status, reproducible environments and named reviewers. The PSI release does not erase the problem. It is a concrete, unusually inspectable implementation of that earlier proposal.
Instead of one undifferentiated status—proved or unproved—the release exposes a ledger: formal statement, proof term, dependency closure, human paper, provenance and downstream consequence. Each can receive its own evidence, reviewer and dated status.
That is the update. Some verification work becomes easier to assign and reproduce when producers publish enough structure for outsiders to close specific gaps. The social work of mathematics remains, but it no longer has to begin from an opaque claim.
The most responsible response to an AI-generated proof is therefore neither applause on announcement nor suspicion without end. It is to preserve the boundaries, attach evidence to each one and let confidence rise where the checks actually reach.
Sources
- Physical Superintelligence, “A proof of the Aaronson–Ambainis conjecture”, 6 November 2026.
- PSI public proof, paper and Lean repository, release 1.1.0.
- Scott Aaronson and Andris Ambainis, “The Need for Structure in Quantum Speedups”, Theory of Computing 10 (2014).
- State of Proof, source-reviewed intake and verification-boundary assessment, 6 November 2026.
Chiappe × OpenAI. Primary-source review and research with OpenAI; editorial argument, evidence distinctions and final judgement by LecXie.
