The research firm PSI has announced the resolution of the Aaronson-Ambainis conjecture, a problem in quantum computing that has remained unsolved for 18 years. The company utilized a proprietary Anthropic model alongside its own infrastructure to generate the mathematical proof within three days.
The resulting proof was verified using Lean, a tool designed for checking the logical consistency of formal reasoning. The system performed two iterations of the output before reaching the final version. The conjecture, first proposed in 2008, addresses the conditions under which quantum computers provide exponential speedups over classical systems.
The findings suggest that for certain classes of algorithms, classical computers may only require polynomial growth in resources rather than exponential growth. This proof does not negate the overall advantages of quantum technology but clarifies the boundaries for specific protocols, excluding specialized solutions like Shor's algorithm.
The work has undergone preliminary review at Stanford University, where researchers previously proved a specific case of the conjecture in August. While Lean ensures internal consistency, the academic community is currently preparing a formal summary to confirm that the automated proof accurately reflects the original mathematical problem.
