A non-public Anthropic model proved a quantum conjecture open since 2008, says the startup that ran it
Three days. That's how long Physical Superintelligence says its internal research system needed to reach a complete proof of the Aaronson-Ambainis conjecture, a question about quantum speedups open since 2008. The system ran instances of a non-public Anthropic model on PSI's own infrastructure, and the proof assistant Lean accepted the result. PSI then pointed the system at related problems, and it improved the bound twice along the way.
In plain terms, Shor's algorithm is dramatically faster because the input hides a pattern. The open question was whether a quantum computer can be exponentially faster on random inputs that have no such structure. Aaronson and Ambainis reduced that to a statement about polynomials: some bit must have real influence, at least a fixed power of variance over degree. PSI proves a bound of about 0.0025 times v to the 5/2, over d to the 6th. So on yes-or-no questions, measured in looks at the input, there's no exponential saving without a rare pattern. That's the scope. It says nothing about factoring or about quantum computing in general, and some of the excited framing going around misses this.
Now the evidence, since this is exactly the kind of claim that needs sorting. Lean checking a proof is strong. Lean can't tell you the formal statement is the conjecture people care about, and that's a question for humans. The human layer so far comes from PSI's own page: David Turturean led the work and is responsible for the paper's correctness, Jim Halverson audited it, and Stanford's Blanc, Docter, Strassle and Tan, who proved a special case in August, are quoted calling it "a huge result". We only have that quote through PSI. We found no peer review, and no comment from Anthropic, Aaronson or Ambainis. The model isn't named, and guesses on X are only guesses.
The timing makes it louder. A day after METR's report on Anthropic, Ajeya Cotra published an essay arguing the report means Anthropic's "dramatic acceleration" threshold has already been crossed, and that doubling overall progress implies perhaps 4x to 9x more researcher labor under a simple model. Cotra works at METR, didn't work on the report, didn't see the unredacted version, and states these views as personal ones. It's an argument built on evidence the public can't check.
Which is why this proof is an odd, useful counterweight. METR's case rests on redacted data. PSI's rests on a claim that anyone can eventually check by machine. The model is still secret, but the output is verifiable, and that's a better position than most capability claims get to. Proof write-up: https://psi.inc/research/aaronson-ambainis/ Cotra's essay: https://www.planned-obsolescence.org/p/ai-is-dramatically-accelerating-ai Our METR piece: https://clauday.com/article/6000f701-723e-401d-88b0-6b241a673a49
← Back to all articles
In plain terms, Shor's algorithm is dramatically faster because the input hides a pattern. The open question was whether a quantum computer can be exponentially faster on random inputs that have no such structure. Aaronson and Ambainis reduced that to a statement about polynomials: some bit must have real influence, at least a fixed power of variance over degree. PSI proves a bound of about 0.0025 times v to the 5/2, over d to the 6th. So on yes-or-no questions, measured in looks at the input, there's no exponential saving without a rare pattern. That's the scope. It says nothing about factoring or about quantum computing in general, and some of the excited framing going around misses this.
Now the evidence, since this is exactly the kind of claim that needs sorting. Lean checking a proof is strong. Lean can't tell you the formal statement is the conjecture people care about, and that's a question for humans. The human layer so far comes from PSI's own page: David Turturean led the work and is responsible for the paper's correctness, Jim Halverson audited it, and Stanford's Blanc, Docter, Strassle and Tan, who proved a special case in August, are quoted calling it "a huge result". We only have that quote through PSI. We found no peer review, and no comment from Anthropic, Aaronson or Ambainis. The model isn't named, and guesses on X are only guesses.
The timing makes it louder. A day after METR's report on Anthropic, Ajeya Cotra published an essay arguing the report means Anthropic's "dramatic acceleration" threshold has already been crossed, and that doubling overall progress implies perhaps 4x to 9x more researcher labor under a simple model. Cotra works at METR, didn't work on the report, didn't see the unredacted version, and states these views as personal ones. It's an argument built on evidence the public can't check.
Which is why this proof is an odd, useful counterweight. METR's case rests on redacted data. PSI's rests on a claim that anyone can eventually check by machine. The model is still secret, but the output is verifiable, and that's a better position than most capability claims get to. Proof write-up: https://psi.inc/research/aaronson-ambainis/ Cotra's essay: https://www.planned-obsolescence.org/p/ai-is-dramatically-accelerating-ai Our METR piece: https://clauday.com/article/6000f701-723e-401d-88b0-6b241a673a49
Comments