An AI system running an Anthropic model settled an almost 20-year-old conjecture with implications for “Quantum Speedup”

AI‑Driven Proof Settles a Two‑Decade‑Old Quantum Conjecture

An AI‑native physics startup, Physical Superintelligence (PSI), announced that its internal system—running a proprietary Anthropic language model—produced a complete, formally verified proof of the Aaronson‑Ambainis conjecture. The conjecture, posed in 2008 by quantum‑complexity theorists Scott Aaronson and Andris Ambainis, has been a central open problem in quantum computing theory for almost twenty years. By leveraging the Lean proof assistant to check every logical step, PSI claims the proof was generated in just three days of computation on its own hardware and subsequently refined through self‑directed iterations.

---

Why the Conjecture Matters

The Aaronson‑Ambainis conjecture addresses a fundamental question: How much advantage can a quantum computer gain over a classical one when answering a yes‑or‑no question on random, unstructured data?

• Quantum speedup is typically measured by how the number of required operations (or queries) grows with input size. Exponential speedups—exemplified by Shor’s factoring algorithm—are the holy grail because they dramatically outpace classical methods as problems scale.
• For unstructured problems, the best known quantum advantage is Grover’s square‑root speedup, which is provably optimal for pure search tasks.
• The Aaronson‑Ambainis conjecture posited that for typical random inputs, any quantum algorithm’s advantage is bounded by a polynomial factor, not an exponential one. In plain terms, a classical computer could predict the quantum answer for almost every input without needing exponentially more data reads.

If true, the conjecture forces a re‑evaluation of claims that quantum computers will deliver exponential gains on messy, real‑world data lacking hidden structure.

---

The AI‑Generated Proof in a Nutshell

1. Model and Infrastructure – PSI’s system ran an unreleased Anthropic model on a dedicated compute cluster. The model was tasked with exploring proof strategies for the conjecture.
2. Formal Verification – The generated proof was encoded in Lean, a proof‑assistant that checks each inference against the underlying logical foundations. Lean accepted the proof on the first pass, confirming its correctness.
3. Self‑Improvement Loop – After the initial proof, the system was given related open problems. It refined its argument twice, each time producing a version that Lean also verified.
4. Public Release – PSI posted the research note, the full formal proof, and accompanying code on GitHub, inviting the community to inspect the work.

The proof hinges on a refined analysis of influence and variance in low‑degree polynomials that represent quantum query algorithms. By establishing a tighter bound on the influence of individual input bits, PSI demonstrated that a classical algorithm can iteratively query the most influential bits, reducing uncertainty to a polynomial‑size number of looks. This resolves the conjecture with an explicit exponent, improving on earlier bounds that weakened exponentially with polynomial degree.

---

Implications for Quantum Computing and Industry

• Re‑framing Quantum Advantage Claims – Companies promising exponential speedups on unstructured data must now articulate the specific structure their algorithms exploit. The proof narrows the landscape of problems where quantum computers can truly outperform classical machines.
• Guidance for Algorithm Design – Researchers can focus on problems with inherent algebraic or periodic structure—where exponential speedups remain viable—rather than expending effort on generic search tasks.
• Validation of AI‑Assisted Mathematics – The success of PSI’s approach showcases how large language models, combined with rigorous formal tools, can accelerate discovery in theoretical computer science. It may inspire broader adoption of AI‑driven proof search in other open problems.
• Cautious Optimism – While the proof is not yet peer‑reviewed, the community’s initial reaction (including the lack of comment from Aaronson and Ambainis as of early November) suggests a period of scrutiny. If the result holds, it will become a cornerstone result in quantum complexity theory.

---

Looking Ahead

The Aaronson‑Ambainis conjecture has long stood as a litmus test for the limits of quantum query complexity. Its resolution clarifies that exponential quantum speedups are intrinsically tied to structured inputs. For practitioners, this means that future quantum‑hardware investments should prioritize algorithms that leverage such structure—factoring, hidden‑period problems, and certain sampling tasks—rather than generic data‑analysis pipelines.

At the same time, the demonstration that an AI system can generate a formally verified proof in days opens a new frontier for collaborative mathematics. As proof assistants become more user‑friendly and language models more capable, we may see a surge of AI‑augmented breakthroughs across mathematics, physics, and computer science.

---

Bottom line: PSI’s AI‑driven proof settles a two‑decade‑old conjecture, confirming that quantum computers cannot achieve exponential speedups on random yes‑no queries without exploitable structure. The result reshapes expectations for quantum advantage and highlights the growing role of AI in formal scientific discovery.