Nearly quartic quantum query speedups: addressed witnesses and probabilistic tournaments

Source and verification

This article explains family 284 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

Overview

For a total Boolean function, how large can the advantage of quantum queries over randomized classical queries be? Family 284 constructs examples approaching a fourth-power separation. Its mechanism combines hard-to-guess certificate addresses, outward-pointing witnesses, and a quantum tournament that works even when comparisons between unsuccessful candidates are unreliable. The claimed new separation matches the exponent in the known universal quartic upper bound. (OpenAI, 2026)

🏷️ Preliminaries: total functions and query complexity

A total Boolean function assigns an output to every bit string of a fixed length. A partial function is defined only on a promised subset. An algorithm for a partial function need only be correct on that subset.

For $f:\{0,1{\}}^N\to \{0,1\}$, write $R(f)$ and $Q(f)$ for its bounded-error randomized and quantum query complexities. Both require error at most $1/3$ on every input and count the worst-case number of queried bits, including over random choices and measurement outcomes. Computation between queries is unrestricted.

A quantum bit query acts as $|i,b,z⟩\mapsto |i,b\oplus x_i,z⟩$, allowing a superposition of indices. This is a query model, not a claim about time needed to implement arbitrary intervening computation or access a physical memory.

The prerequisites are probability, linear algebra, Boolean decision trees, and basic quantum search. The construction uses a partial problem as a building block, but verifies every proposed certificate so that the final function is total.

The manuscript's nearly quartic family

For each fixed integer $k\ge 2$, there are total functions $F_{k,m}$, for sufficiently large powers of four $m$, with

$$\begin{array}{c}Q(F_{k,m})\le C_k\sqrt{m}(\log m{)}^{b_k},\\ R(F_{k,m})\ge c_k\frac{m^{2-1/k}}{(\log m{)}^2}.\end{array}$$

Consequently every universal inequality $R(f)\le C_{\alpha }(1+Q(f){)}^{\alpha }$ must have $\alpha \ge 4$. The known quartic upper bound shows that four is the optimal exponent. (OpenAI, 2026)

The parameter $k$ stays fixed as $m$ tends to infinity. The theorem identifies the optimal power, without claiming an exact logarithmic correction or a single family with a constant-factor $R=Q^4$ relation.

🏷️ A hard address bit with an exact verifier

The address-building problem is $k$-fold Forrelation. Let $H$ be the normalized Walsh–Hadamard matrix of order $m$, let $u=m^{-1/2}(1,\dots ,1{)}^{\mathsf{T}}$, and let $D_z$ be diagonal with sign vector $z$. Define

$$\begin{array}{c}\Phi =u^{\mathsf{T}}{D}_{z_1}H{D}_{z_2}H\cdots H{D}_{z_k}u,\\ \delta =2^{-5k}.\end{array}$$

The partial function $P$ equals one when $\Phi \ge \delta$, equals zero when $|\Phi |\le \delta /2$, and is undefined otherwise. For fixed $k$, the source imports a Forrelation lower bound implying

$$R(P)>L,L=\lfloor \frac{m^{1-1/k}}{({\log }_{2}m{)}^2}\rfloor$$

for large $m$. This external lower bound is the construction’s substantive imported hardness input.

Quantumly, prepare $u$, apply the displayed unitary product, and test projection back onto $u$. The probability is ${\Phi }^2$, separated by a fixed gap depending on $k$ between the two promise cases. Repetition gives error $\eta$ with $O_k(1+\log (1/\eta ))$ queries. The routine still has a fixed query cap and outputs a bit off promise; its answer there need not mean anything.

There is also a small exact classical circuit checking the promise and answer. Since $m$ is a power of four, the unnormalized Walsh transforms compute an integer numerator for $\Phi$ with integer denominator $m(\sqrt{m}{)}^{k-1}$. A butterfly computation uses $O(m\log m)$ additions on $O_k(\log m)$-bit integers. Exact threshold comparisons therefore give a fan-in-two Boolean circuit of size $S=O_k(m(\log m{)}^2)$, with outputs indicating whether $P$ is defined and, if so, its value.

This circuit is used for verification, not for the cheap quantum proposal of an address.

🏷️ The total addressed-certificate function

The input has $m$ columns. Column $i$ contains a string $X_i$ of $m$ bits, together with $r=\lceil 20{\log }_{2}m\rceil$ independent slots for Forrelation inputs $A_{i,h}$. No promise is imposed on these input bits.

It also has a certificate cell $B_{i,s}$ at every $r$-bit address $s$. Each cell stores a pointer to one position in every other string $X_j$, and proposed evaluation transcripts for the exact circuits on all $A_{i,h}$. A transcript lists the non-input gate values; verification reads the actual input bits where needed.

