AI-Assisted Proof Settles Longstanding Question About Quantum Speedups
AI-summarised brief · reviewed before publication
Researchers at Physical Superintelligence (PSI) announced a formal proof of the Aaronson‑Ambainis conjecture, a problem first posed in 2008 about the conditions under which quantum computers can achieve exponential speedups. Using a proprietary Anthropic language model, the team generated a proof that was subsequently verified in the Lean proof assistant and peer‑reviewed. The theorem shows that for most randomly generated yes‑or‑no inputs, a classical algorithm can approximate a quantum algorithm’s acceptance probability without needing exponentially more input queries, implying that exponential advantages require structured inputs. The result limits quantum superiority in the query model but does not constrain total runtime, leaving open the possibility of practical quantum gains on problems with inherent mathematical or physical structure.
💡 Why It Matters
- · It redirects quantum algorithm research toward structured problems, confirming that unstructured data alone cannot yield the dramatic speedups often touted for quantum computers.