# 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.

Canonical: https://closedform.nishachay.tech/e/openai-math-2026-284/
Last updated: 2026-10-14

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

**Trust:** Claimed, not checked · **Papers:** 1 · **First paper:** October 5, 2026 · **Field:** Mathematical physics · **Entry:** 284

*Explained by AI.* Drafted by one AI model and checked sentence by sentence against the paper by a different one. Spot a mistake? Report an error.

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.

## At a glance

- **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[1]. 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[2]. 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[3]. 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[4]. 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[5].

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

- [A Nearly Quartic Separation Between Randomized and Quantum Query Complexity](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) - October 5, 2026

## Quoted lines from the paper (5)

[1] From [A Nearly Quartic Separation Between Randomized and Quantum Query Complexity](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):

> Grover's search algorithm gives the basic quadratic speedup for the OR function, with a matching quantum lower bound.

[2] From [A Nearly Quartic Separation Between Randomized and Quantum Query Complexity](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):

> They conjectured that randomized complexity satisfies the stronger relation $\R(f)=O(\Q(f)^3)$.

[3] From [A Nearly Quartic Separation Between Randomized and Quantum Query Complexity](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):

> The optimal power is $\alpha_{\mathrm{tot}}=4$.

[4] From [A Nearly Quartic Separation Between Randomized and Quantum Query Complexity](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):

> For each fixed integer $k\ge2$, there are positive constants $c_k,C_k,b_k$ and total Boolean functions $F_{k,m}$, for all sufficiently large powers of four $m$, such that \begin{equation} \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}. \end{equation}

[5] From [A Nearly Quartic Separation Between Randomized and Quantum Query Complexity](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):

> The contribution is the family in (…), which rules out every smaller power, including the conjectured cubic relation.

## Other sources

- [openai/math release notes (2026): model provenance and review status](https://github.com/openai/math/blob/main/README.md): “manuscripts and supporting proof artifacts produced by an internal OpenAI model”

## Related

- [Classical capacity of generalized amplitude damping](https://closedform.nishachay.tech/e/openai-math-2026-276/) - Mathematical physics
- [Polynomial-time unitary synthesis from a Boolean oracle](https://closedform.nishachay.tech/e/openai-math-2026-283/) - Mathematical physics
- [Exact quantum factoring over a fixed finite gate set](https://closedform.nishachay.tech/e/openai-math-2026-279/) - Mathematical physics
- [Parity is not in QAC 0](https://closedform.nishachay.tech/e/openai-math-2026-274/) - Mathematical physics
- [Bloch's law, its lattice correction, and the spherical magnetization law](https://closedform.nishachay.tech/e/openai-math-2026-271/) - Mathematical physics
- [Mathematical physics](https://closedform.nishachay.tech/science/mathematics/mathematical-physics/) - Field · 25 results
- [Quantum theory](https://closedform.nishachay.tech/topic/quantum/) - Topic · 9 results
- [Open since the 2010s](https://closedform.nishachay.tech/open-since/2010s/) - Era · 31 results
- [Claimed, not yet checked](https://closedform.nishachay.tech/trust/claimed/) - Trust · 130 results
- [Report an error](https://github.com/nishachay/closed-form/issues/new?template=report-error.yml&labels=entry-error&title=%5Bentry%20284%5D%20)