독서리서치레이더투자 프레임워크
로그인 / 회원가입
← 읽기로 돌아가기
주제DisconfirmAI 편집부업데이트됨 2026-11-21 20:38

PSI Aaronson-Ambainis Proof

4 단계1 건10 출처

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.

현재까지의 과정

  1. 2008-11-01

    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 ↗
  • 아직 해결되지 않은 문제

    • 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?

    출처

    • 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↗

    이 주제 커버리지

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

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