A Query Complexity-agon
A central question in the study of query complexity is finding polynomial relationships between different measures. For instance, D is deterministic query complexity, how many bits you have to read of a string to answer a question about it, while Q is quantum query complexity – how many bit-reads you need to make on a quantum computer.
It’s known that Q ≤ D ≲ Q⁴. The first inequality is easy: Q ≤ D just means that if you can do it in D many reads on a regular computer, then you can do it in that same number on a quantum computer, because a quantum computer can do anything a classical one can. The other inequality means that you can get away with a fourth-power loss when you make a quantum algorithm classical, and this argument is much less straightforward. We also know these are optimal: there are problems where D ≍ Q and problems where D ≍ Q⁴, so it’s not like we could do something more clever and improve this to D ≲ Q³. One could say this comparison is settled, and some people track these, e.g. I track some here. Another important measure between D and Q is R, randomized query complexity.
Recently there were a few breakthroughs: OpenAI’s model found a function where R ≍ Q⁴, and we knew that R ≲ Q⁴, so now that is settled1. And another pair of papers (1, 2) that settled the optimal exponent between R and C, certificate complexity (“how many bits can I show to you to prove the answer”).
With so many exponents settled, I thought, maybe we should ask for more! Maybe we can ask for the whole set of possible joint exponents. Why not have the general relationship between R, Q, C, and so on, all known? AI is letting us learn so much more, so let’s be a bit more ambitious in what we ask.
It turns out (with help from ChatGPT for double-checking my work, and making the pretty pictures) that these recent works did in fact just recently fully determine the (R,Q,C) polygon: we know the set of exponents relating them!
The bottom edge is the line Q ≤ R, which means that quantum computers can do anything a random computer can. The top-left edge says that R ≤ C², which is the first relevant result here, from 1987 (reference). The lower-right edge says that C ≲ R², from Nisan’s block-sensitivity bounds. The right edge says that C ≲ Q⁴, which follows from C ≤ D ≲ Q⁴. The top edge says that R ≲ Q⁴, which follows from R ≤ D ≲ Q⁴.
The vertices correspond to different functions that show these are optimal. It’s five vertices, but actually only three functions are really needed: A is a construction due to Aaronson, Ben-David and Kothari, while C is from the recent pair of human papers and E is from the AI paper. Combining them (taking XORs of them on disjoint inputs) lets you create something like a coordinate-wise “max” and this gets you the other extrema.
As recently as the start of 2025, the picture looked like this:
So now here’s an actual animation over it over time.
You can see how we had to both constrain the shape from the outside and the inside.
This led me to the natural next question about how deterministic complexity, D, fits in here. It does not have all the pairwise exponents settled: we know that D ≲ R³, but we don’t know if it’s always ≲ R², and this is one of the oldest problems in query complexity. But putting that aside, we have a variety of data.
Vertices:
Vertices: eight known profiles and one unfilled outer vertex
| c | r | d | Construction |
|---|---|---|---|
| ½ | 1 | 1 | BKK |
| 1 | 1 | 1 | Parity |
| 1 | 1 | 2 | 2015 pointer function + Parity |
| 2 | 1 | 2 | BDK + Parity |
| 2 | 2 | 4 | 2015 pointer function |
| 2 | 4 | 4 | Quartic R/Q family, with the certificate estimate below |
| 4 | 2 | 4 | BDK |
| 4 | 4 | 4 | BDK XOR quartic family |
| 2 | 1 | 3 | Unfilled: this is not a known construction |
Faces:
Faces: eight proved outer facets and six inner-hull facets
The proved outer approximation has these eight facets:
| Universal bound | Exponent inequality | Reason |
|---|---|---|
| Q ≤ R | r ≥ 1 | Simulation |
| C ≤ D | c ≤ d | A deterministic computation supplies a certificate |
| R ≤ D | r ≤ d | Simulation |
| D ≤ C² | d ≤ 2c | D ≤ C₀C₁ ≤ C² |
| C ≲ R² | c ≤ 2r | C ≤ bs² and bs ≲ R |
| D ≲ CR | d ≤ c + r | D ≤ C·bs and bs ≲ R |
| D ≲ RQ² | d ≤ r + 2 | D ≤ bs·deg, bs ≲ R, deg ≲ Q² |
| D ≲ Q⁴ | d ≤ 4 | The quartic deterministic–quantum theorem |
The hull of the eight known profiles has six facets:
| Inner-hull facet | Universally proved? |
|---|---|
| Q ≤ R | Yes |
| C ≤ D | Yes |
| R ≤ D | Yes |
| D ≤ C² | Yes |
| D ≲ Q⁴ | Yes |
| D ≲ R² | Open |
Adding D ≲ R² makes C ≲ R², D ≲ CR and D ≲ RQ² redundant. The resulting outer polytope is exactly the known eight-vertex hull.
and that creates this cool 3D shape!
It still has a gap. As it turns out, the D vs R exponent in the range [2,3] is kind of the only gap still there. If there is a family of functions where D goes like R cubed, then we know exactly what it’s certificate complexity C and quantum complexity Q must do as well: it sits at a point (2,1,3) in the above (C,R,D) space, normalized by Q, which is to say that R and Q must be proportional while C is like R²; this is the only way D can grow like R³. So getting D ≍ R³ would fix the rest, and fill out the rest of the shape too; we’d be done.
Conversely, if it turns out that D is always at most R², then that adds a new face to the shape connecting four existing points, and would completely seal the shape too.
I hope this visualization was as fun for you to explore as it was for me!
1. up to polylog factors ↩︎