A column is a winner precisely when:

• Its string $X_i$ is all ones.
• Every $P(A_{i,h})$ is defined.
• At the true address $s_i=(P(A_{i,1}),\dots ,P(A_{i,r}))$, every circuit transcript is correct and each pointer hits a zero in the corresponding other column.

The total function $F_{k,m}$ is one exactly when a winner exists. A winner is unique: its outward pointers certify a zero in every other column.

For a specified pair $(i,s)$, all these conditions reduce to

$$\begin{array}{c}K=m+(m-1)+r(S+2)\\ =O_k(m(\log m{)}^3)\end{array}$$

exact local tests. A gate-consistency test reads at most three bits; a pointer test reads $O(\log m)$ bits. Hence each test costs $O(\log m)$ queries and can be evaluated coherently. A nonwinner has a failing test at every address, including addresses proposed by off-promise quantum computations.

🏷️ A tournament with probabilistic comparisons

A true winner can disqualify any other column using its own outward pointer. Conversely, no pointer in any opponent’s cell can hit a zero in the winner’s all-one string. Thus a comparison can favor the winner reliably without requiring the opponent’s Forrelation inputs to satisfy their promises.

The source formalizes this with comparison probabilities $a_{ij}$. The same circuit is used for each unordered pair, so

$$a_{ij}+a_{ji}=1(i\ne j),a_{ii}=0.$$

There is no transitivity assumption, nor any accuracy requirement on comparisons between two nonwinners. Suppose a distinguished candidate $i_{\ast }$ has $a_{i_{\ast }j}\ge 1-ϵ$ for every other $j$.

The ideal sampling process starts with weights $w_i=1$. When $W={\sum }_i{w}_i>0$, it samples a pivot $p$ with probability $w_p/W$ and updates $w_i$ to $w_i{a}_{ip}$. If $W=0$, it keeps all weights zero and leaves the list unchanged. For positive $W$, complementarity gives the exact drift

$$\mathbb{E}[W_{\mathrm{new}}\mid w]=\frac{W^2-{\sum }_i{w}_i^2}{2W}\le \frac{W}{2}.$$

After $T=\lceil {\log }_2(1000m)\rceil$ stages, $\mathbb{E}{W}_T\le m/2^T$. Choose $ϵ=1/(1000T)$. If the distinguished candidate has not yet been selected, its weight remains at least $(1-ϵ{)}^T>1/2$. Markov’s inequality bounds the probability of missing it in the ideal list by $2m/2^T$.

The quantum algorithm never calculates these fractional weights. It prepares a uniform candidate and compares it with every previous pivot in fresh workspaces, retaining all garbage. Conditional on candidate $i$, the probability of defeating every pivot is exactly the product defining $w_i$. Thus conditioning on the success flag samples the desired distribution $w_i/W$.

Bounded amplitude amplification raises the probability of obtaining a successful sample while preserving its entire normalized successful state. A fixed mixture of amplification lengths and a fixed number of trials gives a worst-case cost cap. Before the winner is selected, success probability is at least $1/(2m)$, so a stage fails with probability at most $ϵ$.

Coupling each stage conditional on its full previous history to the ideal process adds at most $Tϵ$ to the miss probability. With comparison cost $c$, the query cost is $O(c\sqrt{m}{T}^2\log T)$ on every branch, even when no distinguished winner exists.

🏷️ Applying the tournament and verifying its list

Decode each column’s $r$ address bits with total error at most $ϵ$ when all its instances are promised. For a pair of columns, inspect their pointers toward each other at the proposed addresses. If exactly one points to a zero in its opponent, declare that column victorious; otherwise choose the smaller index. Retained address registers make these probabilities the ordinary probabilities of the proposed classical outcomes.

A winner always resists disqualification, and its correctly decoded address disqualifies every opponent. Thus it satisfies the tournament hypothesis, regardless of off-promise inputs elsewhere. Each comparison has polylogarithmic query cost.

The resulting list contains at most $T$ candidates. Decode each candidate afresh and quantumly search its $K$ exact tests for a failure. A nonwinner is falsely accepted with probability at most $ϵ$; a winner is accepted whenever its address is decoded correctly, since no failed test exists then.

The zero-input error is at most $Tϵ$. The one-input error is at most $2m/2^T+Tϵ+ϵ<1/3$. The combined search and verification costs give $Q(F_{k,m})\le \sqrt{m}(\log m{)}^{O_k(1)}$ on all inputs.

