A Nearly Quartic Separation Between Randomized and Quantum Query Complexity
OpenAI
Abstract
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.