arXiv:2609.35580
Quantum Query Complexity Beyond the Worst Case
Srinivasan Arunachalam, Yanlin Chen, Amin Shiraz Gilani
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.
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.