{"id":"arxiv/2609.35580","url":"https://arxiv.org/abs/2609.35580","tags":["quant-ph","cs.CC"],"score":0,"title":"Quantum Query Complexity Beyond the Worst Case","domain":"quant-ph","source":"arxiv","authors":["Srinivasan Arunachalam","Yanlin Chen","Amin Shiraz Gilani"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-09-28","reactions":{}}