A Nearly Quartic Separation Between Randomized and Quantum Query Complexity

Introduction

How much can a quantum algorithm reduce the number of input bits needed to compute a total Boolean function? Let $f : \{0,1\}^{n} \to\{0,1\}$. We write $R(f)$ and $Q(f)$ for the minimum worst-case numbers of bit queries made by randomized and quantum algorithms that compute $f$ with error at most $1/3$ on every input. Quantum queries use the standard oracle

Computation between queries is unrestricted. In particular, all query bounds in this paper are worst-case bounds, including over internal randomness and measurement outcomes.

Polynomial relations between these two measures express a basic restriction on quantum speedups for total functions. To ask for the sharp power without imposing a particular logarithmic correction, define

The additive 1 includes constant functions. We prove the following.

Theorem 1.1. The optimal power is $\alpha_{\mathrm{tot}} = 4$. More precisely, $R(f) = O((1 + Q(f))^4)$ for every total Boolean function. 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

The universal upper bound is known. The contribution is the family in (2), which rules out every smaller power, including the conjectured cubic relation.

Historical context

Grover’s search algorithm [16] gives the basic quadratic speedup for the OR function, with a matching quantum lower bound [10]. Beals, Buhrman, Cleve, Mosca, and de Wolf [8] proved the general polynomial relation $D(f) = O(Q(f)^6)$, where $D(f)$ is exact deterministic query complexity. Their result builds on the combinatorial and polynomial measures studied by Nisan [20] and Nisan and Szegedy [21]. Thus totality rules out the exponential query speedups possible for partial functions, but it leaves a substantial range of possible powers.

Pointer constructions introduced by Göös, Pitassi, and Watson [15] and developed by Ambainis, Balodis, Belovs, Lee, Santha, and Smotrov [4] gave a nearly quartic separation between deterministic and quantum queries. For bounded-error randomized queries, Aaronson, Ben-David, and Kothari [2] introduced the cheat-sheet framework and obtained a power-5/2 separation, up to logarithmic factors. This framework places certificates in an array whose correct address is determined by answers to partial-function instances. Improvements in those partial-function separations led to power $8/3 - o(1)$ by Tal [26], and then $3 - o(1)$ by Bansal and Sinha [6] and independently Sherstov, Storozhenko, and Wu [23].

On the upper-bound side, Aaronson, Ben-David, Kothari, Rao, and Tal [3], using Huang’s sensitivity theorem [17], proved $D(f) = O(Q(f)^4)$. They conjectured that randomized complexity satisfies the stronger relation $R(f) = O(Q(f)^3)$ [3 Conjecture 2]. Theorem 1.1 disproves that conjecture and shows that the quartic upper bound already has the optimal power for bounded-error randomized complexity.

There is also a direct connection to algorithms that compare candidate witnesses. Quantum minimum finding [14], sink finding [25], and king finding in tournaments [18] provide related search procedures. Recent constructions of Ben-David and Kothari [9] and Ambainis, Iraids, and Kokainis [5] use comparisons of candidate witnesses to separate certificate complexity from randomized and quantum query complexity. Certificate complexity measures the worst-case size of a smallest partial input assignment that fixes the function value. Their nearly quartic separations between certificate and quantum complexity concern a different classical measure, but their comparison-based viewpoint is particularly relevant here.

The construction and its two analyses

The input is organized into $m$ columns. Each column $i$ contains a string $X_i$ of $m$ bits and an array of certificate cells. The address of the relevant cell is the vector of answers to several disjoint instances of a partial function. Quantumly these answers are cheap to obtain on promised inputs; classically they are hard to guess. Each cell stores pointers to positions in all the other strings $X_j$, together with a circuit transcript certifying the address.

A column wins when its own string is all ones, its address is defined, and its certificate is correct and points to a zero in every other column. The total function asks whether a winner exists. There can be at most one. An incorrect address or transcript simply fails verification; the input to the total function carries no promise.

The direction of the pointers matters. A true winner can use its own certificate to disqualify every opponent. Conversely, no cell in any opponent can point to a zero in the winner’s all-one string. Thus a cheap quantum comparison favors the winner with high probability even if the opponent’s address instances violate their promises. Comparisons between two non-winners may have arbitrary probabilities. Section 3 proves a tournament lemma that permits precisely this behavior. It produces a short list containing the winner in $\sqrt{m}$ times a polylogarithmic number of queries, after which quantum search checks the certificates.

The classical proof starts with one independently hidden zero in every $X_i$ and blank certificate cells. We choose a uniformly random column, erase its zero, and fill its correctly addressed cell. These two changes produce a winner. A randomized algorithm can distinguish the two inputs only by finding the erased zero or querying the filled cell. The first event is unlikely for a uniformly chosen column; the second requires either many address queries in that column or a correct guess of an entire vector of hard answers. An adaptive direct-product argument makes this last assertion precise without conditioning on the algorithm’s choice of which columns to investigate.

