Quantum query methods find faster solutions on smoothed data sets
Quantum Query Complexity Beyond the Worst Case
Computational Complexity
Summary
Usually, computers do differently on tricky problems depending on the worst possible case. This paper studies how quantum computers perform when problems are a bit easier or 'smoothed' rather than at their hardest cases. The authors show that quantum computers can be much faster in these more realistic settings, sometimes exponentially so compared to classical computers. They also analyze how this applies to common problems like pattern matching and edit distance, important in areas such as text and DNA analysis. Their work hints that quantum advantage might be stronger when problems come from practical situations rather than worst-case examples.
What this means in practice
- •For quantum algorithm designers: Develop new quantum strategies for problems like pattern matching that run faster on realistic input distributions.
- •For string processing engineers: Improve performance in pattern matching and edit distance tasks by integrating quantum-inspired algorithms validated for smoothed cases.
Authors
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.