Alex Meiburg / Timeroot

Quantum ⊕ Physics ⊗ Algorithms

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!

All five vertices are attained in exponent closure

11223344c = log C / log Qr = log R / log QR ≲ Q⁴C ≲ Q⁴R ≤ C²Q ≤ RC ≲ R²ABCDE
━ Proven outer bounds ■ Hull of known exponent limits
A (½, 1) · BKK B (2, 1) · BDK + Parity C (4, 2) · New C/Q gap D (4, 4) · XOR of C and E E (2, 4) · OpenAI family, k → ∞

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:

At the start of 2025

11223344c = log C / log Qr = log R / log Qc = 2c = rr = c + 1R ≲ Q⁴C ≲ Q⁴R ≤ C²Q ≤ RC ≲ R²ABCDE
━ Proven outer bounds ■ Hull of displayed 2025 constructions ○ Unfilled outer vertices
A (½, 1) · BKK B (1, 1) · Parity C (2, 2) · OR D (2, 3) · Cheat sheets + Forrelation E (1, 2) · Balanced AND–OR

So now here’s an actual animation over it over time.

Query complexity: the changing exponent region

Folklore. Baseline. Parity; Q ≤ R. The outer region is unbounded.. Outer region continues beyond the viewing window.01234512468Q ≤ RUnbounded · clippedPc = log C / log Qr = log R / log Q
━ Proved outer edges ┄ ■ Hull of known profiles ┆ Witness location unresolved ◇ Guaranteed hull point

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
crdConstruction
½11BKK
111Parity
1122015 pointer function + Parity
212BDK + Parity
2242015 pointer function
244Quartic R/Q family, with the certificate estimate below
424BDK
444BDK XOR quartic family
213Unfilled: 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 boundExponent inequalityReason
Q ≤ Rr ≥ 1Simulation
C ≤ Dc ≤ dA deterministic computation supplies a certificate
R ≤ Dr ≤ dSimulation
D ≤ C²d ≤ 2cD ≤ C₀C₁ ≤ C²
C ≲ R²c ≤ 2rC ≤ bs² and bs ≲ R
D ≲ CRd ≤ c + rD ≤ C·bs and bs ≲ R
D ≲ RQ²d ≤ r + 2D ≤ bs·deg, bs ≲ R, deg ≲ Q²
D ≲ Q⁴d ≤ 4The quartic deterministic–quantum theorem

The hull of the eight known profiles has six facets:

Inner-hull facetUniversally proved?
Q ≤ RYes
C ≤ DYes
R ≤ DYes
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!

Four query measures, three exponent coordinates

Drag to rotate. Tap a vertex or choose a vertex or facet in Inspect. Coordinate order is c, r, d. Orange marks an unproved candidate facet and the unfilled outer vertex.Open (2, 1, 3)crd123412341234
c = log C / log Qr = log R / log Qd = log D / log Q

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 ↩︎