Nearly a fourth power, proved at last?
An AI preprint claims the quartic ceiling between randomized and quantum queries cannot be lowered
Covers result 284 in OpenAI’s catalog: its one paper. See its connections to other results and the work it cites.
3:27. English captions available. The video loads from YouTube when you press play.
Chapters
The claim, in plain words
Imagine computing a yes-or-no function of a hidden string of bits, reading one bit per query. To check whether any bit is a one, a deterministic reader needs all n bits, and a randomized reader allowed to err a third of the time still needs about half of them; Grover’s quantum search needs only about √n. For total functions, defined on every input, the savings are limited: in 2020 Aaronson, Ben-David, Kothari, Rao and Tal proved, building on Huang’s sensitivity theorem, that even deterministic query complexity is at most a constant times the fourth power of quantum query complexity. In the same paper they conjectured that the third power is the truth. The best separations had crept up from 2 to 2.5, then 8/3, and to 3 in 2020, leaving a window between 3 and 4.
Result 284 is one OpenAI preprint, 19 pages, dated October 5, 2026. It claims the fourth-power ceiling cannot be lowered. For each k it builds explicit total functions whose randomized cost is at least the quantum cost to the power 4 − 2/k, up to logarithmic factors: 3 for k = 2, 3.5 for k = 4, and approaching 4. That disproves the cubic conjecture.
What it doesn’t claim
One function reaching the fourth power exactly, explicit constants, or anything new for deterministic or zero-error randomized queries, where quartic gaps up to logarithms were already known. The functions are astronomically large: with about 1,000 columns, the input already has around 1071 bits.
Where it stands
- Posted as a preprint
- OpenAI, 19 pages, dated October 5, 2026
- Peer reviewed
- Not yet
- Checked in Lean
- No
Last checked October 19, 2026. The preprint has not been revised. There is no Lean formalization. Scott Aaronson, a co-author of the cubic conjecture, called it a favorite problem since 1998 and wrote, “this finally closes that story.” OSVerify has not reviewed it, and we found no other comment from specialists.
How the proof goes
- Columns, puzzles and a certificate. The construction has many columns, each a bit string plus a block of Forrelation puzzles, which quantum computers answer in a few queries and classical ones only with many. The answers form an address pointing to a cell that holds a certificate. A column wins if its string is all ones, its certificate checks out, and its cell points to a zero in every other column, so at most one column can win.
- A tournament, then a search. The quantum algorithm runs a tournament before its final search. Columns are compared in pairs, and the true winner beats everyone, because no rival can point to a zero in a string of all ones. Comparison ideas of this kind appeared weeks earlier, in work by Ambainis, Iraids and Kokainis and by Ben-David and Kothari, both made with help from AI tools.
The numbers in the video
- Ours: Grover’s search on 64 items succeeds with probability 0.9966 after 6 rounds, then falls.
- Ours: in a simulation of the ideal tournament weighting, the winner was never lost in 2,000 runs, even with coin-flip or rock-paper-scissors matches among the others.
- Ours: with 1,024 columns, the construction’s input has around 1071 bits.
Read the source
- A Nearly Quartic Separation Between Randomized and Quantum Query Complexity (PDF), 19 pages.
- The collection’s catalog, where this is result 284.
The paper
OpenAI groups related papers into one result; this one has a single paper.
Transcript
Read the full script
0:00The question
Imagine computing a yes-or-no function of a hidden string of bits, reading one bit per query. How many queries does it take? To check whether any bit is a one, a deterministic reader needs all n bits, and a randomized reader allowed to err a third of the time still needs about half of them. Grover’s quantum search needs only about the square root of n. Our computer runs it on 64 items: success peaks at 99.7% after 6 rounds, then falls. For total functions, defined on every input, the quantum savings are limited. In 2020, Aaronson, Ben-David, Kothari, Rao and Tal proved, building on Huang’s sensitivity theorem, that even deterministic query complexity is at most a constant times the fourth power of quantum query complexity. In the same paper they conjectured that the third power is the truth. The best separations had crept up from 2, with Grover’s search, to 2.5, then 8/3, and to 3 in 2020, leaving a window between 3 and 4.
1:06The claims
Result 284 is one OpenAI preprint, 19 pages, dated October 5, 2026. It claims the fourth-power ceiling cannot be lowered. For each k it builds explicit total functions whose randomized cost is at least the quantum cost to the power 4 − 2/k, up to logarithmic factors: 3 for k = 2, 3.5 for k = 4, and approaching 4. That disproves the cubic conjecture. Not claimed: one function reaching the fourth power exactly, explicit constants, or anything new for deterministic or zero-error randomized queries, where quartic gaps up to logarithms were already known. The functions are astronomically large. Our computer finds that with about 1,000 columns, the input already has around 10⁷¹ bits.
1:56How the proof goes
The construction has many columns, each a bit string plus a block of Forrelation puzzles, which quantum computers answer in a few queries and classical ones only with many. The answers form an address pointing to a cell that holds a certificate. A column wins if its string is all ones, its certificate checks out, and its cell points to a zero in every other column, so at most one column can win. The quantum algorithm runs a tournament before its final search. Columns are compared in pairs, and the true winner beats everyone, because no rival can point to a zero in a string of all ones. In our simulation of the ideal weighting process, the winner was never lost in 2,000 runs, even when the other matches were coin flips or rock-paper-scissors cycles. Comparison ideas of this kind appeared weeks earlier, in work by Ambainis, Iraids and Kokainis and by Ben-David and Kothari, both made with help from AI tools.
2:55Where it stands
The preprint is unrefereed and unchanged since release, with no Lean formalization. Aaronson, a co-author of the cubic conjecture, called it a favorite problem since 1998 and wrote, “this finally closes that story”. OSVerify has not reviewed it, and we found no other comment from specialists. If it holds, for total functions, quantum queries can shrink to nearly the fourth root of randomized queries, and no further.
Spot a mistake?
This episode simplifies on purpose, but it shouldn’t be wrong. If something is, open an issue on GitHub or leave a comment on YouTube. Corrections are noted here with a date.