Quantum Query Complexity Beyond the Worst Case
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 ε-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.
Related
- Near-Optimal Separations of Certificate Complexity from Randomized and Quantum Query Complexity
- Quantum Query Complexity of Tournament Solutions
- Optimal query complexity for fractional quantum evolution
- Worst-Case Quantum Algorithm for Optimal Polynomial Intersection Beyond Decoded Quantum Interferometry
- Quantum Query Complexity of Maximum Degree and its Generalizations
BibTeX
@misc{arunachalam2026quantum,
title = {{Quantum Query Complexity Beyond the Worst Case}},
author = {Srinivasan Arunachalam and Yanlin Chen and Amin Shiraz Gilani},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.35580},
eprint = {2609.35580},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.35580},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Quantum Query Complexity Beyond the Worst Case
AU - Srinivasan Arunachalam
AU - Yanlin Chen
AU - Amin Shiraz Gilani
PY - 2026
DA - 2026/09/28
PB - arXiv
DO - 10.48550/arxiv.2609.35580
UR - https://arxiv.org/abs/2609.35580
AB - 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 ε-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.
ER -