The tournament analysis is useful independently of this construction. It uses the actual probabilities of comparisons as multiplicative weights; fresh coherent workspaces and amplitude amplification sample those weights exactly. Only comparisons involving a genuine winner need to be reliable. This extends the candidate-comparison approach to the arbitrary behavior caused here by off-promise address inputs. The classical analysis combines the planted input with a standard per-instance-capped direct-product argument [22, 13]; the separate cell arrays let this argument charge the cost of addressing many possible winners.

Section 2 defines the function and its certificates. Sections 3 and 4 prove the two bounds in (2); Section 5 derives the optimal power. Appendix A gives a self-contained proof of the known quartic upper bound. The only external lower-bound input is the Forrelation theorem stated in Section 2.

Conventions

We write $[m] = \{1, \ldots, m\}$ and use logarithms to base two, except in expressions where changing the base only changes an absolute constant. Constants in bounds for $F_{k,m}$ may depend on the fixed integer $k$. A partial Boolean function is specified on a subset of $\{0, 1\}^{N}$; its algorithms must be correct on that subset. The quantum routines used here have a fixed query cap on every input, including inputs outside the promise. A circuit transcript lists proposed values of the non-input gates; the actual input bits are read directly when a gate check needs them.

An addressed certificate with outward pointers

We construct a total function whose accepting certificate belongs to one column. The certificate must certify the answers to several Forrelation instances and point to a zero in every other column. The latter requirement will let a genuine accepting column defeat any competitor, even when that competitor’s Forrelation instances violate their promise.

Throughout the construction, fix an integer $k \ge2$ and let $m$ tend to infinity through powers of four. Constants in $O_k(\cdot)$ may depend on $k$, which remains fixed as $m$ grows. Write $[m] = \{1,\ldots,m\}$.

The partial function and its exact circuit

We use the $k$-fold Forrelation problem introduced by Aaronson and Ambainis [1], with the thresholds analyzed by Bansal and Sinha [6]. Let $H$ be the normalized Walsh–Hadamard matrix of order $m$, and let $u = m^{-1/2}(1,\ldots,1)^{\mathsf{T}}$. We identify a bit $a$ with the sign $(-1)^a$. For a sign vector $z$, write $D_z$ for the diagonal matrix with diagonal $z$. Given $k$ sign vectors $z_1,\ldots,z_k \in\{\pm1\}^m$, put

Define the partial Boolean function $P = P_{k,m}$ on $km$ bits by

and leave it undefined on all other inputs. The two displayed cases are disjoint. Query complexity for this partial function requires correctness only on its domain.

Lemma 2.1. For each fixed integer $k \ge2$, the functions $P_{k,m}$ have the following properties.

(i) For all sufficiently large powers of four $m$,

(ii) For every $0 < \eta< 1/2$, a quantum algorithm uses $O_k(1+\log(1/\eta))$ bit queries and returns $P_{k,m}$ with error at most $\eta$ on every input in its domain. The algorithm can be implemented coherently, retaining its workspace. On every input, promised or not, it produces a bit when its output register is measured.

(iii) There is a Boolean circuit $C=C_{k,m}$ of fan-in at most two and size $S=S_{k,m}=O_k(m(\log m)^2)$ with two output bits $d,b$ such that

The circuit computes these outputs exactly on every input.

Proof. Theorem 1.3 and Corollary 1.4 of Bansal and Sinha [6] apply to exactly the normalized form and thresholds in (3)–(4). They give, for fixed $k$ and error $1/3$,

This exceeds the value of $L$ in (5) for all sufficiently large $m$.

For the quantum algorithm, prepare $u$, apply the unitary product in (3), in its right-to-left order, and test the projection onto $u$. Each $D_{z_h}$ uses one phase query, implemented by the standard bit oracle, while $H$ and the projection require no queries. The projection succeeds with probability $\Phi^2$. This probability is at least $\delta^2$ on a 1-input and at most $\delta^2/4$ on a 0-input. Independent repetitions and a threshold between these two numbers give error $\eta$ with $O_k(1+\log(1/\eta))$ repetitions. The measurement outcomes and the final threshold decision can instead be computed into registers and retained, giving the claimed coherent implementation.

For the circuit, let $W=\sqrt{m}H$, whose entries are $\pm1$. The scalar

is an integer, and

The denominator is an integer because $m$ is a power of four. Compute $N$ by $k-1$ unnormalized Walsh–Hadamard transforms, coordinatewise sign changes, and a final signed sum. Each transform uses $O(m\log m)$ additions and subtractions by the usual butterfly recursion. All intermediate integers have absolute value at most $m^{O(k)}$, so $O_k(\log m)$ bits suffice. Binary additions, subtractions, sign changes, and comparisons have fan-in-two Boolean circuits of size linear in this bit length. Consequently the entire arithmetic circuit has Boolean size $O_k(m(\log m)^2)$.

Finally, the two tests in (4) are the exact integer comparisons

Set $d$ to the disjunction of these comparisons and $b$ to the first comparison. This adds only $O_k(\log m)$ gates and proves the last assertion. ▫

