Track the frontier, from condensed matter to cosmology.
Search papers, labs, and topics across Lattice.
The authors initiate the systematic study of smoothed quantum query complexity to evaluate quantum algorithmic speedups beyond pessimistic worst-case bounds. They establish an exponential quantum-classical query separation for a total function, provide near-tight bounds for symmetric Boolean functions, and prove polynomial-to-superpolynomial quantum speedups for core string tasks like pattern matching and edit distance. These results demonstrate that realistic input perturbations can reveal dramatic quantum advantages where traditional worst-case complexity metrics suggest marginal or nonexistent gains.
Worst-case complexity heavily masks practical quantum utility: applying smoothed analysis unlocks exponential quantum-classical separations on total functions and superpolynomial speedups for foundational string problems.
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.