The optimal quartic separation between randomized and quantum queries

What OpenAI claims

Shows that the universal bound R(f)=O((1+Q(f))⁴) 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.

Paper

1. A Nearly Quartic Separation Between Randomized and Quantum Query Complexity

   5 October 2026 · Preprint, not peer reviewed · PDF

   We construct total Boolean functions with a nearly quartic separation between bounded-error randomized and quantum query complexity. Writing these complexities as R(f) and Q(f), the examples rule out every universal bound R(f)=O((1+Q(f))^α) 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.

Status

Preprint. The paper has not been independently reviewed. Treat the result as OpenAI's claim until other mathematicians have checked it. If a video exists, it illustrates the statement; it is not the proof.