The exact circuit serves a different purpose from the quantum algorithm. The algorithm will propose an address. A transcript of the circuit will certify that this address consists of defined, correct answers, including on inputs where an arbitrary proposed address has no reason to be correct.

The total function

Set

The input has $m$ columns. Column $i \in[m]$ contains the following bits:

1. A string $X_i \in\{0,1\}^m$.

2. Strings $A_{i,1},\ldots,A_{i,r} \in\{0,1\}^{km}$, with no promise imposed on them.

3. A cell $B_{i,s}$ for each address $s \in\{0,1\}^r$. This cell contains a pointer $p_{i,s,j} \in[m]$ for each $j \ne i$, encoded by $\ell$ bits using a fixed bijection, and an alleged evaluation transcript of $C_{k,m}$ on each $A_{i,h}$, $h \in[r]$.

An evaluation transcript consists of one bit for every non-input gate of $C_{k,m}$, including its output gates. Circuit inputs are the actual bits of $A_{i,h}$; they need not be copied into the transcript. We count these non-input gates in $S$.

Call column $i$ a winner if $X_i = 1^m$, every $P(A_{i,h})$ is defined, and the cell at its true address

contains correct evaluation transcripts and pointers satisfying

Define $F_{k,m}$ to be 1 if a winner exists, and 0 otherwise. This is a total Boolean function: all the preceding conditions are predicates on the input bits, and no promise is made about the $A$-strings, the pointers, or the transcripts.

The addressed transcripts have the certificate role used in cheat-sheet constructions [2], while pointers between columns also occur in earlier query-complexity separations [15, 4]. Here the pointers have a specific outward orientation: an accepting column supplies a direct zero witness against every competitor. In particular, there can be at most one winner, since a winner’s pointer to another column certifies that the latter is not all ones. Figure 1 depicts this condition.

We next make certificate verification precise. For a specified pair $(i,s)$, say that $i$ wins at address $s$ if $i$ is a winner and $s=s_i$.

Lemma 2.2. For every input to $F_{k,m}$ and every pair $(i,s)\in[m]\times\{0,1\}^{r}$, the assertion that $i$ wins at address $s$ is a conjunction of

Boolean tests. Each test can be evaluated exactly with $O(\log m)$ bit queries. The tests can also be evaluated coherently with the same query bound, with their indices supplied in superposition. Their number and indexing convention are the same for every $(i,s)$.

Proof. Use one test for each bit of $X_i$, requiring it to be 1, and one test for each $j\ne i$, reading the pointer $p_{i,s,j}$ and requiring the indicated bit of $X_j$ to be 0. The latter uses $\ell+1$ queries.

For each of the $r$ transcripts in $B_{i,s}$, use one test per gate, requiring its claimed value to be the prescribed Boolean function of its predecessors. A predecessor value is read from the transcript for a non-input gate and from $A_{i,h}$ for an input wire. Fan-in at most two therefore makes each such test use at most three queries. Add two output tests, requiring $d=1$ and $b=s_h$. By induction in a topological order of the circuit, all gate tests pass if and only if the transcript is the true evaluation. The output tests then say exactly that $P(A_{i,h})$ is defined and equals $s_h$. Together with the $X_i$ and pointer tests, these are precisely the winner conditions at $(i,s)$.

The wiring of the circuit and the locations of all bits are fixed and require no queries to compute. A test can load the required bits into ancillas, compute its result reversibly, and unload the bits by querying again. The bit oracle is its own inverse. A controlled use of that oracle, when needed, is likewise implemented by loading, controlled use of the loaded value, and unloading. Thus coherent evaluation, including an input-dependent pointer lookup, changes the query count by at most a constant factor. □

Two consequences will be used repeatedly. A winning column has one address at which every test passes; a nonwinning column has a failing test at every address. Thus an address proposed on an unpromised input can always be checked against the total definition.

Quantum search with probabilistic comparisons

We first prove a general tournament statement. A comparison need not behave almost deterministically: its outcome probabilities may be arbitrary, provided one distinguished candidate beats each opponent with sufficiently high probability. This is the additional feature needed beyond comparison algorithms for a fixed tournament [25, 18, 9]. There is no promised gap between a nonwinner comparison probability and $1/2$, so ordinary error reduction does not provide uniformly cheap bounded-error access to a fixed tournament. After proving the statement, we construct the comparisons for $F_{k,m}$ and verify the candidates they produce.

Amplification without changing the sampled distribution

The tournament will sample a candidate conditioned on defeating every previously selected candidate. Amplification must preserve that conditional distribution while increasing the probability of obtaining a sample. This is a direct consequence of the two-dimensional rotation underlying amplitude amplification [11, 12]; we give the details because the distribution, as well as the success probability, is used in the tournament.

Lemma 3.1 (Bounded amplification). Let $A$ be a quantum state preparation with a designated success bit. Its success probability is $p$, and, if $p > 0$, its normalized successful state is $|g\rangle$. Let $0 < \gamma\le1/2$ and $0 < \eta< 1/2$. There is a procedure using

