Aaronson-Ambainis Conjecture

The Aaronson-Ambainis conjecture is an open question in theoretical computer science, named after the researchers Scott Aaronson and Andris Ambainis, who formulated it in 2009. It revolves around how much faster a quantum computer — a machine that exploits the rules of quantum mechanics — can be compared to an ordinary computer when computing a certain type of function. The conjecture claims: the possible advantage is always bounded, never unboundedly large. This sounds technical, but it has far-reaching consequences for where quantum computers are truly useful and where they are not.

The Limit of Quantum Speedup

Quantum computers are considered significantly more powerful than classical computers — but that is not uniformly true for every problem. For some tasks they offer enormous advantages, for others barely any difference at all. The Aaronson-Ambainis conjecture attempts to precisely describe this boundary.

Specifically, it concerns so-called boolean functions: computational problems in which the input consists of many yes-no decisions and the output is likewise yes or no. Such problems appear everywhere, from database search to cryptography. The conjecture states: if a quantum computer is significantly faster on such a function, there must be a comprehensible structural reason for it — and this reason is always measurable.

This is not self-evident. Without this restriction, it would be conceivable that quantum computers are exponentially faster on certain problems without anyone ever being able to explain why. The conjecture rules out exactly this uncontrollable scenario — provided it turns out to be true.

What Lies Behind the Conjecture

To understand the conjecture, one needs the concept of sensitivity. The sensitivity of a boolean function measures how many inputs must be changed before the output changes. A function with high sensitivity reacts even to small changes. The Aaronson-Ambainis conjecture states, in simplified terms: the more sensitive a function is, the smaller the maximum quantum advantage in computing that function.

To this day, no proof has been found. It has been shown that the conjecture holds for many special classes of functions, but no one has yet been able to prove or disprove the general case. This makes it one of the central open problems of quantum complexity theory — the field that studies which problems are how hard.

A related problem, the so-called sensitivity conjecture concerning classical computers, was likewise considered unsolved for decades — until Hao Huang closed it in 2019 with an elegant, merely two-page proof. This has encouraged researchers: sometimes a new perspective is enough to solve a stuck problem. For the Aaronson-Ambainis conjecture, this breakthrough is still pending.

Where the Conjecture Matters in Practice

For the development of real quantum algorithms, the conjecture serves as an important orienting framework. When engineers and researchers design new algorithms for quantum computers, they must assess for which problems the effort is worthwhile. The conjecture provides a theoretical guardrail here: certain types of speedup are simply not possible — or at least should not be.

In news coverage, it usually comes up when companies like Google or IBM announce new quantum processors and claim to be able to solve certain problems exponentially faster. Critics examine such claims partly by checking whether they are compatible with the Aaronson-Ambainis conjecture. If a supposed quantum advantage could not be explained, it is probably not a real one.

Scott Aaronson himself runs the influential blog Shtetl-Optimized, on which he regularly provides public context for such claims. The conjecture is thus not merely theory in an ivory tower — it is an active tool for critically assessing real products and announcements.