Browse › Mathematical physics › 284 The optimal quartic separation between randomized and quantum queries
A Nearly Quartic Separation Between Randomized and Quantum Query Complexity
Open PDFCite Report a problem Add a reference or comment Interested in working on this Start a discussion
Edit NOTES.md · Existing issues · Source on GitHub
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.
If the PDF does not display here, open it directly: Open PDF.
Notes
No notes yet. Add a reference, a comment or your name with the buttons above, or edit NOTES.md on GitHub.
Automatically collected notes (unreviewed)
work in progress
Collected automatically by AI tools (Claude Opus 5.5 and GPT-6 Astra, 2026-10-21) and not checked by a person. May be wrong or incomplete. Report an error.
Related prior literature mentioned by others
- Scott Aaronson, Shalev Ben-David, Robin Kothari, Shravas Rao and Avishay Tal, Degree vs. Approximate Degree and Quantum Implications of Huang's Sensitivity Theorem (arXiv:2010.12629, 2020-10-23; STOC 2021). Identified in Yesterday in AI as the source of the cubic conjecture challenged by this manuscript, it establishes the quartic bound $D(f)=O(Q(f)^4)$ used in Theorem 1.1; this bound first appeared in the earlier preprint arXiv:2004.13231 (Aaronson, Ben-David, Kothari, Tal), which the paper does not cite.
- Nikhil Bansal and Makrand Sinha, k-Forrelation Optimally Separates Quantum and Classical Query Complexity (arXiv:2008.07003, 2020-08-16). The Open Mathematics Courses exposition identifies this Forrelation lower bound as the external hypothesis used in its treatment of the manuscript's randomized lower bound.
Possibly relevant literature (found by the agent, not checked)
- Shalev Ben-David, A Super-Grover Separation Between Randomized and Quantum Query Complexities (arXiv:1506.08106, 2015). Gives $R(f)=\tilde\Omega(Q(f)^{5/2})$ for a total function independently of the cheat-sheet paper (and power 3 under the Aaronson–Ambainis conjecture), relevant to the introduction's history of the exponent, which credits power 5/2 only to [ABK16]; not in the bibliography.
Digests and expositions
- Open Mathematics Courses / Claude Opus 5.5, Randomized versus quantum query complexity (October 2026). A six-lesson exposition of the outward-pointer construction, probabilistic tournament, randomized lower bound and quartic upper bound, retaining the Bansal–Sinha Forrelation lower bound as an external hypothesis and stating that independent review is incomplete. [AI-generated per source]
News and blogs
- Mint Research, Yesterday in AI · 9 October 2026 (2026-10-09). Reports on Aaronson's response, explains the manuscript's claimed refutation of the cubic conjecture, and distinguishes reading its abstract and introduction from independently checking its proof. [AI-generated per source]
Elsewhere
- VibeMathed: Problem record
- Emergent Mind: family 284
Independent sites; their content is not reviewed here.
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}
}Family 284: The optimal quartic separation between randomized and quantum queries
Shows that the universal bound $R(f)=O((1+Q(f))^4)$ for total Boolean functions is sharp in its exponent, ruling out every smaller power and disproving the conjectured cubic relation. Here R and Q are randomized and quantum worst-case bit-query complexities with error at most 1/3; computation between queries is unrestricted.
This is the only paper in this family.