ReadingResearchRadarInvestment framework
Sign in / Sign up
← Back to reading
TopicDisconfirmAI EditorialUpdated 2026-11-21 20:38

PSI Aaronson-Ambainis Proof

4 steps1 pieces10 Sources

AI startup Physical Superintelligence (PSI) announced on November 6, 2026, that it proved the Aaronson-Ambainis conjecture using an internal, non-public Anthropic model. The result, verified by the Lean proof assistant and reviewed by experts from MIT and Stanford, establishes a fundamental limit for quantum computing: without specific structural patterns in input data, quantum computers cannot achieve exponential speedups over classical algorithms for decision problems.

The timeline of this development begins with the conjecture's formulation by Scott Aaronson and Andris Ambainis in 2008/2009, which posited that bounded low-degree polynomials must have influential variables. In August 2026, researchers at Stanford University settled a special case of the prediction. On November 6, 2026, PSI published the full proof, stating their system found the solution on the third day of its run. By November 8, 2026, an exposition paper by Guy Blanc, Jordan Docter, Carmen Strassle, and Li-Yang Tan was submitted to arXiv, confirming they had read and commented on PSI's work.

The significance lies in defining the boundary of quantum advantage. Peter Shor’s algorithm relies on periodic structures; this proof confirms that such structure is necessary for exponential gains. For random inputs lacking this structure, classical computers can simulate quantum query probabilities with only polynomial overhead. This does not negate quantum utility in chemistry or physics but closes a door on "universal" parallelism myths.

Disagreement centers on verification depth. While Lean checked the formal logic, human mathematicians must confirm the formal statement matches the intended conjecture. Additionally, the proof has not yet undergone traditional peer review. State of Proof noted they had not independently reproduced the check as of early November.

Watch for: 1) Formal publication or journal acceptance of the arXiv preprints (2611.09773 and 2611.11626). 2) Independent reproduction of the Lean verification by external teams. 3) Further commentary from Scott Aaronson regarding the implications for BPP vs BQP complexity classes.

How it got here

  1. 2008-11-01
Sign in / Sign up
ReadingResearchRadarInvestment framework

2008-11-01: Scott Aaronson and Andris Ambainis formulate the conjecture concerning polynomial influence and quantum query limits.

psi.inc ↗
  • 2026-08-01

    2026-08-01: Stanford researchers (Blanc, Docter, Strassle, Tan) prove the conjecture's prediction for a special case involving fixed-round parallel queries.

    psi.inc ↗
  • 2026-11-06

    2026-11-06: PSI publishes the proof of the full Aaronson-Ambainis conjecture, generated by an internal system using a non-public Anthropic model and verified by Lean.

    psi.inc ↗
  • 2026-11-08

    2026-11-08: An exposition paper by Stanford authors detailing the proof is submitted to arXiv, noting no financial compensation from Anthropic or PSI.

    arxiv.org ↗
  • What is still unsettled

    • Has the formal Lean statement been independently confirmed by the mathematical community to exactly match the original 2008 conjecture?
    • Will the proof undergo standard academic peer review, given the current status as an arXiv preprint?
    • What are the precise implications for the BPP vs BQP problem in unrelativized worlds as suggested by the new theorem?

    Sources

    • spektrum.de↗
    • heise.dec't Magazin↗
    • psi.incpsi.inc/research/aaronson-ambainis/index.html↗
    • arxiv.orgarxiv.org/abs/2611.11626v1↗
    • neoteo.comneoteo.com/en/what-psi-claims-about-its-anthropic-assisted-aaronson-ambainis-proof↗
    • github.comgithub.com/physical-superintelligence/aaronson-ambainis/blob/main/AaronsonAmbainis/Main.lean↗
    • arxiv.orgarxiv.org/abs/2611.09773↗
    • original.ifeng.comoriginal.ifeng.com/c/8xsSw9iwlr7↗
    • cj.sina.com.cncj.sina.com.cn/articles/view/5952915720/162d24908067054lo0↗
    • 10100.comwww.10100.com/article/158257851↗

    Coverage in this topic

    • AI Startup PSI Proves Aaronson-Ambainis Conjecture Using Internal Anthropic Model, Defining Quantum Computing Limits2026-11-19News

      AI startup PSI announced it proved the Aaronson-Ambainis conjecture using an internal Anthropic model, a result verified by experts from MIT and Stanford.