View source for Randomized versus quantum query complexity

'''Randomized versus quantum query complexity''' asks how much fewer input bits a quantum algorithm can read than a bounded-error randomized algorithm when both compute the same total Boolean function. It is known that the randomized cost is at most a constant times the fourth power of the quantum cost; a 2021 paper conjectured that the third power suffices. A manuscript dated 5 October 2026 in OpenAI's public mathematics collection ([https://github.com/openai/math github.com/openai/math]) claims functions that come arbitrarily close to the fourth power, so that the exponent 4 is optimal and the cubic conjecture fails. This page summarizes the published claim and lists publicly available follow-up work. Statements are the respective authors' claims; the publication of a paper is not presented here as independent verification.

== Background ==
* As recounted in the introduction of the manuscript:
** Grover's search gives a quadratic quantum speedup for the OR function, with a matching lower bound. Beals, Buhrman, Cleve, Mosca and de Wolf proved that deterministic query complexity is at most the sixth power of quantum query complexity for every total function, so totality rules out exponential speedups but leaves a range of possible powers.
** Pointer functions of Göös, Pitassi and Watson, developed by Ambainis, Balodis, Belovs, Lee, Santha and Smotrovs, gave a nearly quartic separation between deterministic and quantum queries. For bounded-error randomized queries, Aaronson, Ben-David and Kothari introduced cheat sheets and obtained power 5/2 up to logarithmic factors; Tal improved this to 8/3 − o(1), and Bansal and Sinha and, independently, Sherstov, Storozhenko and Wu reached 3 − o(1).
** Aaronson, Ben-David, Kothari, Rao and Tal used Huang's sensitivity theorem to prove that deterministic query complexity is at most a constant times the fourth power of quantum query complexity, and conjectured that randomized query complexity is at most a constant times its third power.

