How large can a quantum query advantage be? The quartic boundary

← All digests

Family 284 · Mathematical physics
Importance 4/5 · Provisional editorial rating
Sources consulted 2026-10-25

1. The question

Suppose an unknown binary string is stored behind an interface. An algorithm may request individual bits, and its task is to compute a specified yes-or-no property of the string. How many requests can quantum computation save?

For the property “at least one bit equals one,” classical randomized computation needs a number of requests proportional to the string length, while quantum search needs only its square root. More elaborate properties allow larger advantages. But if the property must be defined on every binary string, there is a universal restriction: classical queries never need to exceed a constant times the fourth power of quantum queries.

Family 284 claims that this fourth power is optimal, even when the classical algorithm may use randomness and make a small error. Its constructed examples approach a quartic separation and thereby disprove a proposed cubic upper bound. The distinction between a completely defined problem and a problem restricted to promised inputs drives the story.

2. Background and essential definitions

A total Boolean function is a map $f:\{0,1\}^n\to\{0,1\}$. “Total” means that every possible input has an assigned output. A partial function is defined only on some inputs; an algorithm for it need be correct only when the input satisfies that promise.

Write $R(f)$ for bounded-error randomized query complexity and $Q(f)$ for bounded-error quantum query complexity. Both require success probability at least $2/3$ on every relevant input. Both count the worst-case number of queries, including the worst case over random choices or measurement outcomes. Time spent computing between requests is unrestricted.

A quantum query can access a superposition of addresses. Its standard reversible form is

$$O_x|i,b,z\rangle=|i,b\mathbin{\oplus}x_i,z\rangle.$$

Here $i$ is an address, $b$ a one-bit register, $x_i$ the requested input bit, and $z$ other working memory; $\oplus$ denotes addition modulo two. Applying this operation to a superposition does not reveal all bits at once. Interference and the final measurement determine what information can actually be extracted.

A certificate is a collection of specified input bits sufficient to force an output. For OR, a single observed one certifies acceptance, whereas certifying rejection requires seeing every bit. Certificate size, deterministic query complexity $D(f)$, and randomized query complexity are different measures. A large separation involving one does not automatically establish the same separation involving another.

The notation $O(g)$ means an upper bound by a constant multiple of $g$ for sufficiently large parameters; $\Omega(g)$ means the analogous lower bound. Logarithmic factors matter for precise bounds but do not change the limiting power discussed here.

3. Development history and previous partial results

Grover’s search algorithm supplies the basic quadratic advantage. The polynomial method of Beals, Buhrman, Cleve, Mosca and de Wolf established a much broader restriction: for total Boolean functions, deterministic queries are at most a sixth power of bounded-error quantum queries. Thus the spectacular exponential separations available for some promise problems cannot simply carry over to total functions.

Constructing larger total-function separations nevertheless proved difficult. Pointer functions made certificates navigable in ways that favored quantum algorithms and produced nearly quartic deterministic-versus-quantum separations. Randomized algorithms were harder to defeat: they can explore many possible witnesses without committing to a deterministic search pattern.

Aaronson, Ben-David and Kothari’s cheat-sheet framework hid useful certificates at addresses determined by hard partial-function instances. It gave a randomized-versus-quantum exponent of $5/2$, ignoring logarithms. Subsequent work by Tal raised the exponent to nearly $8/3$; work by Bansal and Sinha and, independently, Sherstov, Storozhenko and Wu brought it arbitrarily close to three.

On the other side, the consequences of Huang’s sensitivity theorem gave the known quartic upper bound for deterministic complexity and hence also for randomized complexity. The associated conjecture proposed that randomness should improve the exponent to three. Family 284 targets precisely the remaining gap between this conjectured cubic restriction and the known quartic restriction.

Its main external lower-bound ingredient is Bansal and Sinha’s result about generalized Forrelation, a promise problem comparing several sign vectors through Fourier transforms. Quantum queries can estimate the relevant correlation with very few accesses, while classical randomized queries need almost the full input length. The new manuscript combines this existing ingredient with a different organization of witnesses.

4. What the new manuscripts claim

M1 states that the optimal universal power is four. More explicitly, for every fixed integer $k\geq2$, it constructs total Boolean functions $F_{k,m}$, for sufficiently large powers of four $m$, with

$$Q(F_{k,m})\leq C_k\sqrt m\,(\log m)^{b_k},$$

and

$$R(F_{k,m})\geq c_k\frac{m^{2-1/k}}{(\log m)^2}.$$

The positive constants $c_k,C_k,b_k$ may depend on $k$. The parameter $m$ describes the construction’s columns, not its total number of input bits; the latter also includes large arrays of certificate cells.

Combining the two estimates gives an exponent approaching $4-2/k$, apart from logarithmic losses. For any proposed universal exponent $\alpha<4$, one first fixes $k$ large enough that $4-2/k>\alpha$, and then lets $m$ grow. Polynomial growth eventually dominates the logarithms. Consequently, M1 rules out every bound

