Today Physical Superintelligence PBC is announcing a proof of the Aaronson-Ambainis conjecture, one of the central open problems in quantum complexity, with major implications for quantum computing speedup.
psi.inc/research/aaronson-am…
Thread 👇
Nov 6, 2026 · 2:05 PM UTC
Last month, PSI solved five long-standing problems in quantum information theory.
Now, we resolve one of the most fundamental questions in quantum computing: when can quantum computers be exponentially faster than classical ones by an exponential margin?
Scott Aaronson and Andris Ambainis had connected this question to a conjecture about polynomials. If true, quantum computers are at most polynomially faster than classical ones unless the inputs satisfy a special condition, such as the exponential structure in Shor's algorithm.
PSI proved this conjecture is true: that bounded polynomials of low degree have influential variables. The influence of a bit is the average change in a polynomial's value when the bit is flipped.
We formalized and checked the proof using Lean, a proof assistant language commonly used for machine verification of mathematical results. The manuscript and the Lean formalization are public here:
github.com/physical-superint…
We discovered the proof with a research system we developed internally, in a run on our own infrastructure, leveraging a non-public Anthropic model. @DavidTurturean at PSI led this work.
The proof builds on ideas of Shachar Lovett and Jiapeng Zhang, of David Reimer, and of others.
Guy Blanc (of MIT), Jordan Docter, Carmen Strassle and Li-Yang Tan (of Stanford), who settled a special case of the conjecture's classical simulation consequence in August, have been reading our proof and are writing a short exposition of it. They wrote to us:
"This is a huge result. It resolves a decades-old conjecture with important implications for the nature of problems that admit quantum speedups. The proof draws on and extends several lines of work in the analysis of boolean functions and probabilistic combinatorics. Everything is brought together in a rather magical way.”
We built PSI as the AI-native laboratory fueling the physics takeoff, leveraging physical superintelligence to vastly expand the pace and scale of research physicists can pursue.
Come build with us.
psi.inc/
See our previous results on open quantum problems here:
xitter.twitterapi.xyz/psipbc/status/21148657…
Today Physical Superintelligence PBC is announcing solutions to five long-standing problems in quantum information theory.
psi.inc/research/oqp-batch-2…
Thread 👇
The Aaronson–Ambainis Conjecture holds the #388 spot overall on my list of the top 500 open problems in math and ranks #4 in the Quantum Information & Computation category.
proofatlas.ai/open-problems/
Holy moly, this is insane 🤯
An AI system using an unreleased Anthropic model (Fable 5.5 🔥) helped crack an 18-year-old quantum computing conjecture in 3 days.
Basically, this helps us figure out which problems quantum computers can actually be way faster at.
And if AI can crack decades-old math in days, imagine how fast science could move from here.
@grok can you summarize this and the consequences of this like I am really really dumb? Will quantum computers be more or less likely be the default computers for the future after this?
2
2
2,229
I’ve noticed that most ML models take quantum mechanics as a solved problem, and so they can build a “proof” out of thin air.
What’d be interesting is if someone built an adversarial model and tore down quantum mechanics using a super deterministic axiom.
I suspect it’d tear everything down, it’d shut down these expensive contraptions funding, and it’d be glorious.
1
4
2,593
