VibeMathedMath problems solved with AI
Sign in

Randomized versus quantum query complexity of total Boolean functions: is R(f) = O(Q(f)^3)?

For total Boolean functions the bounded-error randomized query complexity RR and quantum query complexity QQ are polynomially related: Beals et al. proved D=O(Q6)D=O(Q^6), and after Huang's sensitivity theorem Aaronson, Ben-David, Kothari, Rao and Tal proved D(f)=O(Q(f)4)D(f)=O(Q(f)^4), hence R=O(Q4)R=O(Q^4). The best separations were power 5/25/2 (cheat sheets), then 8/3−o(1)8/3-o(1) (Tal) and 3−o(1)3-o(1) (Bansal-Sinha; Sherstov-Storozhenko-Wu). Aaronson, Ben-David, Kothari, Rao and Tal conjectured that the cubic relation holds. Is R(f)=O(Q(f)3)R(f)=O(Q(f)^3) for every total Boolean function, or is the quartic exponent optimal?

Result
Disproved(see note)
Status
Candidate (review pending)
AI contribution
AI-discovered
Method
Construction
Field
Query complexity
Posed by
Scott Aaronson, Shalev Ben-David, Robin Kothari, Shravas Rao and Avishay Tal
Year posed
2021
Years open
5y
Solved
2026-10-05
Model
Unreleased internal OpenAI model
Vendor
OpenAI
Collaborators
—
Verification
Unreviewed
Publication
Announced
Collection
OpenAI math release (October 2026), version adc7f12
Significance
38 / 100
Disclosed cost
—
Wikipedia
No dedicated article

What was actually shown

Theorem 1.1: for each fixed k≥2k\ge2 there are total Boolean functions Fk,mF_{k,m} with Q(Fk,m)≤Ckm(log⁡m)bkQ(F_{k,m})\le C_k\sqrt m(\log m)^{b_k} and R(Fk,m)≥ckm2−1/k/(log⁡m)2R(F_{k,m})\ge c_km^{2-1/k}/(\log m)^2, a power 4−2/k4-2/k separation up to logarithms, so no bound R=O((1+Q)α)R=O((1+Q)^\alpha) holds with α<4\alpha<4. With the known R=O(Q4)R=O(Q^4) the optimal exponent is exactly 4, and the cubic conjecture is false. The functions are cheat-sheet-style columns whose certificate cells are addressed by answers to partial-function instances. Not shown: a separation with exponent exactly 4 for a single family, or new results for partial functions.

What the AI did

The release README says the results were produced by an unreleased internal OpenAI model with a fixed procedure, on average about three hours of ChatGPT Pro thinking compute per result, and that some outputs build on earlier model results. This result is not among the README's exceptions (the Hodge conjecture for CM abelian varieties and the Re(s) > 11/12 zero-free region). The manuscripts are authored 'OpenAI' and name no human author. The single manuscript (October 5, 2026) is the whole family.

Verification

No independent mathematician has checked this yet. Checked here: the abstract, introduction, Theorem 1.1 and the quantum upper-bound proposition were read against Conjecture 2 as the manuscript states it. The construction and its analyses (a quantum tournament lemma for candidate comparisons, an adaptive direct-product lower bound) were not refereed. No Lean formalization accompanies this manuscript. Both measures are worst-case bit-query counts with error at most 1/3 and unrestricted computation between queries, as the paper states.

Sources

Changelog1 change

Discussion