Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.35580

Quantum Query Complexity Beyond the Worst Case

Srinivasan Arunachalam, Yanlin Chen, Amin Shiraz Gilani

quant-phcs.CCSubmitted Sep 28, 2026• Announced Sep 29, 2026• 0 citations
arXivHTMLPDF

Abstract

Smoothed analysis is a central framework in classical algorithms for explaining the performance of algorithms beyond the worst case, often explaining why algorithms perform well in practice. We initiate a systematic study of its quantum counterpart and show the following results. $(1)$ We show that there is a total function whose smoothed quantum query complexity is exponentially smaller than its classical query complexity. $(2)$ We give near-tight characterizations of smoothed randomized and quantum query complexities for symmetric Boolean functions, unifying the worst-case complexity results of [Beals et al, FOCS'98] and average-case complexity results of [Ambainis and de Wolf, STACS'00]. $(3)$ We study string problems such as pattern matching and edit distance and, in various regimes, give polynomial to superpolynomial quantum speedups. Our main technical ingredients include a near-tight quantum algorithm for $\varepsilon$-approximating the number of collisions between two non-repetitive strings, improving the result of Le Gall and Ng [QIC'22]. Together, our results show that smoothing can reveal larger quantum speedups than worst-case analysis suggests, opening a path towards quantum advantage on more realistic inputs.

AI Summary

The paper studies quantum query complexity under smoothed input models: an adversarial input is randomly perturbed, and expected query cost is maximized over perturbation centers. In its basic model, correctness remains required on every input; smoothing interpolates between worst-case and uniform-average cost. For total Simon’s problem on an oracle $f:\{0,1\}^n\to\{0,1\}^n$, it obtains quantum smoothed complexity $O(n/\sigma)$, versus randomized $\Omega(2^{n/2})$, giving an exponential separation when $\sigma\geq1/\operatorname{poly}(n)$. The proof rerandomizes whole oracle outputs: smoothing creates singleton fibers whose uniform Fourier samples rapidly certify absence of a period; an exhaustive fallback preserves correctness. For every symmetric Boolean function, two transition-based parameters characterize randomized and quantum smoothed complexity up to polylogarithmic factors. The proof combines layerwise distinguishing bounds and adaptive weight estimation with averaging over perturbed Hamming weights. String applications include a $\widetilde O(\sqrt{n/m}\,2^{O(\sqrt{\log m})}/\sigma)$ pattern-matching algorithm in a match-preserving perturbation model, and tight-up-to-logarithms bounds $\widetilde\Theta(n/(\sigma m))$ classically and $\widetilde\Theta(\sqrt{n/(\sigma m)})$ quantumly for explicit patterns under independent text smoothing, when $\sigma m=\Omega(\log n)$. For smoothed edit distance $R$, an $O(1/\sigma)$-approximation uses $\widetilde O((n/R+n^{2/3}/R^{1/3})/\sigma)$ queries. Its ingredients include improved collision counting, quantum walks, variable-time approximate counting, and a reduction through non-repetitive strings. The results concern query rather than general running-time complexity. The string models differ: some preserve matches through coupled perturbations, while edit distance couples perturbations along a fixed longest common subsequence. Extension to running time and further problems remains open.

Little sign of AI-generated textAI use disclosedStrong assumptionsPossible error
We relied on GPT 5.5's help in proving Lemma~\ref{lem:localization}

Error found: The Total Simon upper-bound proof analyzes replacement of whole oracle outputs rather than the defined bitwise perturbation, and its singleton-fiber lemma is false for bitwise smoothing, although a direct disagreement-based Fourier-sampling argument repairs the separation.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Related papers

Average-case quantum query complexity

Andris Ambainis, Ronald de Wolf

We compare classical and quantum query complexities of total Boolean functions. It is known that for worst-case complexity, the gap between quantum and classical can be at most polynomial. We show that for average-case complexity under the uniform distribution, quantum algorithms can be exponentially faster than classical algorithms. Under non-uniform distributions the gap can even be super-exponential. We also prove some general bounds for average-case complexity and show that the average-case quantum complexity of MAJORITY under the uniform distribution is nearly quadratically better than the classical complexity. A preliminary version of this paper appeared in the Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science (STACS'2000) (Lecture Notes in Computer Science vol 1770) (Berlin: Springer).

Journal of Physics A Mathematical and General•Aug 24, 2001•19 citations

Average-Case Quantum Query Complexity

Andris Ambainis, Ronald de Wolf

We compare classical and quantum query complexities of total Boolean functions. It is known that for worst-case complexity, the gap between quantum and classical can be at most polynomial. We show that for average-case complexity under the uniform distribution, quantum algorithms can be exponentially faster than classical algorithms. Under non-uniform distributions the gap can even be super-exponential. We also prove some general bounds for average-case complexity and show that the average-case quantum complexity of MAJORITY under the uniform distribution is nearly quadratically better than the classical complexity.

arXiv:quant-ph/9904079•Lecture notes in computer science•Apr 23, 1999•15 citations

Query Complexity: Worst-Case Quantum Versus Average-Case Classical

Scott Aaronson

In this note we investigate the relationship between worst-case quantum query complexity and average-case classical query complexity. Specifically, we show that if a quantum computer can evaluate a total Boolean function f with bounded error using T queries in the worst case, then a deterministic classical computer can evaluate f using O(T^5) queries in the average case, under a uniform distribution of inputs. If f is monotone, we show furthermore that only O(T^3) queries are needed. Previously, Beals et al. (1998) showed that if a quantum computer can evaluate f with bounded error using T queries in the worst case, then a deterministic classical computer can evaluate f using O(T^6) queries in the worst case, or O(T^4) if f is monotone. The optimal bound is conjectured to be O(T^2), but improving on O(T^6) remains an open problem. Relating worst-case quantum complexity to average-case classical complexity may suggest new ways to reduce the polynomial gap in the ordinary worst-case versus worst-case setting.

arXiv:cs/0001013•Jan 19, 2000•0 citations

Quantum speedups in query complexity

Shalev Ben-David

In this thesis, we study randomized and quantum algorithms in the query complexity model.We investigate when and by how much quantum algorithms provide a speedup over the best possible classical algorithm in the query complexity setting.We introduce a total Boolean function that exhibits a power 2.5 quantum speedup compared to the best possible randomized algorithm.In the process, we introduce the "cheat sheet" method for turning partial Boolean functions into total Boolean functions, and examine some of its other applications.We also study lower bound techniques for randomized algorithms.We introduce a measure called randomized sabotage complexity which lower bounds randomized query complexity and behaves well under compositions.This tool for controlling the randomized query complexity of composed functions combines nicely with the cheat sheet technique, which often features composed functions in its applications.In addition, we study the quantum analogue of this tool, and use it to show a new power 5 relationship between zero-error and bounded-error quantum query complexity.Finally, we characterize the total Boolean functions that exhibit exponential quantum speedups when their domain is restricted to an arbitrarily chosen set.We show that such a "sculpting" of a quantum speedup is possible if and only if the original total function has many inputs with large certificate complexity.Along the way, we also show that functions defined on very small domains or that are very unbalanced can display at most a quadratic quantum speedup.

•Jan 1, 2017•0 citations

Pseudo-deterministic Quantum Algorithms

Hugo Aaronson, Tom Gur, Jiawei Li

We initiate a systematic study of pseudo-deterministic quantum algorithms. These are quantum algorithms that, for any input, output a canonical solution with high probability. Focusing on the query complexity model, our main contributions include the following complexity separations, which require new lower bound techniques specifically tailored to pseudo-determinism: - We exhibit a problem, Avoid One Encrypted String (AOES), whose classical randomized query complexity is $O(1)$ but is maximally hard for pseudo-deterministic quantum algorithms ($Ω(N)$ query complexity). - We exhibit a problem, Quantum-Locked Estimation (QL-Estimation), for which pseudo-deterministic quantum algorithms admit an exponential speed-up over classical pseudo-deterministic algorithms ($O(\log(N))$ vs. $Θ(\sqrt{N})$), while the randomized query complexity is $O(1)$. Complementing these separations, we show that for any total problem $R$, pseudo-deterministic quantum algorithms admit at most a quintic advantage over deterministic algorithms, i.e., $D(R) = \tilde O(psQ(R)^5)$. On the algorithmic side, we identify a class of quantum search problems that can be made pseudo-deterministic with small overhead, including Grover search, element distinctness, triangle finding, $k$-sum, and graph collision.

quant-pharXiv:2602.17647•Leibniz international proceedings in informatics•Feb 20, 2026•2 citations

Average/Worst-Case Gap of Quantum Query Complexities by On-Set Size

Andris Ambainis, Kazuo Iwama, Masaki Nakanishi +4 more

This paper considers the query complexity of the functions in the family F_{N,M} of N-variable Boolean functions with onset size M, i.e., the number of inputs for which the function value is 1, where 1<= M <= 2^{N}/2 is assumed without loss of generality because of the symmetry of function values, 0 and 1. Our main results are as follows: (1) There is a super-linear gap between the average-case and worst-case quantum query complexities over F_{N,M} for a certain range of M. (2) There is no super-linear gap between the average-case and worst-case randomized query complexities over F_{N,M} for every M. (3) For every M bounded by a polynomial in N, any function in F_{N,M} has quantum query complexity Theta (sqrt{N}). (4) For every M=O(2^{cN}) with an arbitrary large constant c<1, any function in F_{N,M} has randomized query complexity Omega (N).

arXiv:0908.2468•Aug 18, 2009•9 citations
Smoothed analysis is a central framework in classical algorithms for explaining the performance of algorithms beyond the worst case, often explaining why algorithms perform well in practice. We initiate a systematic study of its quantum counterpart and show the following results. (1)(1)(1) We show that there is a total function whose smoothed quantum query complexity is exponentially smaller than its classical query complexity. (2)(2)(2) We give near-tight characterizations of smoothed randomized and quantum query complexities for symmetric Boolean functions, unifying the worst-case complexity results of [Beals et al, FOCS'98] and average-case complexity results of [Ambainis and de Wolf, STACS'00]. (3)(3)(3) We study string problems such as pattern matching and edit distance and, in various regimes, give polynomial to superpolynomial quantum speedups. Our main technical ingredients include a near-tight quantum algorithm for ε\varepsilonε-approximating the number of collisions between two non-repetitive strings, improving the result of Le Gall and Ng [QIC'22]. Together, our results show that smoothing can reveal larger quantum speedups than worst-case analysis suggests, opening a path towards quantum advantage on more realistic inputs.
The paper studies quantum query complexity under smoothed input models: an adversarial input is randomly perturbed, and expected query cost is maximized over perturbation centers. In its basic model, correctness remains required on every input; smoothing interpolates between worst-case and uniform-average cost.
For total Simon’s problem on an oracle f:{0,1}n→{0,1}nf:\{0,1\}^n\to\{0,1\}^nf:{0,1}n→{0,1}n, it obtains quantum smoothed complexity O(n/σ)O(n/\sigma)O(n/σ), versus randomized Ω(2n/2)\Omega(2^{n/2})Ω(2n/2), giving an exponential separation when σ≥1/poly⁡(n)\sigma\geq1/\operatorname{poly}(n)σ≥1/poly(n). The proof rerandomizes whole oracle outputs: smoothing creates singleton fibers whose uniform Fourier samples rapidly certify absence of a period; an exhaustive fallback preserves correctness.
For every symmetric Boolean function, two transition-based parameters characterize randomized and quantum smoothed complexity up to polylogarithmic factors. The proof combines layerwise distinguishing bounds and adaptive weight estimation with averaging over perturbed Hamming weights.
String applications include a O~(n/m 2O(log⁡m)/σ)\widetilde O(\sqrt{n/m}\,2^{O(\sqrt{\log m})}/\sigma)O(n/m​2O(logm​)/σ) pattern-matching algorithm in a match-preserving perturbation model, and tight-up-to-logarithms bounds Θ~(n/(σm))\widetilde\Theta(n/(\sigma m))Θ(n/(σm)) classically and Θ~(n/(σm))\widetilde\Theta(\sqrt{n/(\sigma m)})Θ(n/(σm)​) quantumly for explicit patterns under independent text smoothing, when σm=Ω(log⁡n)\sigma m=\Omega(\log n)σm=Ω(logn). For smoothed edit distance RRR, an O(1/σ)O(1/\sigma)O(1/σ)-approximation uses O~((n/R+n2/3/R1/3)/σ)\widetilde O((n/R+n^{2/3}/R^{1/3})/\sigma)O((n/R+n2/3/R1/3)/σ) queries. Its ingredients include improved collision counting, quantum walks, variable-time approximate counting, and a reduction through non-repetitive strings.
The results concern query rather than general running-time complexity. The string models differ: some preserve matches through coupled perturbations, while edit distance couples perturbations along a fixed longest common subsequence. Extension to running time and further problems remains open.
We compare classical and quantum query complexities of total Boolean functions. It is known that for worst-case complexity, the gap between quantum and classical can be at most polynomial. We show that for average-case complexity under the uniform distribution, quantum algorithms can be exponentially faster than classical algorithms. Under non-uniform distributions the gap can even be super-exponential. We also prove some general bounds for average-case complexity and show that the average-case quantum complexity of MAJORITY under the uniform distribution is nearly quadratically better than the classical complexity. A preliminary version of this paper appeared in the Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science (STACS'2000) (Lecture Notes in Computer Science vol 1770) (Berlin: Springer).
We compare classical and quantum query complexities of total Boolean functions. It is known that for worst-case complexity, the gap between quantum and classical can be at most polynomial. We show that for average-case complexity under the uniform distribution, quantum algorithms can be exponentially faster than classical algorithms. Under non-uniform distributions the gap can even be super-exponential. We also prove some general bounds for average-case complexity and show that the average-case quantum complexity of MAJORITY under the uniform distribution is nearly quadratically better than the classical complexity.
In this note we investigate the relationship between worst-case quantum query complexity and average-case classical query complexity. Specifically, we show that if a quantum computer can evaluate a total Boolean function f with bounded error using T queries in the worst case, then a deterministic classical computer can evaluate f using O(T^5) queries in the average case, under a uniform distribution of inputs. If f is monotone, we show furthermore that only O(T^3) queries are needed. Previously, Beals et al. (1998) showed that if a quantum computer can evaluate f with bounded error using T queries in the worst case, then a deterministic classical computer can evaluate f using O(T^6) queries in the worst case, or O(T^4) if f is monotone. The optimal bound is conjectured to be O(T^2), but improving on O(T^6) remains an open problem. Relating worst-case quantum complexity to average-case classical complexity may suggest new ways to reduce the polynomial gap in the ordinary worst-case versus worst-case setting.
In this thesis, we study randomized and quantum algorithms in the query complexity model.We investigate when and by how much quantum algorithms provide a speedup over the best possible classical algorithm in the query complexity setting.We introduce a total Boolean function that exhibits a power 2.5 quantum speedup compared to the best possible randomized algorithm.In the process, we introduce the "cheat sheet" method for turning partial Boolean functions into total Boolean functions, and examine some of its other applications.We also study lower bound techniques for randomized algorithms.We introduce a measure called randomized sabotage complexity which lower bounds randomized query complexity and behaves well under compositions.This tool for controlling the randomized query complexity of composed functions combines nicely with the cheat sheet technique, which often features composed functions in its applications.In addition, we study the quantum analogue of this tool, and use it to show a new power 5 relationship between zero-error and bounded-error quantum query complexity.Finally, we characterize the total Boolean functions that exhibit exponential quantum speedups when their domain is restricted to an arbitrarily chosen set.We show that such a "sculpting" of a quantum speedup is possible if and only if the original total function has many inputs with large certificate complexity.Along the way, we also show that functions defined on very small domains or that are very unbalanced can display at most a quadratic quantum speedup.
We initiate a systematic study of pseudo-deterministic quantum algorithms. These are quantum algorithms that, for any input, output a canonical solution with high probability. Focusing on the query complexity model, our main contributions include the following complexity separations, which require new lower bound techniques specifically tailored to pseudo-determinism: - We exhibit a problem, Avoid One Encrypted String (AOES), whose classical randomized query complexity is O(1)O(1)O(1) but is maximally hard for pseudo-deterministic quantum algorithms (Ω(N)Ω(N)Ω(N) query complexity). - We exhibit a problem, Quantum-Locked Estimation (QL-Estimation), for which pseudo-deterministic quantum algorithms admit an exponential speed-up over classical pseudo-deterministic algorithms (O(log⁡(N))O(\log(N))O(log(N)) vs. Θ(N)Θ(\sqrt{N})Θ(N​)), while the randomized query complexity is O(1)O(1)O(1). Complementing these separations, we show that for any total problem RRR, pseudo-deterministic quantum algorithms admit at most a quintic advantage over deterministic algorithms, i.e., D(R)=O~(psQ(R)5)D(R) = \tilde O(psQ(R)^5)D(R)=O~(psQ(R)5). On the algorithmic side, we identify a class of quantum search problems that can be made pseudo-deterministic with small overhead, including Grover search, element distinctness, triangle finding, kkk-sum, and graph collision.
This paper considers the query complexity of the functions in the family F_{N,M} of N-variable Boolean functions with onset size M, i.e., the number of inputs for which the function value is 1, where 1<= M <= 2^{N}/2 is assumed without loss of generality because of the symmetry of function values, 0 and 1. Our main results are as follows: (1) There is a super-linear gap between the average-case and worst-case quantum query complexities over F_{N,M} for a certain range of M. (2) There is no super-linear gap between the average-case and worst-case randomized query complexities over F_{N,M} for every M. (3) For every M bounded by a polynomial in N, any function in F_{N,M} has quantum query complexity Theta (sqrt{N}). (4) For every M=O(2^{cN}) with an arbitrary large constant c<1, any function in F_{N,M} has randomized query complexity Omega (N).