$$R(f)\leq C_\alpha(1+Q(f))^\alpha$$

holding for all total Boolean functions with $\alpha<4$. The additive one handles constant functions harmlessly.

This is a nearly quartic separation, not a statement that the displayed examples satisfy an exact lower bound proportional to $Q(f)^4$. The known universal quartic upper bound supplies the other side of the optimal-exponent conclusion; that upper bound is credited to earlier work.

5. Why the advance matters

Importance: 4/5. If correct, this resolves a central quantitative question in quantum query complexity and disproves a specific proposed limitation on quantum advantages. It shows that randomized classical access can be almost as far from quantum access, in exponent, as deterministic classical access is allowed to be.

The conceptual gain is also substantial. Promise problems offer unusually favorable terrain for quantum algorithms, but real total-function separations must remain well-defined and correctly handled when every internal promise fails. M1 explains how to preserve useful quantum behavior while making malformed local data merely invalidate a candidate witness.

The rating concerns a basic computational model rather than an immediate experimental application. Query complexity deliberately ignores potentially expensive computation between oracle calls. The construction identifies a boundary of information access; it does not by itself supply a practical fourth-power speedup for an everyday numerical task.

6. The main idea

Hide the certificate’s address

The input has $m$ columns. Column $i$ contains a string $X_i$ of $m$ bits, several Forrelation instances, and an array of certificate cells. The answers to the Forrelation instances determine the address of the relevant cell.

A column is a winner if its own string is all ones, its address instances satisfy their promises, and its correctly addressed certificate verifies those answers while pointing to a zero in every other column. The function accepts exactly when a winner exists. At most one column can win: a purported second winner would have to contain a zero identified by the first.

Certificates include transcripts of ordinary Boolean circuits that check the address claims. Thus validity is a definite condition on the input bits even when the Forrelation promises fail. Invalid instances produce no winning certificate. The outer function is genuinely total.

Let the winner defeat unreliable opponents

Quantumly, the address information is cheap to obtain on valid instances, and quantum search accelerates certificate checking. The harder issue is locating a winner without thoroughly checking every column.

Pointers point outward from the winning column to zeros in its competitors. This orientation gives a reliable comparison whenever a genuine winner participates: its evidence can defeat an opponent, while an opponent cannot point to a zero in the winner’s all-one string. Comparisons between two non-winners may behave arbitrarily, including when their address promises fail.

M1’s tournament procedure is designed for exactly this uneven reliability. It uses comparison probabilities as weights, with coherent workspaces and amplitude amplification, to obtain a short list containing any true winner. Subsequent checking gives the stated square-root dependence on the number of columns, up to logarithmic factors. The argument does not assume that all pairwise comparisons define a consistent ranking.

Make classical discovery expensive

For the classical lower bound, begin with one independently hidden zero in every column and blank certificate cells. This is a rejecting input. Select a random column, erase its zero, and fill its correctly addressed certificate cell. The modified input has a winner.

A randomized algorithm distinguishes the two only by encountering the erased zero or the filled cell. Finding the relevant hidden zero across many possible columns is costly. Finding the filled cell requires learning enough hard address information or successfully guessing a whole vector of answers.

An adaptive direct-product argument controls the second possibility even when the algorithm chooses its next column from everything observed so far. This is where simply analyzing one fixed hard instance would be insufficient: the algorithm can spread its effort among many candidate winners.

7. Scope, limitations, and open questions

The claims concern bounded-error, worst-case bit queries for total Boolean functions. They do not compare gate counts, memory, communication, energy use, or classical and quantum wall-clock running time. The quantum routines retain a fixed query cap even on inputs that violate the internal promises.

The parameter $k$ is fixed before $m$ tends to infinity. Constants may deteriorate with $k$, and the theorem leaves logarithmic losses and exact constant factors unresolved. It settles the best universal exponent, not the sharpest possible relationship at every finite input size.

The construction is deliberately elaborate: certificate arrays, address instances and transcripts form part of the actual input. Replacing them by a succinct representation would change the access model and would require a separate analysis. A more natural or smaller-input realization of the same extremal behavior would be a further contribution, rather than an automatic consequence of the theorem.

Finally, the lower bound uses an established Forrelation theorem. M1’s contribution is the total-function construction and its quantum and randomized analyses, not the discovery of that underlying partial-function separation.

8. Sources and further reading

• Aaronson and collaborators, Quantum Implications of Huang’s Sensitivity Theorem, for the quartic upper bound and the surrounding complexity measures.
• Bansal and Sinha, k-Forrelation Optimally Separates Quantum and Classical Query Complexity, for the partial-function ingredient.
• Aaronson and Ambainis, Forrelation: A Problem that Optimally Separates Quantum from Classical Computing, for the original correlation problem and its query interpretation.

Source manuscripts

• M1. OpenAI, A Nearly Quartic Separation Between Randomized and Quantum Query Complexity (October 5, 2026).

Sources consulted on 25 October 2026 at repository revision 1581d4c. Download the manuscript citations.