calls to $A$ and $A^{-1}$ that either reports failure or produces a successful outcome. Conditional on success, the output state is $|g\rangle$ up to a global phase. If $p \ge\gamma$, its failure probability is at most $\eta$. If $p = 0$, it always reports failure. The call bound holds for every $p$ and on every branch.

Proof. For $0 < p < 1$, write

where the two normalized vectors lie in the successful and unsuccessful subspaces. Reflection about $A|0\rangle$, followed in the appropriate order by a phase flip of the success bit, gives after $\ell$ Grover iterations the state

Thus measuring success leaves exactly the same normalized successful state, independently of $\ell$. Each reflection about the prepared state uses $A$, a query-free reflection about $|0\rangle$, and $A^{-1}$.

Set $M = \lceil10/\sqrt{\gamma}\rceil$. A trial chooses, with equal probabilities, either $\ell= 0$ or a uniform $\ell\in\{0,\ldots,M-1\}$, then measures the success bit. If $p \ge1/2$, the first choice alone gives success probability at least $1/4$. If $\gamma\le p \le1/2$, then

Summing a geometric progression bounds the averaged success probability in the second choice by

Every trial therefore succeeds with probability at least $9/40$ when $p \ge\gamma$. Repeat a fixed $\lceil\log(1/\eta)/\log(40/31)\rceil$ number of trials with fresh registers, stopping at the first success. The probability that all fail is at most $\eta$. Each trial uses $O(M)$ calls, whether it succeeds or fails. Every successful trial has the same state $|g\rangle$, so neither the random choice of length nor stopping at the first success changes that state. The cases $p=0$ and $p=1$ follow directly, with the successful component absent or equal to the entire prepared state.

The tournament

Fix an input to the bit oracle. For candidates in $[m]$, suppose a coherent comparison produces one victorious candidate for each unordered pair. It retains all workspace, so it is a unitary state preparation that can be reversed. Let $a_{ij}$ be the probability that $i$ defeats $j$ when the comparison result is measured. We always use the same circuit for the unordered pair, and set $a_{ii}=0$. Hence

The following result is pointwise in the fixed oracle input; its probabilities are over the algorithm’s internal randomness and measurements.

Proposition 3.2 (A tournament for probabilistic comparisons). For $m\ge2$, put

Suppose a coherent comparison circuit, controlled by two candidate indices and reversible with all workspace retained, uses at most $c\ge1$ bit queries. Let $a_{ij}$ be the probability that it reports $i$ defeating $j$, and assume (10). There is a quantum algorithm making

queries on every branch and returning a list of at most $T$ candidates with the following guarantee. If $i_* \in[m]$ satisfies

then the list contains $i_*$ with probability at least $1-2m/2^T-T\epsilon$.

Proof. We analyze an ideal sampling process and then implement each of its steps quantumly. Start with $w_i=1$ for all $i$, and write $W=\sum_i w_i$. When $W>0$, sample a pivot $p$ with probability $w_p/W$, append it to the list, and update

When $W=0$, leave the list unchanged and keep all weights zero. The weights only define this ideal process; the algorithm will not compute them numerically.

For $W>0$, complementarity gives the exact drift identity

The same inequality holds when $W=0$, so after $T$ steps $\mathbb{E}W_T\le m/2^T$. If a candidate $i_*$ satisfying (11) has never been selected, its final weight is at least

In particular, the process cannot reach zero total weight before selecting it. Markov’s inequality implies

Now fix an arbitrary list of previously selected pivots $p_1,\ldots,p_t$, where $t<T$. Prepare a uniform superposition of $i \in[m]$, and, for each pivot, compare $i$ with that pivot in a fresh workspace. Conditional on $i$, let $\lvert\phi(i,p_b)\rangle$ denote the complete comparison state, including its result bit. Before computing a success bit, the joint state is

Set the success bit precisely when every comparison says that $i$ defeats its pivot. All garbage is retained. By the tensor product in (15), the conditional success probability for index $i$ is

The empty product is one. Distinct index registers are orthogonal, so the total success probability is $W/m$, and the conditional distribution of $i$ on success is exactly $w_i/W$.

Apply Lemma 3.1 with $\gamma=1/(2m)$ and $\eta=\epsilon$. A successful sample still has exactly this index distribution: amplification preserves the full successful state, not just its total probability. If sampling reports failure, stop and return the list already accumulated. Otherwise measure the index, append it, and continue, for at most $T$ stages.

Until $i_*$ is first selected, its weight is at least $1/2$, so $W/m\ge1/(2m)$. At each such history the sampler has failure probability at most $\epsilon$ and, conditional on success, exactly the ideal pivot law. One can therefore couple that stage to an ideal pivot, with probability at most $\epsilon$ of terminating instead. The coupling is conditional on the entire previous pivot history; it does not require history-independent failure probabilities. Summing these failure probabilities over at most $T$ stages and using (14) gives the stated guarantee. Once $i_*$ has entered the list, later termination cannot remove it.

