Family 284Mathematical physicsNo LeanNot yet digested

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.

Manuscripts in this family · 1

A Nearly Quartic Separation Between Randomized and Quantum Query Complexity

Oct 5, 2026·quartic-query-separation.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.

Full abstract

PDF on GitHub LaTeX source