PSI says research system found proof of quantum computing conjecture

Proposed by Scott Aaronson and Andris Ambainis, the conjecture concerns when quantum computers can achieve exponential speedups over classical computers.[1] PSI says its proof replaces a conjectured inequality with a new inequality proved in the manuscript.[1] The practical scope matters: the result concerns a specific question about quantum speedups, and does not establish a general limit on total computing time.[1][2] PSI also states that, for fixed error and fraction, the number of looks an ordinary computer needs grows at most as a fixed power of T.[1]

The quoted formal result gives a lower bound for influence: Inf_i[p] ≥ (8√15 / (125π⁴))·ε^(5/2)/d⁶ ≥ (ε/d)⁷.[3] The repository defines a variable’s influence as the expected squared change in the polynomial when that variable is flipped.[3] That mathematical statement should not be read as a general bound on total computing time; the Quantum Insider says the theorem establishes no such limit.[2] The bound and definitions give readers specific material to examine in the published formalization, but do not broaden the theorem beyond its stated scope.[3]

PSI says the system improved the result twice and Lean accepted the final version, and its paper, Lean proofs and code are publicly available.[1] The repository says PSI’s four theorems were proved without placeholders or added axioms, and that two independent implementations of the Lean kernel re-checked the formal proof.[3] PSI says AI models produced the proof, paper and formalization.[3] The company says David Turturean developed and ran the system, scoped the problem, reviewed the draft and is responsible for the paper’s correctness; Jim Halverson audited the proof, and Phiala Shanahan commented on the Lean formalization.[1]

Formal verification does not by itself settle whether the formal statement matches the printed conjecture: Unite.AI says readers still need to confirm that correspondence.[4] Unite.AI also reports that the human-readable paper itself was not machine-checked.[4] PSI says Guy Blanc, Jordan Docter, Carmen Strassle and Li-Yang Tan read the full proof, sent comments and are preparing a shorter expert exposition.[1] The researchers described the result as a major resolution with implications for which problems admit quantum speedups.[1] For readers assessing the claim, the published proof, the match between its formal statement and the conjecture, and the forthcoming exposition are distinct things to consider.[1][4]