A Nearly Quartic Separation Between Randomized and Quantum Query Complexity

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.