The optimal quartic separation between randomized and quantum queries. Shows that the universal bound $R(f)=O((1+Q(f))^4)$ for total Boolean functions is sharp in its exponent, ruling out every smaller power and disproving the conjectured cubic relation. Here R and Q are randomized and quantum worst-case bit-query complexities with error at most 1/3; computation between queries is unrestricted.
released 2026-10-05 | 2 theorems · 8 lemmas · 12 proofs · 8,116 words |
PLAY LEVEL 1 »(pdf)
We construct total Boolean functions with a nearly quartic separation between bounded-error randomized and quantum query complexity. Writing these complexities as $\mathrm R(f)$ and $\mathrm Q(f)$, the examples rule out every universal bound $\mathrm R(f)=O((1+\mathrm Q(f))^\alpha)$ with α < 4. Thus the known quartic upper bound has the optimal exponent, disproving the conjectured cubic bound. Both complexities count worst-case bit queries with error at most 1/3 on every input.