At stage $t$, the preparation and its inverse use $O(c(t+1))$ queries. Lemma 3.1 uses $O(\sqrt{m}\log(1/\epsilon))$ such calls. Summing over $t<T$ gives $O(c\sqrt{m}T^2\log T)$ queries. The number of stages and all trial counts are fixed upper bounds, so this is a worst-case query bound even if there is no candidate satisfying (11). □

The proof uses no order or transitivity among the candidates. Its shrinking quantity is the sum of fractional weights in (12), and complementarity alone yields (13). This is why unpromised address computations will be permitted in the application.

Comparing columns and verifying the list

We now fix an arbitrary input to $F_{k,m}$, including possibly undefined Forrelation instances and incorrect circuit transcripts. Keep $T$ and $\epsilon$ as in Proposition 3.2. To decode column $i$, run the quantum algorithm for each of its $r$ partial-function instances, amplified to error at most $\epsilon/r$. Repetition and a majority computation take

queries. If all these instances are defined, the resulting address is correct with probability at least $1-\epsilon$. Otherwise the routine still returns some address. All repetitions and majority computations can be performed unitarily with their workspaces retained.

For a pair of distinct columns, sort their indices and apply the following comparison in this fixed order. Decode the address of each column in a separate workspace. Read each column’s pointer toward the other at its decoded address, and inspect the bit of the other’s $X$ string to which it points. A column disqualifies its opponent if that bit is zero. If exactly one column disqualifies the other, declare it victorious; otherwise declare the smaller index victorious. For a self-comparison, return false without reading a pointer.

These operations prepare a comparison state with $c=(\log m)^{O_k(1)}$ queries. The decoded addresses remain in their registers, and subsequent operations are controlled in the computational basis. Consequently its measurement probabilities agree with the description just given; different address outcomes are orthogonal and do not interfere. Reversing the complete preparation costs the same number of bit queries. Using the same sorted-pair circuit for either ordering ensures (10).

If $i_*$ is a winner, then $X_{i_*}$ is all ones. No opponent, at any decoded address, can point to a zero there. When the address of $i_*$ is correctly decoded, its own certificate points to a zero in every other column. Thus

regardless of whether the opponent’s address instances are defined. Proposition 3.2 therefore returns a list containing the winner, when one exists, with probability at least $1-2m/2^T-T\epsilon$.

For each listed column, decode and measure its address afresh. At that fixed address, the winner conditions are the exact local tests of Lemma 2.2. Let their number be $K=m(\log m)^{O_k(1)}$. A uniform test index and an exact failing-test flag give a preparation whose success probability is zero when all tests pass, and at least $1/K$ otherwise. Lemma 3.1, with $\gamma=1/K$ and $\eta=\epsilon$, searches for a failed test in

queries. Here $K \ge m \ge4$. Reject this candidate if a failed test is found, and accept it otherwise. Exact testing cannot report a failure when all tests pass. If the column is not a winner, every address has a failed test, so it is accepted with probability at most $\epsilon$. A true winner is accepted whenever decoding is correct: in that case there is no failed test for the search to report. Its rejection probability is therefore at most $\epsilon$, solely from address decoding.

Output one if any listed candidate is accepted. On a zero-input, a union bound gives error at most $T\epsilon$. On a one-input, the miss probability and the winner’s verification error give total error at most

The comparisons, tournament, and at most $T$ verifications prove

Proposition 3.3. For every fixed $k \ge2$, the total functions of Section 2 satisfy

All superposed array accesses used above are ordinary bit queries. The global bit index is computed reversibly from the column, cell, and wire indices. A pointer is read one bit at a time in $O(\log m)$ queries, after which its target index is computed without queries. A controlled bit query can be implemented by loading the addressed input bit into an ancilla, using it under the required control, and unloading it with a second query. Thus neither coherent addressing nor retaining and reversing comparison garbage changes the query model.

The randomized lower bound

We compare a distribution with one zero in every column to a coupled distribution in which one uniformly chosen column is made a winner. An algorithm can distinguish them only by finding the zero that was removed or by reaching the newly filled certificate cell. The first event requires searching many columns; the second requires either many Forrelation queries in the chosen column or a successful guess of its entire address.

Independent answers under adaptive queries

We first record the precise amplification fact needed for address guessing. We use the capped direct-product argument developed by Drucker [13 Section 1.3 and Lemmas 3.1–3.2], following earlier work of Shaltiel [22]. Its query limit is imposed separately on each input, while queries to different inputs may be interleaved adaptively.

Lemma 4.1. Let $P:D\to\{0,1\}$, where $D\subseteq\{0,1\}^{n}$, let $\mu$ be a distribution on $D$, and let $L$ be a nonnegative integer. Suppose every deterministic algorithm making at most $L$ queries computes $P$ under $\mu$ with success probability at most $\beta$. If $U_1,\ldots,U_r$ are independent samples from $\mu$, every classical algorithm making at most $L$ queries to each $U_h$ has probability at most $\beta^r$ of outputting

