A proof of Aaronson‑Ambainis conjecture.
* Physical Superintelligence (PSI) announced that its automated research system used an unreleased, non-public Anthropic model to prove the conjecture—a major open problem in quantum complexity theory and computing speedups that had remained unsolved since 2008.
* According to PSI, the AI system successfully generated a complete proof by its third day of operation, and the final proof was formally checked and verified using the Lean interactive theorem prover.
* The result sheds light on the exact conditions under which quantum computers hold an exponential advantage over classical computers, while also highlighting the performance gap between advanced internal AI research models and those currently available to the public.
Notes:
The (AA) conjecture, posed by Scott Aaronson and Andris Ambainis in 2008, addresses a fundamental question in theoretical computer science: When can a quantum computer run exponentially faster than a classical computer, and when is that exponential speedup impossible?
To understand the conjecture without getting lost in mathematical physics, it helps to look at how computer scientists evaluate quantum speedups through the Query Model (or “black-box” model).
1. The Black-Box (Query) Model.
In quantum complexity theory, algorithms are often evaluated by asking: How many times must the computer query an unknown black box (an input database or function) to find an answer?
* Polynomial Speedup: A classical search takes N queries (e.g., checking an unsorted phonebook of N names one by one). Grover’s quantum search algorithm does it in sqrt N queries. That is a quadratic speedup—valuable, but not exponential.
* Exponential Speedup: Shor’s algorithm for factoring large numbers or algorithms evaluating specific algebraic structures can solve in log(N) or polynomial steps what would take a classical computer exponential time.
Aaronson and Ambainis wanted to pinpoint the exact structural feature of a problem that allows for an exponential quantum speedup in this query setting.
2. The Core Idea: Influential Inputs vs. Distributed Clues.
The AA conjecture focuses on bounded functions (problems where the output is between-1 and 1 and measures the influence of individual input bits.
* High Individual Influence: Think of a needle in a haystack. Changing a single specific bit in the input drastically alters the output. The information is localized.
* Low Individual Influence: The output depends on collective, global properties of the data, but *no single bit* carries significant weight by itself. The information is smoothly spread out across millions of inputs.
The conjecture makes a precise mathematical assertion about functions where every single input bit has very low influence:
The Conjecture:
Any quantum algorithm that queries a black-box function where all individual input variables have small influence can be approximated by a classical algorithm using only a polynomially larger number of queries.
3. Why It Matters for Quantum Computing Speedups.
The resolution of the conjecture establishes a clean boundary between where quantum computing shines and where classical algorithms can keep up.
It Rules Out “Magic” Quantum Speedups on Spread-Out Data.
If no single bit of an input function matters much on its own, a quantum computer cannot achieve an exponential query speedup over a classical computer. At best, the quantum advantage is polynomial (like Grover’s search).
It pins down the source of exponential advantage.
For a quantum algorithm to yield an exponential speedup (like Shor’s algorithm or period-finding routines), the underlying problem must possess rich global algebraic structure or internal symmetries (such as hidden subgroup structures) that create concentrated “influential features” when transformed (e.g., via Quantum Fourier Transforms).
Formalizing Complexity Boundaries.
In complexity theory, proving this conjecture connects quantum query complexity to classical polynomial approximations and Fourier analysis of Boolean functions (specifically extensions of the Kahn-Kalai-Linial theorem to quantum settings). It proves that quantum algorithms cannot bypass fundamental analytical limits of function influence.
#ArtificialIntelligence #QuantumComputing #quantumphysics
A proof of the conjecture about quantum speedups on random inputs, with a complete formalization in Lean.