A startup says an unreleased Anthropic model proved an 18-year-old quantum computing conjecture
Physical Superintelligence says a Lean-checked proof came on day three of a run. The proof hasn't been peer reviewed, and the model hasn't been named.
Physical Superintelligence, an AI physics lab that goes by PSI, said Friday that a research system it built proved the Aaronson-Ambainis conjecture, a quantum complexity problem first posed in 2008. PSI says the run used instances of a non-public Anthropic model on its own infrastructure. The system had a complete proof on the third day, and Lean, a proof assistant that checks each step by computer, accepted it. PSI says the system then improved the result twice, and Lean accepted the final version as well.
In plain terms, the result says that on most random inputs, an ordinary computer can predict a quantum algorithm's yes-or-no output with only polynomially more looks at the data. Big quantum speedups in this setting therefore need special structure in the input. PSI's David Turturean built the system and is responsible for the paper's correctness. Four Stanford researchers who proved a special case in August are reading the proof and called it 'a huge result,' according to PSI.
This is the company's own claim. The paper hasn't been through peer review, and PSI hasn't said which Anthropic model it used. Business Insider reports that Anthropic did not respond to a request for comment.
- Problem
- Aaronson-Ambainis conjecture (2008)
- Model
- Non-public Anthropic model, not named
- Time to proof
- Third day of the run
- Verification
- Lean; peer review pending