AI-Assisted Proof Settles Longstanding Question About Quantum Speedups

Introduction

A team at Physical Superintelligence (PSI) has announced a breakthrough proof of the Aaronson‑Ambainis conjecture, a question that has lingered in quantum‑computing theory since 2008. Using a non‑public Anthropic language model and the Lean proof assistant, the researchers demonstrated that exponential quantum advantages in the query model—the number of times an algorithm reads its input—cannot arise on most randomly generated yes‑or‑no problems unless the problem possesses special structure. The result sharpens our theoretical understanding of where quantum computers can truly outperform classical machines, while still allowing for practical speedups in structured domains.

The query model and the conjecture

In the query model, computational effort is measured by how many queries an algorithm makes to its input rather than by total runtime. A classical query reads a single bit; a quantum query can act on a superposition of bits, potentially extracting more information per query. The Aaronson‑Ambainis conjecture posited that for any quantum algorithm, there must exist at least one input bit whose influence on the algorithm’s acceptance probability is large enough to let a deterministic classical algorithm approximate that probability with only a polynomial overhead in the number of queries.

The new proof confirms this intuition. It shows that for any quantum algorithm making Q queries, a classical deterministic algorithm can estimate the quantum acceptance probability on all but a tiny fraction of inputs using O(Q^c) queries, where c is a fixed constant independent of the problem size. In other words, on most random inputs, classical computers can mimic the query behavior of quantum algorithms without an exponential blow‑up.

How AI helped discover the proof

PSI’s research system ran multiple instances of an Anthropic model that scoured the literature, generated candidate lemmas, and stitched together arguments. After three days of automated exploration, the system produced a complete proof of the conjecture, which was then refined twice to improve the quantitative bounds. All steps were formalized in Lean, and the Lean kernel verified the logical correctness of the proof. Human researchers, led by David Turturean, curated the AI‑generated material, edited the exposition, and took responsibility for the final manuscript.

Implications for quantum algorithm design

The theorem does not claim that quantum computers cannot outperform classical ones; it only limits the query advantage on unstructured inputs. Practical quantum speedups still thrive on problems with exploitable structure—such as Shor’s factoring algorithm, which leverages periodicity, or quantum simulation of physical systems with symmetries. The result therefore nudges algorithm designers toward focusing on structured problems where quantum interference can be harnessed effectively.

Moreover, the proof clarifies that the barrier is informational: the number of input bits a quantum algorithm must learn cannot be dramatically lower than what a classical algorithm can achieve on average. It leaves open the possibility of moderate (polynomial) query savings or large speedups when the problem’s mathematical or physical structure supplies the needed leverage.

Limits and avenues for future work

While the theorem settles the conjecture, several open questions remain:

• Tightening the bound. The current guarantee provides a polynomial relationship between quantum and classical query counts. Sharper constants or lower‑degree polynomials could further restrict quantum advantages.
• Beyond query complexity. The result does not address total runtime, memory usage, or other resources that may still favor quantum machines.
• Robustness across models. Extending the analysis to other computational models—such as communication complexity or learning theory—could reveal additional nuances.
• AI‑assisted discovery. The success of PSI’s system suggests a promising role for large language models in mathematical research, but reproducibility and scalability to other open problems need systematic study.

Closing thoughts

The AI‑assisted proof of the Aaronson‑Ambainis conjecture marks a milestone in both quantum‑computing theory and the emerging practice of machine‑augmented mathematics. By establishing that exponential query‑based quantum speedups require structured inputs, the work provides a clearer roadmap for where to seek genuine quantum advantage. At the same time, it highlights the continuing relevance of classical algorithmic insight and the potential of AI tools to accelerate deep theoretical breakthroughs.