The algorithm may be randomized, choose its queries adaptively among the $r$ inputs, and receive arbitrary additional information independent of $(U_1,\ldots,U_r)$.

Proof. Fix the additional information and all internal random coins, leaving a deterministic algorithm. At any transcript $\tau$ of positive probability, the conditional law of $(U_1,\ldots,U_r)$ is a product of their separate conditional laws. Indeed, the event of obtaining $\tau$ requires exactly the observed bit values in each input. Any tuple satisfying these requirements follows the same query schedule, since the next query is determined by the preceding answers. Thus this event is a Cartesian product of constraints on the individual inputs.

For each $h$, let $q_h$ be the number of queries already made to $U_h$, and let $V_h(\tau)$ be the largest success probability for computing $P(U_h)$ from its current conditional law using at most $L-q_h$ further queries. This maximum is attained because the domain and the remaining query budget are finite. If the next query addresses $U_h$, optimality gives

where $\tau'$ includes its answer: making that particular query and then using an optimal continuation is one allowed strategy in the definition of $V_h(\tau)$. The conditional laws and budgets of the other inputs do not change. Hence

The product is therefore a supermartingale over the successive queries. There are at most $rL$ such queries; a run that stops earlier can be extended by steps leaving all values unchanged.

At the final transcript, the conditional probability that the algorithm’s chosen answer vector is correct is at most

The first inequality uses the product conditional law, and the second uses the option of making no further queries. Initially every $V_h$ is at most $\beta$. Taking expectations proves the bound $\beta^r$. Averaging over the fixed information and coins proves the full statement.

Return to $P = P_{k,m}$ and $L$ from (5), with $m$ large enough that $1 \le L < \mathrm{R}(P)$. There are finitely many deterministic decision trees of depth at most $L$ on this finite domain. A randomized algorithm of that query depth is a distribution on these trees. Finite minimax, in its query-complexity formulation [27], applied to the payoff that the answer is correct, gives

The left-hand side is less than $2/3$, since its maximum is attained and $L < \mathrm{R}(P)$. Consequently there is a distribution $\mu$ on $\operatorname{dom} P$ for which every such deterministic tree has success probability at most $2/3$. Lemma 4.1 therefore bounds the success probability of guessing $r$ independent answers by $(2/3)^r$.

Coupled zero and one inputs

Proposition 4.2. For each fixed integer $k \ge2$ and every sufficiently large power of four $m$, the total function of Section 2 satisfies

Proof. Generate a dummy input $Y^{(0)}$ as follows. Independently for each $i \in[m]$, choose $J_i$ uniformly from $[m]$ and put a single zero at position $J_i$ in $X_i$, setting its other bits to 1. Draw all $A_{i,h}$ independently from $\mu$, independently also of the $J_i$. Set all cells $B_{i,s}$ to one fixed blank bit pattern. Since each $X_i$ has a zero, $F_{k,m}(Y^{(0)}) = 0$.

Choose $I$ uniformly from $[m]$, independently of the entire dummy input. Form a planted input $Y^{(1)}$ by setting $X_I = 1^m$ and filling its true-address cell $B_{I,s_I}$ with the correct circuit transcripts and the pointers $p_{I,s_I,j} = J_j$ for $j \ne I$. All $A$-strings are in the domain of $P$, so $s_I$ is well defined. Column $I$ is a winner, and therefore $F_{k,m}(Y^{(1)}) = 1$.

Fix a deterministic algorithm making at most $G$ queries, and consider its run on $Y^{(0)}$. The coupled inputs can differ only at the bit $X_I[J_I]$ and inside the cell $B_{I,s_I}$. Until one of these locations is queried, the two executions have identical answers and hence identical subsequent queries. It follows that the difference between their output-1 probabilities is at most

Counting every visit to the indicated cell is an upper bound even if the queried bit happens to agree with its blank value.

Finding the removed zero. Let $Z$ be the number of columns whose zero is discovered in the dummy run. Before the zero in a column is found, its location is uniform among the positions in that column not yet queried. This remains true conditional on the full adaptive transcript: the other $X$-strings and all $A$-strings are independent of its zero location, and the blank cells supply no information about that location. Call a discovery early if fewer than $m/2$ distinct positions in its column were queried before it. Conditional on the preceding transcript, each query has probability at most $2/m$ of an early discovery. Thus the expected number of early discoveries is at most $2G/m$. Each remaining discovery occurs in a column that receives at least $m/2$ queries, and there are at most $2G/m$ such columns. Hence

The dummy run is independent of $I$, so

Reaching the planted cell. Call a column heavy if, over the entire dummy run, the algorithm makes more than $L$ queries in total to its strings $A_{i,1},\ldots,A_{i,r}$. There are at most $G/L$ heavy columns. Independence of $I$ gives

For the other columns we use Lemma 4.1. The following simulation bounds a joint event and does not condition the input distribution on a column being nonheavy.

