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.
Cite
@misc{OAI:A-Nearly-Quartic-Separation-Between-Randomized-and-Quantum-Query-Complexity-October-5-2026,
author = {{OpenAI}},
title = {{A Nearly Quartic Separation Between Randomized and Quantum Query Complexity}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/A-Nearly-Quartic-Separation-Between-Randomized-and-Quantum-Query-Complexity-October-5-2026/quartic-query-separation.pdf}{OAI:A-Nearly-Quartic-Separation-Between-Randomized-and-Quantum-Query-Complexity-October-5-2026}},
year = {2026}
}