Quantum computing · Theory (AI-assisted)
Separations Between Randomized and Exact Quantum Query Complexity for Boolean Functions
arXiv:2611.21189v1 ↗PDF ↗Submitted 16 November 2026
- Question
- How far can quantum algorithms beat randomized ones when the quantum algorithm must always be right? For total Boolean functions \(R(f)\le D(f)\le16Q_E(f)^3\) caps the gap at a polynomial, and the best published separation had been \(R=\widetilde\Omega(Q_E^{3/2})\). For partial functions, bounded-error quantum algorithms with \(O(1)\) queries against \(\Omega(n^{1-\varepsilon})\) randomized queries were known, and Girish and Servedio asked whether exact quantum algorithms can match that.
- Result
- A family of total functions with \(R(F)\ge q^2\,2^{-O(\sqrt{\log q})}\), where \(q=Q_E(F)\); and, for each fixed \(\varepsilon\in(0,1)\), partial functions on \(n\) bits with \(Q_E=O_\varepsilon(1)\) and \(R=\Omega_\varepsilon(n^{1-\varepsilon})\). Lifting with inner-product gadgets gives total communication functions with the same nearly quadratic gap and partial ones with \(O_\varepsilon(\log n)\) exact quantum against \(\Omega_\varepsilon(n^{1-\varepsilon})\) randomized communication.
The paper in detail
In the query model an algorithm learns its input only by asking for individual bits, and only the number of questions counts. Randomized algorithms \(R(f)\) and quantum algorithms \(Q(f)\) may err with probability \(1/3\); the exact quantum complexity \(Q_E(f)\) demands the right answer with certainty. A gap between \(R\) and \(Q_E\) is a quantum advantage that survives the strictest correctness requirement. For total functions, defined on every input, early exact algorithms gave constant-factor gains, Ambainis found the first superlinear gap, and pointer functions reached \(R=\widetilde\Omega(Q_E^{3/2})\). For partial functions, defined on a promise set, the strongest bounded-error separations come from Forrelation, which asks how strongly one Boolean function correlates with the Fourier transform of another.
Bounded-error quantum algorithms such as the one for Forrelation succeed with a probability that depends on the input, while exact algorithms need perfect cancellation. Amplitude amplification can turn a known success probability into certainty, but here it is unknown. The paper's answer, adapting a method of AIK26, is to arrange that every accepting branch of the computation contains the data that determines its success probability. A controlled rotation can then scale the probability to exactly \(1/4\), and one round of amplification finishes the job.
For total functions the input has \(m\) columns, each with \(b\) data bits, an address made of Forrelation instances whose answers form a label, and a table of pointer cells. A column wins if its data are all ones, its address is valid, and the cell selected by its label points to a zero in every other column; at most one column can win. The quantum algorithm decodes all labels, runs a knockout tournament in which each comparison reads two pointers and the bits they point to, and then reads the final candidate's address and data in full. The winner survives every comparison whenever its own label is decoded correctly, so the acceptance probability equals the decoder's success probability on the winner's address, which the algorithm has just read. Rescaling and amplification give an exact algorithm with \(m^{1+o(1)}\) queries.
The randomized lower bound plants a winner. A negative input hides one zero in each column's data; the positive input deletes the zero in a uniformly random column and redirects that column's true pointer cell. Until a randomized algorithm touches one of these places it sees identical answers, and touching them requires either finding a hidden zero among \(b\) bits or decoding a Forrelation label, which is hard. The resulting inequality forces \(m^{2-o(1)}\) queries. For partial functions the address is promised to be a Hadamard encoding, decodable with Bernstein–Vazirani in constant queries, and the exact success probability is written, also Hadamard-encoded, in the true cell; the quantum algorithm needs \(O_\varepsilon(1)\) queries while randomized algorithms need \(\Omega(M^{1-1/k-2/d}/\log M)\) on inputs of length \(\Theta(M^{1+1/d})\).
Transferable methods
Exact amplification from a self-reported success probability
Amplitude amplification reaches certainty only when the initial success probability is known in advance. The construction makes every accepting branch carry the input data that determine that probability, so a controlled rotation can rescale it to exactly \(1/4\) before a single amplification round.
If a circuit \(W\) accepts with probability \(\sin^2\theta\), one amplification round gives \(\sin^2(3\theta)\). At \(\sin^2\theta=\tfrac14\), \(\theta=\pi/6\) and \(\sin^2(\pi/2)=1\). So if \[\|\Pi W_x\ket0\|^2=\frac{f(x)}{4}\] for every valid input, three calls to \(W\) or \(W^\dagger\) compute \(f\) exactly (Lemma 2.4).
Why acceptance equals the decoder's success probability: write the state after decoding as \(\sum_z\ket z\ket{\psi_{X,z}}\) over label strings \(z\). Given \(z\), the tournament and verification are deterministic and accept exactly when the winner's label is right, because a correctly labelled winner points to a zero in every opponent while no pointer can find a zero in its own all-ones data. Hence \[\Pr[A=1]=\sum_{z:\,z_w=P(x_w)}\|\psi_{X,z}\|^2=\sigma(x_w).\]
Append a qubit \(B\) and, controlled on \(A=1\) and the address register holding \(x\), rotate \(B\) so that it reads 1 with probability \(1/(4\sigma(x))\), which lies in \([1/4,3/8]\) because \(\sigma\ge2/3\). Every accepting branch holds the same \(x_w\), so \(\Pr[A=B=1]=\sigma(x_w)\cdot\frac1{4\sigma(x_w)}=\frac14\) on positive inputs and 0 on negative ones; the rotation needs no queries.
How to reuse it
Whenever a bounded-error subroutine's success probability is a known function of data the algorithm can afford to read, storing that data on the accepting branch and rescaling converts the subroutine into an exact one at constant cost. Arranging such self-certification is a general route from bounded-error to exact quantum speedups.
Planted-winner coupling for randomized lower bounds
To show that randomized algorithms need many queries, compare a negative input with a positive one that differs only in a few hidden places. With the same random coins, the algorithm sees identical answers until it touches one of those places, so the task reduces to bounding the probability of touching them.
Negative inputs hide one uniformly random zero in each column's data and draw each address from a hard Forrelation distribution; the positive input picks a uniform column \(w\), deletes its zero and redirects its true pointer cell. An algorithm making \(T\) queries reads more than half the data of at most \(2T/b\) columns; elsewhere each fresh data query finds the zero with probability at most \(2/b\), so the expected number of zeros found is at most \(4T/b\) and the chance of hitting the deleted one is at most \(4T/(mb)\).
Likewise, at most \(T/R_{\mathrm{addr}}\) columns receive more than \(R_{\mathrm{addr}}\) address queries, and using the true pointer cell after fewer address queries would predict a Forrelation label, which succeeds with probability at most \(m^{-5}\) per step. A correct algorithm must separate the two cases by \(1/3\), so \[\frac13\le\frac{4T}{mb}+\frac{T}{mR_{\mathrm{addr}}}+Tm^{-5},\] and with \(b=m^{1+o(1)}\) and \(R_{\mathrm{addr}}=m^{1-o(1)}\) this gives \(T\ge m^{2-o(1)}\).
Editorial reading of the gap: a randomized algorithm must examine about \(m\) columns at a cost of roughly \(b\) or \(R_{\mathrm{addr}}\) queries each, both about \(m\), hence \(m^2\). The quantum algorithm decodes all labels for \(m\cdot m^{o(1)}\) queries, compares cheaply, and reads only one column in full, hence \(m^{1+o(1)}\).
How to reuse it
Pointer and cheat-sheet constructions follow this pattern: verifying a certificate is cheap once found, but locating it requires solving a hard subproblem at many candidate places. A coupling with a planted certificate then yields a lower bound of order the number of places times the per-place hardness.
Context & limitations
Why it matters. The partial-function result answers Girish and Servedio: demanding zero error costs nothing asymptotically, since it matches the bounded-error separation of Bansal and Sinha and of Sherstov, Storozhenko and Wu. The nearly quadratic total separation, found independently of Chiruvella et al. this year, has a smaller subpolynomial loss. Both rest on one device: an algorithm that can read its own exact success probability on every accepting branch can rescale it to \(1/4\), after which one round of amplitude amplification makes it exact.
Limitations. Because \(D\le16Q_E^3\), a cubic gap is not excluded, and whether \(R\) can exceed \(Q_E^2\) for total functions stays open; the construction is quadratic only up to a \(2^{O(\sqrt{\log q})}\) factor, and its inputs are polynomially long. The constants for partial functions grow quickly as \(\varepsilon\to0\) (Forrelation order \(\lceil4/\varepsilon\rceil\) and \(\lceil12/\varepsilon\rceil\) address blocks), and all functions are built from Forrelation instances and pointers rather than natural problems. The author states that ChatGPT assisted with developing and organizing the constructions and proof arguments in Sections 3–4 and Appendix A, including the exact algorithms and the randomized lower bounds.