Fix $i \in[m]$ and a time $t \in\{1,\ldots,G\}$. Give a simulator all the dummy input outside $A_{i,1},\ldots,A_{i,r}$ for free. This information is independent of those $r$ strings. The simulator runs the deterministic algorithm up to its proposed $t$th query, but aborts before making an $(L+1)$st query to these $r$ strings in total. If it reaches time $t$ and the proposed query is to a cell $B_{i,s}$, it outputs the address $s$ as its guess for the vector of $r$ answers. Otherwise, including if the simulated run stops or aborts, it outputs any fixed vector.

The simulator makes at most $L$ queries in total to the target strings, and in particular at most $L$ to each one. By Lemma 4.1, its probability of guessing $s_i$ correctly is at most $(2/3)^r$. Whenever the original dummy run queries $B_{i,s_i}$ at time $t$ and column $i$ is nonheavy, this simulator has not aborted and outputs the correct address. Thus

Union bounding over $t$ and averaging over the independent uniform choice of $I$, then adding (20), yields

Equations (18), (19), and (22) bound the difference of output probabilities by

For all sufficiently large $m$, we have $1 \le L \le m$ and $G \le mL/100$. The first two terms are therefore at most $4/100$ and $1/100$, respectively. Moreover, (6) gives

In particular, (23) is strictly less than $1/3$ for large $m$.

The same bound holds for a randomized algorithm of worst-case query cost $G$, by fixing its coins and then averaging. Such an algorithm, if it had worst-case error at most $1/3$, would output $1$ with probability at most $1/3$ on $Y^{(0)}$ and at least $2/3$ on $Y^{(1)}$. Their output-$1$ probabilities would differ by at least $1/3$, contradicting the preceding estimate. Hence $R(F_{k,m}) > G$. ∎

For fixed $k$, Proposition 4.2 implies

The heavy-column estimate pays for learning an address, while the independent-answer estimate makes guessing an unlearned address negligible even over all $G$ adaptive queries.

The optimal power

We combine the quantitative bounds before recalling the universal upper bound in the appendix.

Proof of Theorem 1.1. For each fixed $k \ge2$, Proposition 3.3 gives $\mathrm{Q}(F_{k,m}) \le C_k\sqrt{m}(\log m)^{b_k}$ for suitable constants. Proposition 4.2 gives

for sufficiently large $m$, after decreasing $c_k > 0$. This proves (2).

Now fix $0 \le\alpha< 4$ and choose an integer $k \ge2$ such that $2 - 1/k > \alpha/2$. The integer $k$ remains fixed as $m$ tends to infinity. The preceding bounds imply

Hence no exponent smaller than four belongs to the set in (1). Conversely, Theorem A.1 proves $\mathrm{R}(f) \le\mathrm{D}(f) = O((1+\mathrm{Q}(f))^4)$ for every total Boolean function. Therefore four does belong to that set, and its infimum is four.

Separate address arrays force a classical algorithm to invest in many columns, while quantum comparisons locate a candidate before its certificate is checked. Quantum search then supplies the quadratic saving in checking the local tests. The direct-product estimate prevents a classical algorithm from bypassing the addressing cost by guessing certificate locations.

The universal quartic bound

For completeness, we prove the upper bound used in Theorem 1.1. The argument is the one of Aaronson, Ben-David, Kothari, Rao, and Tal [3], combining Huang’s signed-cube method [17] with the adversary bound and the deterministic degree–block-sensitivity inequality. No part of the construction is used in this appendix.

For a total Boolean function $f$, let $\mathrm{D}(f)$ be its exact deterministic query complexity and $\deg(f)$ its degree as a real multilinear polynomial. The degree is unchanged by replacing input or output bits by signs. A nonempty set $B \subseteq[n]$ is a sensitive block at $x$ if flipping every bit in $B$ changes $f(x)$. The block sensitivity $\mathrm{bs}(f)$ is the maximum, over $x$, of the number of pairwise disjoint sensitive blocks at $x$.

Theorem A.1 ([3]). Every total Boolean function satisfies

We establish the three ingredients separately. All matrix norms below are operator norms for the Euclidean norm.

Lemma A.2 (Nonnegative spectral adversary bound). Let $f$ be a nonconstant total Boolean function. Let $\Gamma$ be a nonzero real symmetric matrix, indexed by inputs, with nonnegative entries and $\Gamma_{xy}=0$ whenever $f(x)=f(y)$. Let

Then, for an absolute constant $c>0$,

Proof. This is the spectral adversary argument of Barnum, Saks, and Szegedy [7]; see also Špalek and Szegedy [24]. Purify all randomness and defer measurements. A bounded-query algorithm can be represented with a fixed number of queries, with at most a constant-factor overhead: branches that have finished can perform ineffective queries, and controlled queries can be simulated with two bit queries. Let $\lvert\psi_x^t\rangle$ be its normalized pure state on input $x$ after $t$ queries.

By the Perron–Frobenius theorem, $\Gamma$ has a nonnegative unit eigenvector $v$ of eigenvalue $\lVert\Gamma\rVert$. Track

Initially the states are input-independent, so $W_0=v^\top\Gamma v=\lVert\Gamma\rVert$. Input-independent unitaries preserve every overlap.