🏷️ Adaptive address guessing

For the classical lower bound, finite minimax applied to $R(P)>L$ supplies a distribution $\mu$ on promised inputs under which every deterministic depth-$L$ decision tree succeeds with probability at most $2/3$.

For $r$ independent samples, an adaptive algorithm making at most $L$ queries to each sample guesses the entire answer vector with probability at most $(2/3{)}^r$. Interleaving queries among samples and receiving independent side information do not invalidate this bound.

The proof uses the full transcript. Conditional on a fixed transcript, the input samples remain independent under their respective observed-bit constraints: every tuple satisfying those constraints follows the same adaptive query schedule. Let $V_h$ be the best conditional success probability on sample $h$ with its remaining budget. A query to $h$ satisfies $\mathbb{E}[V_h^{\prime }\mid \tau ]\le V_h$; other values remain unchanged. Therefore ${\prod }_h{V}_h$ is a supermartingale, initially at most $(2/3{)}^r$, and bounds the final joint guessing probability.

This argument is applied to a capped simulator. It avoids conditioning on a column being selected for unusually few queries, which could bias its answer distribution.

🏷️ A planted winner and indistinguishable transcripts

Construct a dummy zero-input by putting one independently uniform hidden zero $J_i$ in each $X_i$, sampling all address instances from $\mu$, and leaving every certificate cell blank. Independently choose a uniform column $I$. Make a coupled one-input by erasing its zero and filling its true-address cell with correct transcripts and pointers to the other hidden zeros.

The two executions of a fixed algorithm are identical until it queries either the erased zero or the filled cell. Let its worst-case query budget be $G=\lfloor mL/100\rfloor$.

The expected number of discovered zeros is at most $4G/m$. Before half a column has been queried, a new query finds its zero with probability at most $2/m$; afterwards each such column has already consumed at least $m/2$ queries. Since $I$ is independent and uniform, the chance of querying the erased zero is at most $4G/m^2$.

Call a column heavy if it receives more than $L$ total queries to its $r$ address inputs. At most $G/L$ columns are heavy, so $I$ is heavy with probability at most $G/(mL)$.

For each fixed column and query time, simulate the dummy execution while aborting before its $(L+1)$st total address-input query in that column. Give the simulator all other dummy information for free; it is independent of the target inputs. If the proposed query visits a certificate cell, use its address as the guess for the $r$ answers.

Whenever that time visits the true cell in a nonheavy column, the simulator guesses correctly. The adaptive-product bound applies to this joint event, without conditioning on nonheaviness. Union bounding over query times and averaging over $I$ bounds the probability of reaching the planted cell by $G/(mL)+G(2/3{)}^r$.

The output distributions can consequently differ by at most

$$\frac{4G}{m^2}+\frac{G}{mL}+G(2/3{)}^r<\frac{1}{3}$$

for large $m$. Correctness with error at most $1/3$ on both inputs would require a difference at least $1/3$. Fixing and then averaging random coins gives the same contradiction for randomized algorithms, proving the claimed lower bound.

🏷️ Why the matching exponent is four

Fix $0\le \alpha <4$ and then choose a fixed $k$ with $2-1/k>\alpha /2$. The family bounds imply

$$\begin{array}{c}\frac{R(F_{k,m})}{(1+Q(F_{k,m}){)}^{\alpha }}\\ \ge c_{k,\alpha }\frac{m^{2-1/k-\alpha /2}}{(\log m{)}^{2+\alpha b_k}}⟶\infty .\end{array}$$

The positive power dominates all logarithms, excluding every smaller universal exponent.

The source also explains the known upper bound. Let $\mathrm{bs}(f)$ be the maximum number of disjoint sensitive blocks at an input, $\mathrm{deg}(f)$ the exact real multilinear degree, and $\lambda (f)$ the norm of the sensitivity graph’s adjacency matrix. Spectral adversary arguments give $\mathrm{bs}(f)=O(Q(f{)}^2)$ and $\lambda (f)=O(Q(f))$.

Huang’s signed-cube method yields $\mathrm{deg}(f)\le \lambda (f{)}^2$: a highest-degree restriction correlates with parity, giving a set larger than half a cube whose induced edges are sensitivity edges. A signed adjacency matrix squaring to $dI$ supplies a Rayleigh quotient at least $\sqrt{d}$ on that set.

Finally, a deterministic algorithm repeatedly queries a maximum-degree monomial. At a fixed actual input each round contains a sensitive block, and different rounds use disjoint coordinates. Hence $D(f)\le \mathrm{bs}(f)\mathrm{deg}(f)$, so $R(f)\le D(f)=O(Q(f{)}^4)$ for nonconstant total functions. The additive one covers constant functions.

