An AI-assisted proof narrows where quantum query advantages can hide
PSI reports a Lean-checked proof of the Aaronson–Ambainis conjecture, a major result about quantum queries on typical inputs whose scope does not extend to all quantum algorithms.
Physical Superintelligence announced a proof of the Aaronson–Ambainis conjecture on November 6, produced using its research harness and a non-public Anthropic model.
The result concerns how many queries a quantum algorithm needs to answer a yes-or-no question about an input, compared with a classical algorithm. It constrains large advantages on typical, unstructured inputs; it does not abolish useful quantum computing. [1][3]
The team released a paper and a Lean formalization. Its repository records checks with Lean’s kernel, additional kernel implementations and a comparison of the formal statements. That is unusually inspectable evidence for an AI-assisted mathematical announcement: a computer can check whether the formal derivation follows from its premises. [2]
Sources & details 3 sources
Discuss in your voice app
Take the reporting, visual explanations and original sources into a conversation. Copy the brief, paste it into your preferred assistant, then start its voice mode.
Paste the brief into your voice app to discuss this reporting.Reporting sources
- PSI’s research announcement
November 6 first-party account of the proof and discovery process; proprietary harness and non-public model.
- Public paper and Lean verification repository
Formal statements, proof files, dependency caveats and recorded checker results. This newsroom did not execute them.
- Scott Aaronson’s assessment
November 8 explanation by a co-originator of the conjecture; supports mathematical significance and scope, not an independent rerun by this newsroom.
Images & figures
AI-generated editorial illustration of a theorem's limited domain and structured possibilities beyond it; not a proof diagram, a quantum device or a claim that quantum advantage is eliminated.
Euangelion · AI-generated editorial illustration · Source · Usage terms