Immediately before a query, write the normalized state as

The bit oracle acts identically on inputs $x,y$ at that index unless $x_i\ne y_i$. When they differ, the overlap changes in magnitude by at most $2\lVert\phi_{x,i}\rVert\lVert\phi_{y,i}\rVert$, since the difference between the relevant unitary and the identity has norm at most two. Put $u_i(x)=v_x\lVert\phi_{x,i}\rVert$. Nonnegativity of the weights gives

The last equality follows from normalization of each query state and $\sum_xv_x^2=1$.

At the end, measure the output bit. For opposite-output inputs, one output-one probability is at most $1/3$, and the other is at least $2/3$. Splitting the two states by that output and applying Cauchy–Schwarz bounds their overlap in absolute value by $2\sqrt{2}/3$. Hence the final value satisfies

The required total change in $W$ divided by the per-query bound proves the assertion. □

Let $S_f$ be the adjacency matrix of the sensitivity graph: its vertices are $\{0,1\}^n$, and two vertices are adjacent if they differ in exactly one bit and have different function values. Write $\lambda(f)=\lVert S_f\rVert$.

Lemma A.3. For every nonconstant total Boolean function,

Proof. Choose an input $x$ with $b = \operatorname{bs}(f)$ disjoint sensitive blocks. Take $\Gamma$ to be the adjacency matrix of the star whose center is $x$ and whose leaves are the $b$ inputs obtained by flipping those blocks, with zero entries elsewhere. Its norm is $\sqrt{b}$. Each coordinate belongs to at most one block, so $\Gamma_i$ has at most one undirected edge and norm at most one. Lemma A.2 gives $Q(f) = \Omega(\sqrt{b})$. This recovers the usual block-sensitivity lower bound for quantum queries [8].

For the second assertion, use $\Gamma= S_f$. The edges in any one coordinate form a partial matching, whose adjacency matrix has norm at most one. Another application of Lemma A.2 gives $Q(f) = \Omega(\lambda(f))$, as in [3].

Lemma A.4 ([3], using [17]). Every nonconstant total Boolean function satisfies $\operatorname{deg}(f) \le\lambda(f)^2$.

Proof. Write the function with sign inputs and sign outputs, and set $d = \operatorname{deg}(f) \ge1$. Choose a monomial supported on a set of $d$ variables with nonzero coefficient, and fix all other variables to any signs. Its coefficient survives: any different monomial that could contribute to that coefficient would strictly contain its support and have degree larger than $d$. The restricted sign function $g$ on the $d$-cube therefore has nonzero correlation with parity. For some sign $\sigma\in\{-1,1\}$, the set

has size greater than $2^{d-1}$. Every cube edge with both endpoints in $U$ changes $g$, since parity changes across each edge.

Define a signed adjacency matrix of the cube recursively by

Its entrywise absolute value is the ordinary cube adjacency matrix. Induction gives $(H'_j)^2 = jI$, and its trace is zero. Thus $H'_d$ has eigenvalues $\pm\sqrt{d}$, each with multiplicity $2^{d-1}$. The $\sqrt{d}$-eigenspace intersects the space of vectors supported on $U$ nontrivially, because their dimensions sum to more than $2^d$. Choose a nonzero real vector $v$ in this intersection, and put $u = |v|$ entrywise. If $A_U$ is the unsigned adjacency induced on $U$, then

All edges of $A_U$ are sensitivity edges of the restriction, and hence of the original function. Extending $u$ by zero to the full input cube gives $\lambda(f) \ge\sqrt{d}$, as required.

Lemma A.5 ([19]). Every total Boolean function satisfies $D(f) \le\operatorname{bs}(f)\operatorname{deg}(f)$.

Proof. Consider the following deterministic algorithm. If the function restricted by the queries so far is nonconstant, select a monomial of maximum degree in that restricted polynomial and query all its variables. Continue until the restriction is constant.

Fix the actual full input $x$. In a given round, let $S$ be the selected monomial’s support. Fix all other still-unqueried variables to their values in $x$. The coefficient on $S$ remains nonzero, since no monomial in the current restriction strictly contains $S$. The resulting function on $S$ is nonconstant. Some assignment to $S$ therefore differs in value from the actual assignment $x|_S$. The nonempty subset of coordinates on which these two assignments differ is a sensitive block at the original input $x$.

Different rounds query disjoint sets, so these sensitive blocks are disjoint. There are at most $\operatorname{bs}(f)$ rounds. Restrictions do not increase degree, and each round queries at most $\operatorname{deg}(f)$ variables. The stated deterministic bound follows. $\square$

Proof of Theorem A.1. For nonconstant $f$, Lemmas A.3 and A.4 give both $\operatorname{bs}(f) = O(Q(f)^2)$ and $\operatorname{deg}(f) = O(Q(f)^2)$. Lemma A.5 then gives $D(f) = O(Q(f)^4)$. Since a deterministic algorithm is also randomized, $R(f) \le D(f)$. Constant functions require no queries. $\square$