🏷️ Reading and verification scope

The main file and all six principal sections, including the upper-bound appendix, were read. The tournament distribution, worst-case amplification cap, adaptive direct-product argument, planted-input coupling, and order of asymptotic parameters were checked against the source. The imported Forrelation lower bound and other external references were not independently audited. No quantum circuit was implemented.

🏷️ Key steps and proof outlines

Amplifying an unknown success probability without biasing the pivot

The tournament requires a sample from its exact fractional-weight distribution. Ordinary statements that amplification “finds a good candidate” do not guarantee this. Write the complete preparation as

$$A|0⟩=\sin \theta |g⟩+\cos \theta |b⟩,$$

where $|g⟩$ includes every successful candidate and its retained comparison workspace. After $\ell$ Grover iterations, only the two scalar coefficients change:

$$\sin ((2\ell +1)\theta )|g⟩+\cos ((2\ell +1)\theta )|b⟩.$$

Thus every successful measurement gives the same normalized vector $|g⟩$, up to global phase. Randomizing the iteration count cannot bias the measured candidate.

For a promised lower bound $p={\sin }^2\theta \ge \gamma$, take $M=\lceil 10/\sqrt{\gamma }\rceil$. A trial chooses with equal probability either zero iterations or a uniformly random $\ell <M$. If $p\ge 1/2$, the zero-iteration choice succeeds with probability at least $1/4$. If $\gamma \le p\le 1/2$, then $\sin (2\theta )\ge \sqrt{\gamma }$, and summing the geometric progression gives

$$\frac{1}{M}\sum _{\ell =0}^{M-1}{\sin }^2((2\ell +1)\theta )\ge \frac{1}{2}-\frac{1}{2M|\sin (2\theta )|}\ge \frac{9}{20}.$$

Every trial therefore has success probability at least $9/40$. A fixed number $O(\log (1/\eta ))$ of fresh trials makes failure at most $\eta$. This proves both the capped cost and preservation of the pivot law. If no winner exists, the success promise may fail, but the cost cap remains intact. (OpenAI, 2026)

The signed cube explains the fourth-power upper-bound exponent

The matching upper bound uses an exact spectral construction. Let $d=\mathrm{deg}(f)$, choose a nonzero degree-$d$ monomial, and fix all other variables. Its coefficient survives because any additional monomial contributing to it would have degree larger than $d$. The restricted sign function consequently correlates with parity. After choosing a sign, its parity-agreement set $U$ contains more than half of the $d$-cube, and every cube edge inside $U$ is a sensitivity edge.

Define the signed adjacency matrices recursively:

$$H_1^{\prime }=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right),H_{j+1}^{\prime }=\left(\begin{array}{cc}{H}_j^{\prime }& I\\ I& -H_j^{\prime }\end{array}\right).$$

The off-diagonal terms cancel when squaring, so $(H_d^{\prime }{)}^2=dI$. Its trace is zero; therefore the $+\sqrt{d}$ eigenspace has dimension exactly half the cube. Since $|U|$ exceeds that half, this eigenspace contains a nonzero vector $v$ supported on $U$.

Taking entrywise absolute values can only increase the signed quadratic form. With $u=|v|$ and $A_U$ the ordinary induced adjacency,

$$u^{\top }{A}_{U}u\ge v^{\top }{H}_d^{\prime }v=\sqrt{d}\Vert u{\Vert }^2.$$

Extending $u$ by zero gives a Rayleigh test for the sensitivity graph, proving $\lambda (f)\ge \sqrt{d}$. Combining this with the adversary bounds $\lambda (f)=O(Q(f))$, $\mathrm{bs}(f)=O(Q(f{)}^2)$, and the monomial-query estimate $D(f)\le \mathrm{bs}(f)\mathrm{deg}(f)$ produces the exponent four. This argument supplies the universal ceiling that the addressed-certificate construction approaches. (OpenAI, 2026)

See Also

• Huang’s sensitivity theorem supplies the signed-cube spectral mechanism used in the quartic upper bound.
• Boolean-oracle unitary synthesis treats coherent oracle access with total gate and workspace bounds; the present query model leaves intervening computation unrestricted.

🏷️ Manuscripts and verification scope

• A Nearly Quartic Separation Between Randomized and Quantum Query Complexity — pinned manuscript and companion source.

No family scope page was present at lean/docs/284.md in the pinned snapshot. This does not establish that all related formalization code is absent. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026. A Nearly Quartic Separation Between Randomized and Quantum Query Complexity.