A D V E R T |
I S E M E N T |
| Math Sites: lean ages 13-∞ readme referees parents | >>> MAITH GAMES <<< | all 372 compute stand |
|
LEVEL 1 OF 1 · The optimal randomized–quantum query exponent
A Nearly Quartic Separation Between Randomized and Quantum Query Complexity
expertly designed by an internal OpenAI model · released 2026-10-05
· original PDF
IntroductionHow 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 \(\mathrm R(f)\) and \(\mathrm 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 \[O_x\lvert i,b,z\rangle=\lvert i,b\oplus x_i,z\rangle.\] 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 \[ \alpha_{\mathrm{tot}}= \inf\left\{\alpha\ge0: \begin{array}{l} \text{there exists }C_\alpha<\infty\text{ such that, for every }n\ge1\nobreak\text{ and}\smallskip\\ f:\{0,1\}^n\to\{0,1\},\quad \mathrm R(f)\le C_\alpha(1+\mathrm Q(f))^\alpha \end{array}\right\}. \tag{1}\] The additive \(1\) includes constant functions. We prove the following. Theorem 1. The optimal power is \(\alpha_{\mathrm{tot}}=4\). More precisely, \(\mathrm R(f)=O((1+\mathrm 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 \[ \mathrm Q(F_{k,m})\le C_k\sqrt m\,(\log m)^{b_k}, \qquad \mathrm R(F_{k,m})\ge c_k\frac{m^{2-1/k}}{(\log m)^2}. \tag{2}\] 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 contextGrover’s search algorithm (Grover 1996) gives the basic quadratic speedup for the OR function, with a matching quantum lower bound (Bennett et al. 1997). Beals, Buhrman, Cleve, Mosca, and de Wolf (Beals et al. 2001) proved the general polynomial relation \(\mathrm D(f)=O(\mathrm Q(f)^6)\), where \(\mathrm D(f)\) is exact deterministic query complexity. Their result builds on the combinatorial and polynomial measures studied by Nisan (Nisan 1991) and Nisan and Szegedy (Nisan and Szegedy 1994). 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 (Göös et al. 2015) and developed by Ambainis, Balodis, Belovs, Lee, Santha, and Smotrovs (Ambainis et al. 2017) gave a nearly quartic separation between deterministic and quantum queries. For bounded-error randomized queries, Aaronson, Ben-David, and Kothari (Aaronson et al. 2016) 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 (Tal 2020), and then \(3-o(1)\) by Bansal and Sinha (Bansal and Sinha 2021) and independently Sherstov, Storozhenko, and Wu (Sherstov et al. 2023). On the upper-bound side, Aaronson, Ben-David, Kothari, Rao, and Tal (Aaronson et al. 2021), using Huang’s sensitivity theorem (Huang 2019), proved \(\mathrm D(f)=O(\mathrm Q(f)^4)\). They conjectured that randomized complexity satisfies the stronger relation \(\mathrm R(f)=O(\mathrm Q(f)^3)\) (Aaronson et al. 2021, Conjecture 2). Theorem 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 (Dürr and Høyer 1996), sink finding (Sun et al. 2004), and king finding in tournaments (Mande et al. 2023) provide related search procedures. Recent constructions of Ben-David and Kothari (Ben-David and Kothari 2026) and Ambainis, Iraids, and Kokainis (Ambainis et al. 2026) 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 analysesThe 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 (Shaltiel 2003; Drucker 2012); 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 6 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. ConventionsWe 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 pointersWe 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\geq 2\) 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 circuitWe use the \(k\)-fold Forrelation problem introduced by Aaronson and Ambainis (Aaronson and Ambainis 2018), with the thresholds analyzed by Bansal and Sinha (Bansal and Sinha 2021). 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 \[ \Phi(z_1,\ldots,z_k) =u^{\mathsf T}D_{z_1}H D_{z_2}H\cdots H D_{z_k}u, \qquad \delta=2^{-5k}. \tag{3}\] Define the partial Boolean function \(P=P_{k,m}\) on \(km\) bits by \[ P(z_1,\ldots,z_k)= \begin{cases} 1,&\Phi(z_1,\ldots,z_k)\geq\delta,\\ 0,&|\Phi(z_1,\ldots,z_k)|\leq\delta/2, \end{cases} \tag{4}\] 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. For each fixed integer \(k\geq2\), the functions \(P_{k,m}\) have the following properties.
Proof. Theorem 1.3 and Corollary 1.4 of Bansal and Sinha (Bansal and Sinha 2021) apply to exactly the normalized form and thresholds in (3)–(4). They give, for fixed \(k\) and error \(1/3\), \[\mathrm R(P_{k,m})= \Omega_k\!\left( \left(\frac{m}{\log(km)}\right)^{1-1/k} \right).\] 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 \[N=z_1^{\mathsf T}W D_{z_2}W\cdots W D_{z_k}(1,\ldots,1)^{\mathsf T}\] is an integer, and \[\Phi=\frac{N}{M_{k,m}}, \qquad M_{k,m}=m(\sqrt m)^{k-1}.\] 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 \[2^{5k}N\geq M_{k,m}, \qquad 2^{5k+1}|N|\leq M_{k,m}.\] 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 functionSet \[ r=\lceil20\log_2m\rceil, \qquad \ell=\log_2m. \tag{6}\] The input has \(m\) columns. Column \(i\in[m]\) contains the following bits:
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 \[ s_i=(P(A_{i,1}),\ldots,P(A_{i,r})) \tag{7}\] contains correct evaluation transcripts and pointers satisfying \[ X_j[p_{i,s_i,j}]=0\qquad\text{for every }j\ne i. \tag{8}\] 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 (Aaronson et al. 2016), while pointers between columns also occur in earlier query-complexity separations (Göös et al. 2015; Ambainis et al. 2017). 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 3. 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 \[K_{k,m}=m+(m-1)+r(S_{k,m}+2) =O_k(m(\log m)^3)\] 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 comparisonsWe 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 (Sun et al. 2004; Mande et al. 2023; Ben-David and Kothari 2026). 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 distributionThe 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 (Boyer et al. 1998; Brassard et al. 2002); we give the details because the distribution, as well as the success probability, is used in the tournament. Lemma 4 (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 \(\lvert g\rangle\). Let \(0<\gamma\le1/2\) and \(0<\eta<1/2\). There is a procedure using \[O\bigl(\gamma^{-1/2}\log(1/\eta)\bigr)\] calls to \(A\) and \(A^{-1}\) that either reports failure or produces a successful outcome. Conditional on success, the output state is \(\lvert 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 \[A\lvert0\rangle =\sin\theta\lvert g\rangle+\cos\theta\lvert b\rangle, \qquad 0<\theta<\pi/2,\] where the two normalized vectors lie in the successful and unsuccessful subspaces. Reflection about \(A\lvert0\rangle\), followed in the appropriate order by a phase flip of the success bit, gives after \(\ell\) Grover iterations the state \[\sin((2\ell+1)\theta)\lvert g\rangle +\cos((2\ell+1)\theta)\lvert b\rangle.\] 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 \(\lvert0\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 \[\sin(2\theta)=2\sqrt{p(1-p)}\ge\sqrt\gamma.\] Summing a geometric progression bounds the averaged success probability in the second choice by \[ \frac1M\sum_{\ell=0}^{M-1}\sin^2((2\ell+1)\theta) \ge \frac12-\frac{1}{2M\abs{\sin(2\theta)}} \ge\frac{9}{20}. \tag{9}\] 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 \(\lvert 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 tournamentFix 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 \[ a_{ij}+a_{ji}=1\quad(i\ne j),\qquad a_{ii}=0. \tag{10}\] The following result is pointwise in the fixed oracle input; its probabilities are over the algorithm’s internal randomness and measurements. Proposition 5 (A tournament for probabilistic comparisons). For \(m\ge2\), put \[T=\lceil\log(1000m)\rceil, \qquad \epsilon=\frac{1}{1000T}.\] 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 \[O\bigl(c\sqrt m\,T^2\log T\bigr)\] queries on every branch and returning a list of at most \(T\) candidates with the following guarantee. If \(i_\ast\in[m]\) satisfies \[ a_{i_\ast j}\ge1-\epsilon\qquad(j\ne i_\ast), \tag{11}\] then the list contains \(i_\ast\) 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_iw_i\). When \(W>0\), sample a pivot \(p\) with probability \(w_p/W\), append it to the list, and update \[ w_i\longleftarrow w_i a_{ip}\qquad(i\in[m]). \tag{12}\] 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 \[\begin{align*} \mathbb E[W_{\mathrm{new}}\mid w] &=\frac{1}{W}\sum_{p,i}w_pw_i a_{ip}\\ &=\frac{W^2-\sum_iw_i^2}{2W}\le\frac W2. \tag{13}\end{align*}\] The same inequality holds when \(W=0\), so after \(T\) steps \(\mathbb EW_T\le m/2^T\). If a candidate \(i_\ast\) satisfying (11) has never been selected, its final weight is at least \[(1-\epsilon)^T\ge1-T\epsilon>\frac12.\] In particular, the process cannot reach zero total weight before selecting it. Markov’s inequality implies \[ \Pr[i_\ast\text{ absent from the ideal list}] \le\Pr[W_T\ge1/2]\le\frac{2m}{2^T}. \tag{14}\] 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 \[ \frac1{\sqrt m}\sum_{i=1}^m \lvert i\rangle\bigotimes_{b=1}^t \lvert\phi(i,p_b)\rangle. \tag{15}\] 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 \[\prod_{b=1}^t a_{i p_b}=w_i.\] 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 4 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_\ast\) 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_\ast\) has entered the list, later termination cannot remove it. At stage \(t\), the preparation and its inverse use \(O(c(t+1))\) queries. Lemma 4 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 listWe 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 5. 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 \[O_k\bigl(r\log(r/\epsilon)\bigr)=(\log m)^{O_k(1)}\] 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_\ast\) is a winner, then \(X_{i_\ast}\) is all ones. No opponent, at any decoded address, can point to a zero there. When the address of \(i_\ast\) is correctly decoded, its own certificate points to a zero in every other column. Thus \[a_{i_\ast j}\ge1-\epsilon\qquad(j\ne i_\ast),\] regardless of whether the opponent’s address instances are defined. Proposition 5 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 3. 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 4, with \(\gamma=1/K\) and \(\eta=\epsilon\), searches for a failed test in \[O\bigl(\sqrt K\log(1/\epsilon)\log m\bigr) =\sqrt m(\log m)^{O_k(1)}\] 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 \[\frac{2m}{2^T}+T\epsilon+\epsilon<\frac13.\] The comparisons, tournament, and at most \(T\) verifications prove Proposition 6. For every fixed \(k\ge2\), the total functions of Section 2 satisfy \[\mathrm Q(F_{k,m})\le\sqrt m(\log m)^{O_k(1)}.\] 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 boundWe 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 queriesWe first record the precise amplification fact needed for address guessing. We use the capped direct-product argument developed by Drucker (Drucker 2012, sec. 1.3 and Lemmas 3.1–3.2), following earlier work of Shaltiel (Shaltiel 2003). Its query limit is imposed separately on each input, while queries to different inputs may be interleaved adaptively. Lemma 7. Let \(P\colon\mathcal D\to\{0,1\}\), where \(\mathcal D\subseteq\{0,1\}^n\), let \(\mu\) be a distribution on \(\mathcal 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 \[(P(U_1),\ldots,P(U_r)).\] 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 \[ \mathbb E[V_h(\tau')\mid\tau]\leq V_h(\tau), \tag{16}\] 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 \[\mathbb E\!\left[ \prod_{j=1}^r V_j(\tau')\,\middle|\,\tau \right] \leq \prod_{j=1}^r V_j(\tau).\] 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 \[\prod_{h=1}^r \max_{b\in\{0,1\}}\Pr(P(U_h)=b\mid\tau) \leq \prod_{h=1}^r V_h(\tau).\] 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\leq 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 (Yao 1977), applied to the payoff that the answer is correct, gives \[\begin{aligned} &\max_{\text{distributions on depth-$L$ trees}} \min_{x\in\operatorname{dom}P}\Pr(\text{correct on }x)\\ &\hspace{2em}= \min_{\mu}\max_{\text{depth-$L$ trees }T} \Pr_{x\sim\mu}(T(x)=P(x)). \end{aligned}\] 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 7 therefore bounds the success probability of guessing \(r\) independent answers by \((2/3)^r\). Coupled zero and one inputsProposition 8. For each fixed integer \(k\geq2\) and every sufficiently large power of four \(m\), the total function of Section 2 satisfies \[ \mathrm R(F_{k,m})> G:=\left\lfloor\frac{mL}{100}\right\rfloor, \qquad L=\left\lfloor\frac{m^{1-1/k}}{(\log_2m)^2}\right\rfloor. \tag{17}\] 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 \[ \Pr(\text{the dummy run queries }X_I[J_I]) +\Pr(\text{the dummy run queries any bit of }B_{I,s_I}). \tag{18}\] 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 \[\mathbb E Z\leq\frac{4G}{m}.\] The dummy run is independent of \(I\), so \[ \Pr(\text{the dummy run queries }X_I[J_I]) =\frac{\mathbb E Z}{m}\leq\frac{4G}{m^2}. \tag{19}\] 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 \[ \Pr(I\text{ is heavy})\leq\frac{G}{mL}. \tag{20}\] For the other columns we use Lemma 7. 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 7, 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 \[ \Pr\bigl(i\text{ is nonheavy and the $t$th query is in }B_{i,s_i}\bigr) \leq (2/3)^r. \tag{21}\] Union bounding over \(t\) and averaging over the independent uniform choice of \(I\), then adding (20), yields \[ \Pr(\text{the dummy run queries }B_{I,s_I}) \leq\frac{G}{mL}+G(2/3)^r. \tag{22}\] Equations (18), (19), and (22) bound the difference of output probabilities by \[ \frac{4G}{m^2}+\frac{G}{mL}+G(2/3)^r. \tag{23}\] For all sufficiently large \(m\), we have \(1\leq L\leq m\) and \(G\leq mL/100\). The first two terms are therefore at most \(4/100\) and \(1/100\), respectively. Moreover, (6) gives \[G(2/3)^r \leq\frac1{100}m^{\,2-20\log_2(3/2)}=o(1).\] 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 \(\mathrm R(F_{k,m})>G\). ◻ For fixed \(k\), Proposition 8 implies \[\mathrm R(F_{k,m})= \Omega_k\!\left(\frac{m^{2-1/k}}{(\log m)^2}\right).\] 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 powerWe combine the quantitative bounds before recalling the universal upper bound in the appendix. Proof of Theorem 1. For each fixed \(k\ge2\), Proposition 6 gives \(\mathrm Q(F_{k,m})\le C_k\sqrt m(\log m)^{b_k}\) for suitable constants. Proposition 8 gives \[\mathrm R(F_{k,m})> \left\lfloor\frac m{100} \left\lfloor\frac{m^{1-1/k}}{(\log m)^2}\right\rfloor \right\rfloor \ge c_k\frac{m^{2-1/k}}{(\log m)^2}\] 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 \[\frac{\mathrm R(F_{k,m})}{(1+\mathrm Q(F_{k,m}))^\alpha} \ge c_{k,\alpha} \frac{m^{2-1/k-\alpha/2}} {(\log m)^{2+\alpha b_k}} \longrightarrow\infty.\] Hence no exponent smaller than four belongs to the set in (1). Conversely, Theorem 9 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 boundFor completeness, we prove the upper bound used in Theorem 1. The argument is the one of Aaronson, Ben-David, Kothari, Rao, and Tal (Aaronson et al. 2021), combining Huang’s signed-cube method (Huang 2019) 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 \(\operatorname{bs}(f)\) is the maximum, over \(x\), of the number of pairwise disjoint sensitive blocks at \(x\). Theorem 9 ((Aaronson et al. 2021)). Every total Boolean function satisfies \[\mathrm R(f)\le\mathrm D(f)=O((1+\mathrm Q(f))^4).\] We establish the three ingredients separately. All matrix norms below are operator norms for the Euclidean norm. Lemma 10 (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 \[(\Gamma_i)_{xy}=\Gamma_{xy}\,\mathbf1_{\{x_i\ne y_i\}}.\] Then, for an absolute constant \(c>0\), \[\mathrm Q(f)\ge c\frac{\norm{\Gamma}}{\max_i\norm{\Gamma_i}}.\] Proof. This is the spectral adversary argument of Barnum, Saks, and Szegedy (Barnum et al. 2003); see also Špalek and Szegedy (Špalek and Szegedy 2006). 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 \(\norm{\Gamma}\). Track \[W_t=\sum_{x,y}v_xv_y\Gamma_{xy} \langle\psi_x^t\mid\psi_y^t\rangle.\] Initially the states are input-independent, so \(W_0=v^\top\Gamma v=\norm{\Gamma}\). Input-independent unitaries preserve every overlap. Immediately before a query, write the normalized state as \[\lvert\psi_x\rangle=\sum_i\lvert i\rangle\lvert\phi_{x,i}\rangle, \qquad \sum_i\norm{\phi_{x,i}}^2=1.\] 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\norm{\phi_{x,i}}\norm{\phi_{y,i}}\), since the difference between the relevant unitary and the identity has norm at most two. Put \(u_i(x)=v_x\norm{\phi_{x,i}}\). Nonnegativity of the weights gives \[\begin{align*} \abs{W_{t+1}-W_t} &\le2\sum_i u_i^\top\Gamma_i u_i\\ &\le2\max_i\norm{\Gamma_i}\sum_i\norm{u_i}^2 =2\max_i\norm{\Gamma_i}. \end{align*}\] 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\sqrt2/3\). Hence the final value satisfies \[\abs{W_{\mathrm{final}}} \le\frac{2\sqrt2}{3}\sum_{x,y}v_xv_y\Gamma_{xy} =\frac{2\sqrt2}{3}\norm{\Gamma}.\] 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)=\norm{S_f}\). Lemma 11. For every nonconstant total Boolean function, \[\operatorname{bs}(f)=O(\mathrm Q(f)^2),\qquad \lambda(f)=O(\mathrm Q(f)).\] 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 10 gives \(\mathrm Q(f)=\Omega(\sqrt b)\). This recovers the usual block-sensitivity lower bound for quantum queries (Beals et al. 2001). 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 10 gives \(\mathrm Q(f)=\Omega(\lambda(f))\), as in (Aaronson et al. 2021). ◻ Lemma 12 ((Aaronson et al. 2021), using (Huang 2019)). Every nonconstant total Boolean function satisfies \(\deg(f)\le\lambda(f)^2\). Proof. Write the function with sign inputs and sign outputs, and set \(d=\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 \[U=\{x\in\{-1,1\}^d:g(x)=\sigma x_1\cdots x_d\}\] 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 \[H'_1=\begin{pmatrix}0&1\\1&0\end{pmatrix}, \qquad H'_{j+1}=\begin{pmatrix}H'_j&I\\I&-H'_j\end{pmatrix}.\] 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=\abs v\) entrywise. If \(A_U\) is the unsigned adjacency induced on \(U\), then \[u^\top A_Uu\ge v^\top H'_dv=\sqrt d\,\norm v^2 =\sqrt d\,\norm u^2.\] 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 13 ((Midrijanis 2004)). Every total Boolean function satisfies \(\mathrm D(f)\le\operatorname{bs}(f)\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 \(\deg(f)\) variables. The stated deterministic bound follows. ◻ Proof of Theorem 9. For nonconstant \(f\), Lemmas 11 and 12 give both \(\operatorname{bs}(f)=O(\mathrm Q(f)^2)\) and \(\deg(f)=O(\mathrm Q(f)^2)\). Lemma 13 then gives \(\mathrm D(f)=O(\mathrm Q(f)^4)\). Since a deterministic algorithm is also randomized, \(\mathrm R(f)\le\mathrm D(f)\). Constant functions require no queries. ◻
Aaronson, Scott, and Andris Ambainis. 2018. “Forrelation: A Problem That Optimally Separates Quantum from Classical Computing.” SIAM Journal on Computing 47 (3): 982–1038. https://doi.org/10.1137/15M1050902.
Aaronson, Scott, Shalev Ben-David, and Robin Kothari. 2016. “Separations in Query Complexity Using Cheat Sheets.” Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 863–76. https://doi.org/10.1145/2897518.2897644.
Aaronson, Scott, Shalev Ben-David, Robin Kothari, Shravas Rao, and Avishay Tal. 2021. “Degree Vs. Approximate Degree and Quantum Implications of Huang’s Sensitivity Theorem.” Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, 1330–42. https://doi.org/10.1145/3406325.3451047.
Ambainis, Andris, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, and Juris Smotrovs. 2017. “Separations in Query Complexity Based on Pointer Functions.” Journal of the ACM 64 (5): 32:1–24. https://doi.org/10.1145/3106234.
Ambainis, Andris, Jānis Iraids, and Martins Kokainis. 2026. Near-Optimal Separations of Certificate Complexity from Randomized and Quantum Query Complexity. https://arxiv.org/abs/2609.11664.
Bansal, Nikhil, and Makrand Sinha. 2021. “\(k\)-Forrelation Optimally Separates Quantum and Classical Query Complexity.” Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, 1303–16. https://doi.org/10.1145/3406325.3451040.
Barnum, Howard, Michael E. Saks, and Mario Szegedy. 2003. “Quantum Query Complexity and Semi-Definite Programming.” Proceedings of the 18th Annual IEEE Conference on Computational Complexity, 179–93. https://doi.org/10.1109/CCC.2003.1214419.
Beals, Robert, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf. 2001. “Quantum Lower Bounds by Polynomials.” Journal of the ACM 48 (4): 778–97. https://doi.org/10.1145/502090.502097.
Ben-David, Shalev, and Robin Kothari. 2026. Randomized Query Complexity Can Beat Certificate Complexity. https://arxiv.org/abs/2609.15063.
Bennett, Charles H., Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. 1997. “Strengths and Weaknesses of Quantum Computing.” SIAM Journal on Computing 26 (5): 1510–23. https://doi.org/10.1137/S0097539796300933.
Boyer, Michel, Gilles Brassard, Peter Høyer, and Alain Tapp. 1998. “Tight Bounds on Quantum Searching.” Fortschritte Der Physik 46 (4–5): 493–506. https://arxiv.org/abs/quant-ph/9605034.
Brassard, Gilles, Peter Høyer, Michele Mosca, and Alain Tapp. 2002. “Quantum Amplitude Amplification and Estimation.” In Quantum Computation and Quantum Information, edited by Samuel J. Lomonaco Jr., vol. 305. Contemporary Mathematics. American Mathematical Society. https://doi.org/10.1090/conm/305/05215.
Drucker, Andrew. 2012. “Improved Direct Product Theorems for Randomized Query Complexity.” Computational Complexity 21 (2): 197–244. https://doi.org/10.1007/s00037-012-0043-7.
Dürr, Christoph, and Peter Høyer. 1996. A Quantum Algorithm for Finding the Minimum. https://arxiv.org/abs/quant-ph/9607014.
Göös, Mika, Toniann Pitassi, and Thomas Watson. 2015. “Deterministic Communication Vs. Partition Number.” Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science, 1077–88. https://doi.org/10.1109/FOCS.2015.70.
Grover, Lov K. 1996. “A Fast Quantum Mechanical Algorithm for Database Search.” Proceedings of the 28th Annual ACM Symposium on Theory of Computing, 212–19. https://doi.org/10.1145/237814.237866.
Huang, Hao. 2019. “Induced Subgraphs of Hypercubes and a Proof of the Sensitivity Conjecture.” Annals of Mathematics 190 (3): 949–55. https://doi.org/10.4007/annals.2019.190.3.6.
Mande, Nikhil S., Manaswi Paraashar, and Nitin Saurabh. 2023. “Randomized and Quantum Query Complexities of Finding a King in a Tournament.” 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Leibniz international proceedings in informatics, vol. 284: 30:1–19. https://doi.org/10.4230/LIPIcs.FSTTCS.2023.30.
Midrijanis, Gatis. 2004. Exact Quantum Query Complexity for Total Boolean Functions. https://arxiv.org/abs/quant-ph/0403168.
Nisan, Noam. 1991. “CREW PRAMs and Decision Trees.” SIAM Journal on Computing 20 (6): 999–1007. https://doi.org/10.1137/0220062.
Nisan, Noam, and Mario Szegedy. 1994. “On the Degree of Boolean Functions as Real Polynomials.” Computational Complexity 4 (4): 301–13. https://doi.org/10.1007/BF01263419.
Shaltiel, Ronen. 2003. “Towards Proving Strong Direct Product Theorems.” Computational Complexity 12 (1–2): 1–22. https://doi.org/10.1007/s00037-003-0175-x.
Sherstov, Alexander A., Andrey A. Storozhenko, and Pei Wu. 2023. “An Optimal Separation of Randomized and Quantum Query Complexity.” SIAM Journal on Computing 52 (2): 525–67. https://doi.org/10.1137/22M1468943.
Špalek, Robert, and Mario Szegedy. 2006. “All Quantum Adversary Methods Are Equivalent.” Theory of Computing 2 (1): 1–18. https://doi.org/10.4086/toc.2006.v002a001.
Sun, Xiaoming, Andrew C. Yao, and Shengyu Zhang. 2004. “Graph Properties and Circular Functions: How Low Can Quantum Query Complexity Go?” Proceedings of the 19th Annual IEEE Conference on Computational Complexity, 286–93. https://doi.org/10.1109/CCC.2004.1313851.
Tal, Avishay. 2020. “Towards Optimal Separations Between Quantum and Randomized Query Complexities.” Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science, 228–39. https://doi.org/10.1109/FOCS46700.2020.00030.
Yao, Andrew Chi-Chih. 1977. “Probabilistic Computations: Toward a Unified Measure of Complexity.” Proceedings of the 18th Annual Symposium on Foundations of Computer Science, 222–27. https://doi.org/10.1109/SFCS.1977.24.
|
| ||||||||
|