== The original result ==
* '''Claim.''' Theorem 1.1 of ''A Nearly Quartic Separation Between Randomized and Quantum Query Complexity'' states that the optimal power is 4. For each fixed integer ''k'' ≥ 2 it constructs total Boolean functions ''F''<sub>''k'',''m''</sub> whose quantum query complexity is at most a constant times √''m'' up to a polylogarithmic factor and whose bounded-error randomized query complexity is at least a constant times ''m''<sup>2 − 1/''k''</sup>/(log ''m'')<sup>2</sup>. Hence no bound of the form ''R''(''f'') = ''O''((1 + ''Q''(''f''))<sup>''α''</sup>) with ''α'' &lt; 4 holds, and the conjectured cubic relation is false. Both complexities count worst-case bit queries with error at most 1/3 on every input; the universal quartic upper bound is the known one, with a self-contained proof in an appendix.
* ''Method, as described:'' the input has ''m'' columns, each with a bit string and an array of certificate cells; the address of the relevant cell is the vector of answers to several instances of a Forrelation-type partial function, cheap for quantum and hard for classical algorithms. A column wins if its string is all ones and its correctly addressed certificate points to a zero in every other column, so at most one column wins. A quantum tournament whose comparisons need to be reliable only when they involve the winner produces a short list containing the winner; a randomized lower bound plants a winner in a random column and uses a direct-product argument. The only external lower-bound input is the Forrelation theorem.
* '''Source''' (openai/math repository, commit <code>7ef5c0c</code>): [https://github.com/openai/math/tree/7ef5c0cc5ca4b0e072b7a050fca09ab24bc6fa3a/preprints/A-Nearly-Quartic-Separation-Between-Randomized-and-Quantum-Query-Complexity-October-5-2026 A Nearly Quartic Separation Between Randomized and Quantum Query Complexity], dated 5 October 2026.
* '''Formalization.''' The repository has no Lean scope note for this family.

== Public follow-up work ==
{| class="wikitable"
! Date !! Work !! Relation !! Public claim !! Public status (checked 29 October 2026)
|-
| 2026-10-07 || S. Aaronson, [https://scottaaronson.blog/?p=10169 ''The Mathocalypse''], a post on the blog ''Shtetl-Optimized'' || Remark (blog post) || Lists the result among the claims of the release and writes that it had been a favorite problem of his since 1998, when the optimal separating exponent was known only to lie between 2 and 6, that for the past few years it was known to lie between 3 and 4, and that "this finally closes that story". Aaronson is a co-author of the 2021 paper whose cubic conjecture the manuscript disproves. || Blog post of 7 October 2026; it does not report a check of the proof. Read on 29 October 2026.
|-
| 2026-10-07 || [https://lowrank.github.io/latent-seminar/OpenAI-Math/284-quartic-randomized-quantum-queries ''Nearly quartic quantum query speedups: addressed witnesses and probabilistic tournaments''], an article of the Latent Seminar blog at lowrank.github.io || Reading (exposition) || Explains the construction: a hard address bit with an exact verifier, the total addressed-certificate function, a tournament with probabilistic comparisons, adaptive address guessing, a planted winner with indistinguishable transcripts, and why the matching exponent is four. || Blog article; it states that its review covers statements, introductions and selected proof mechanisms and is not an independent verification of the complete proofs.
|-
| 2026-10-13 || [https://kokunoyumeto.github.io/open-math-courses-public/courses/randomized-versus-quantum-query-complexity/ ''Randomized versus quantum query complexity''], a course on Open Mathematics Courses ([https://github.com/kokunoyumeto/open-math-courses-public kokunoyumeto/open-math-courses-public]) || Reading (exposition) || Six lessons: query complexity and a function with outward pointers, the quantum query model, amplitude amplification and the Forrelation test, a tournament with probabilistic comparisons, the randomized lower bound, and the quartic upper bound with the optimal exponent. The randomized lower bound is presented with one named hypothesis, the Forrelation lower bound of Bansal and Sinha. || The course states that it was written and self-checked by Claude Opus 5.5 (Anthropic) and that independent review is not complete.
|-
| 2026-10-16
| J. Jardine, Lattice24, referee review [https://github.com/JJardine919/openai-math-audit/blob/a06a8c6e77974d4c6021338a55a8e91b634f67f7/reviews/rank_527.json rank_527] in [https://github.com/JJardine919/openai-math-audit JJardine919/openai-math-audit] (archived at [https://doi.org/10.5281/zenodo.23422995 Zenodo 10.5281/zenodo.23422995])
| Review (AI-assisted audit)
| Reports no gap. The reviewer read the construction, the quantum tournament and its error accounting, and the classical lower bound. Its one minor note: it could not check offline the exact thresholds of the cited Bansal–Sinha theorem used in Lemma 2.1, and states that a mismatch would change only constants and logarithmic factors.
| Part of an audit of the collection's manuscripts without Lean that the audit describes as complete. The reviews are published under CC BY 4.0.
|-
| 2026-10-18 || ''AI Proved What?'', episode 284 [https://aiprovedwhat.com/episodes/284-quartic-separation/ Nearly a fourth power, proved at last?], remade version of 23 October 2026 || Reading (exposition) || Video explainer of the claim that for each ''k'' there are total functions whose randomized cost is at least their quantum cost to the power 4 − 2/''k'' up to logarithmic factors, which disproves the cubic conjecture. The episode states that one function reaching the fourth power exactly, explicit constants, and anything new for deterministic or zero-error randomized queries are not claimed, and that the functions are astronomically large. || Web page and video; the site states that its scripts and animations are produced with AI assistance and that the narration is an AI-generated voice. Status record last checked 27 October 2026: posted as a preprint: OpenAI, 19 pages, dated October 5, 2026; under expert review: not yet; peer reviewed: not yet; checked in Lean: no. The page also quotes Aaronson's comment above and states that OSVerify has not reviewed the result and that it found no other comment from specialists.
|}

== Notes ==
* The background summarizes the manuscript's own account of earlier work. The agent-collected notes of the community revision [https://github.com/mathcommunity/oai-math-revised mathcommunity/oai-math-revised] point out that S. Ben-David's preprint ''A Super-Grover Separation Between Randomized and Quantum Query Complexities'' ([https://arxiv.org/abs/1506.08106 arXiv:1506.08106], June 2015) also gave a total function with a power-5/2 separation, up to logarithmic factors; its abstract confirms this, and the manuscript's bibliography does not include it.
* The list covers follow-ups found in public sources up to the date above; it is not a priority or completeness claim.

[[Category:OpenAI results]]