Startup PSI Says Its AI System Proved an 18-Year-Old Quantum Conjecture in Three Days
Research startup PSI (Physical Superintelligence) announced on November 6 that its internal research system has proved the Aaronson-Ambainis conjecture. Stated by computer scientists Scott Aaronson and Andris Ambainis in 2008, the quantum complexity conjecture bears on when quantum computers can be exponentially faster than classical machines, and had resisted proof for 18 years.
PSI says the research system — built and run by member of technical staff David Turturean — runs instances of a non-public Anthropic model, and produced a complete proof on the third day of its run; the system then improved the result twice. The formal version was machine-checked step by step by the Lean proof assistant: the public repository holds 648 machine-checked theorems, with no unproved placeholders and no added axioms, re-verified by two independent Lean kernel implementations. The paper and the Lean code were released together.
The result has not been peer-reviewed and the paper is a preprint; neither Aaronson nor Ambainis has publicly weighed in. PSI's repository also leaves one task to readers: confirming that the formal statement matches the conjecture as originally printed, since the human-readable paper itself is not machine-checked. In August, a Stanford team proved a special case of the conjecture, for algorithms using a fixed number of parallel query rounds; PSI says its proof covers the general case. Whether it holds under sustained expert scrutiny remains the open question.
(Source: PSI)
Source: PSI (Physical Superintelligence
Published by GSM · USA (original Chinese edition)
Photo: 图：IBM 量子计算机装置。An IBM quantum computing installation. (Wikimedia Commons, CC BY 2.0)
