Physical Superintelligence says an AI system proved the Aaronson–Ambainis conjecture
Start-up Physical Superintelligence said its system, running a non-public Anthropic model, had a proof by day three; Scott Aaronson wrote he believes it, citing the Lean check and expert review.
- Ideas & essays
- Notable
Physical Superintelligence (PSI), a start-up, said on its research page that a research system it built, running instances of a non-public Anthropic model, had proved the Aaronson–Ambainis conjecture, an open problem since 2008. TechCrunch reported that the model was Anthropic’s Fable 5.2, to which PSI had early access, and that PSI held the result until the model was nearly ready for release. Anthropic announced Fable 5.2 and Mythos 5.2 on 9 November.
The conjecture, stated by Scott Aaronson and Andris Ambainis, concerns polynomials. PSI said that if it holds, quantum computers are at most polynomially faster than classical ones on random yes-or-no questions, ruling out exponential speedups for unstructured inputs. PSI reported that its system had a complete proof on the third day of a run and that the Lean proof assistant accepted it. The team then pointed the system at related open problems, improved the result twice, and had Lean accept the final version. The page does not give the length of the run.
The evidence is PSI’s own, with a public paper and Lean code for checking. David Turturean, who ran the system, is named as responsible for the paper’s correctness; he prompted the model to draft the paper and reviewed it, and PSI describes it as a first draft. PSI said Stanford researchers who proved a related partial result in August have reviewed the full proof, sent comments and called it “a huge result”. The paper is not peer-reviewed.
Aaronson wrote on 8 November that he believed the proof was correct, citing the Lean certificate and review by human experts, though TechCrunch reported he said he does not fully follow it. He said the result rules out one type of quantum advantage and has “zero effect” on Shor’s factoring algorithm. TechCrunch quoted him noting surprise that it had not appeared in OpenAI’s October batch of AI-written proofs. It reported no reaction from other mathematicians beyond PSI’s own adviser, Jim Halverson.
The result adds to a run of AI-credited mathematics that leans on Lean verification, including DeepMind’s quantum programs the same week.
In the commentary
What people were saying around this time — external links, from the record's commentary rail.