Quantum Query Complexity of Boolean Functions

This direction is merged into another direction: quantum query complexity lower bounds, quantum algorithms for matroid problems. Its last version stays readable and citable here.

Version 1 of 182 papers114 conceptsfrozen 2026-10-04

In the quest to understand what makes quantum computers powerful, researchers often strip away the complexity of hardware and focus on the "black-box" or query model. In this setting, we measure the efficiency of an algorithm by how many times it must "ask" an oracle for a piece of input data to compute a function $f(x)$.

The study of quantum query complexity seeks to map the fundamental boundaries of quantum advantage. By analyzing Boolean functions—the simplest logical building blocks—researchers have uncovered a rigorous mathematical landscape where quantum speedups are governed by the underlying structure of the problem.

The Structural Divide: Total vs. Partial Functions

The most significant realization in this field is that quantum speedup is not a universal "magic dust." Instead, as Scott Aaronson argues in How Much Structure Is Needed for Huge Quantum Speedups?, there is a "Law of Conservation of Weirdness." Exponential speedups are only possible when a problem is partial—meaning it comes with a "promise" that the input has a very specific, rare structure.

A classic example is the Forrelation problem, introduced by Scott Aaronson and Andris Ambainis in Forrelation: A Problem that Optimally Separates Quantum from Classical Computing. A quantum computer can solve Forrelation in just one query, while a classical computer requires $\sqrt{N}$ queries. This represents the "ceiling" of quantum-classical separation in the black-box model.

In contrast, total functions—those defined for every possible binary input—are much harder to speed up. For decades, it was conjectured that quantum computers could only achieve a quadratic speedup (like Grover’s algorithm) over classical ones for total functions. However, Scott Aaronson, Shalev Ben-David, and Robin Kothari shattered this in Separations in query complexity using cheat sheets by introducing a "cheat sheet" framework that proved a power-2.5 separation, showing that the gap is larger than previously thought but still strictly polynomial.

The Polynomial Bridge

Why can we prove these limits so precisely? The answer lies in the Polynomial Method. Every quantum algorithm that makes $T$ queries can be represented as a complex polynomial of degree at most $2T$. This creates a constructive equivalence: if you want to know if a quantum algorithm can compute a function, you can instead ask if a low-degree polynomial can approximate that function.

This bridge allows researchers to apply tools from classical analysis to quantum problems:

The Sensitivity Breakthrough and the Quartic Ceiling

For years, a major missing piece was the "Sensitivity Conjecture," which related various complexity measures of Boolean functions. When Hao Huang proved this conjecture in 2019, it had immediate "quantum implications."

In Quantum Implications of Huang's Sensitivity Theorem, Scott Aaronson showed that for any total Boolean function, the classical deterministic query complexity $D(f)$ is at most the fourth power of the quantum query complexity $Q(f)$. This $D(f) = O(Q(f)^4)$ result effectively set a "quartic ceiling" on quantum speedups for unstructured problems, proving that for total functions, we will never see the exponential leaps found in Shor's algorithm.

Extending the Reach: Communication and Learning

The insights from Boolean query complexity are now being exported to other domains:

By treating Boolean functions not just as logic gates but as mathematical objects with Fourier spectra and polynomial degrees, this research direction has moved quantum computing from a collection of "clever tricks" to a rigorous branch of complexity theory.

Papers in this version

Showing 60 of 82 papers.

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_quantum_query_complexity_of_boolean_func_aec8c2d6,
  title = {Quantum Query Complexity of Boolean Functions},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/quantum-query-complexity-of-boolean-functions/rdr_aec8c2d610f04595a654564d77647850},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_quantum_query_complexity_of_boolean_func_aec8c2d6_v1,
  title = {Quantum Query Complexity of Boolean Functions},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/quantum-query-complexity-of-boolean-functions/rdr_aec8c2d610f04595a654564d77647850/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}