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.
Comments and reviews
No comments yet.
Discussed elsewhere
API
curl /api/v1/records/openai-math/A-Nearly-Quartic-Separation-Between-Randomized-and-Quantum-Query-Complexity
curl -X POST /api/v1/records/openai-math/A-Nearly-Quartic-Separation-Between-Randomized-and-Quantum-Query-Complexity/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/openai-math/A-Nearly-Quartic-Separation-Between-Randomized-and-Quantum-Query-Complexity/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'
The MathocalypseShtetl-OptimizedOct 7, 2026
A favorite problem of mine since 1998 (!), when we knew only that the optimal separating exponent was between 2 and 6. For the past few years, we knew it was between 3 and 4. So, this finally closes that story. A superquadratic separation between sensitivity and block sensitivity. Area law for 2D…