Search

The optimal quartic separation between randomized and quantum queries

Claims functions where randomized queries need nearly the fourth power of quantum queries, refuting a cubic conjecture.

1 paper October 5, 2026 Explained by AI

A query algorithm learns about a hidden input string by reading its bits one at a time. For some tasks a quantum algorithm needs far fewer reads than a randomized one. It was known that the randomized count is at most the fourth power of the quantum count, and experts conjectured the third power. This paper claims functions where the gap comes as close to the fourth power as you like. That would make the known bound optimal and the cubic conjecture false.

First step
2016
Scott Aaronson, Shalev Ben-David and Robin Kothari, cheat-sheet framework with a power 5/2 separation
Significance
Major
It settles the optimal power relating randomized and quantum query complexity for total functions.
Trust
Claimed, not checked
Field
Mathematical physics
1 paper

The explanation

Hide a string of one million bits and ask whether any bit is a 1. A randomized algorithm must read nearly all of them to be fairly sure. A quantum algorithm can do it with about a thousand reads, the square root of a million. This is Grover's search, and it is the basic quadratic speedup for this task. A read is called a query. The fewest queries needed, allowing error at most 1/3 on every input, is the query complexity. Write R for the randomized count and Q for the quantum count.

The task above is a total function: it has an answer for every possible string. For partial functions, defined only on some inputs, quantum speedups can be exponential. For total functions they cannot. The randomized count is at most a fixed power of the quantum count. Since 2021 that power was known to be at most four, building on Huang's sensitivity theorem. Those authors conjectured that the right power is three. Separations had climbed from power 5/2 to 3, up to logarithmic factors. The obstacle was to go beyond 3. Known constructions put certificates in an array, with the correct address found by solving smaller problems.

This paper claims the optimal power is exactly 4. For each whole number k of at least 2, it builds functions on about m bits. Their quantum count is near √m and their randomized count near m^(2 − 1/k), ignoring constants and logarithmic factors. Then R is near Q to the power 4 − 2/k. For k = 2 that power is 3. For k = 10 it is 3.8, and for k = 100 it is 3.98. Take m = 4¹⁰ = 1,048,576 and k = 10, still ignoring those factors. Then Q is near 1,024, and R is near m^1.9, about 2.7 × 10¹¹. That is far above Q³, about 1.1 × 10⁹, and below Q⁴, about 1.1 × 10¹². The family rules out every smaller power, including the conjectured cubic relation.

The construction extends the cheat-sheet idea. A winning column of the hidden array holds pointers out to a zero in every other column. Those zeros disqualify each rival. The quantum algorithm compares candidate witnesses, using tools like quantum minimum finding.

How sure is this? There is no Lean check; a computer proof checker has not looked at it. The upper bound of power 4 was already known. The new claim is the lower-bound family, whose randomized analysis is the hard part. No specialist review of the paper has been published.

What it doesn't show. This does not remove the logarithmic factors in the separation, and it does not reach the fourth power exactly.

Where it came from

This result comes from an unreleased OpenAI model, published in the openai/math release on 6 October 2026.

Hype check

Major if the proof holds. It closes the gap between the known quartic bound and the cubic conjecture, but there is no Lean check and no published specialist review.

Words used

Query
One read of one bit of the hidden input string.
Query complexity
The fewest reads an algorithm needs in the worst case to compute the answer with error at most 1/3.
Total Boolean function
A rule giving an answer 0 or 1 for every possible input string of bits.
Randomized algorithm
An ordinary algorithm that may flip coins to decide which bit to read next.
Separation
An example showing one measure can be much larger than another.
Logarithmic factor
A slowly growing extra factor such as log m, which changes the count but not the power.

The original paper

All quoted lines (5)
  1. Grover's search algorithm gives the basic quadratic speedup for the OR function, with a matching quantum lower bound.
    A Nearly Quartic Separation Between Randomized and Quantum Query Complexity Back to text
  2. They conjectured that randomized complexity satisfies the stronger relation R(f)=O(Q(f)3)\R(f)=O(\Q(f)^3).
    A Nearly Quartic Separation Between Randomized and Quantum Query Complexity Back to text
  3. The optimal power is αtot=4\alpha_{\mathrm{tot}}=4.
    A Nearly Quartic Separation Between Randomized and Quantum Query Complexity Back to text
  4. For each fixed integer k≥2k\ge2, there are positive constants ck,Ck,bkc_k,C_k,b_k and total Boolean functions Fk,mF_{k,m}, for all sufficiently large powers of four mm, such that Q(Fk,m)≤Ckm (log⁡m)bk,R(Fk,m)≥ckm2−1/k(log⁡m)2.\Q(F_{k,m})\le C_k\sqrt m\,(\log m)^{b_k}, \qquad \R(F_{k,m})\ge c_k\frac{m^{2-1/k}}{(\log m)^2}.
    A Nearly Quartic Separation Between Randomized and Quantum Query Complexity Back to text
  5. The contribution is the family in (…), which rules out every smaller power, including the conjectured cubic relation.
    A Nearly Quartic Separation Between Randomized and Quantum Query Complexity Back to text

Other sources

  1. openai/math release notes (2026): model provenance and review status manuscripts and supporting proof artifacts produced by an internal OpenAI model

Browse Mathematical physics Quantum theoryOpen since the 2010sClaimed, not yet checked