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.