Near-Optimal-Time Quantum Algorithms for Approximate Pattern Matching

Approximate Pattern Matching is among the most fundamental string-processing tasks. Given a text 𝑇 of length 𝑛, a pattern 𝑃 of length 𝑚, and a threshold 𝑘, the task is to identify the fragments of 𝑇 that are at distance at most 𝑘 to 𝑃. We consider the two most common distances: Hamming distance (the number of mismatches or character substitutions) in Pattern Matching with Mismatches and edit distance (the minimum number of character insertions, deletions, and substitutions) in Pattern Matching with Edits. We revisit the complexity of these two problems in the quantum setting.

Our recent work [STOC'24] shows that Ô( 𝑛/𝑚 • √ 𝑚𝑘) = Ô( √ 𝑛𝑘)1 quantum queries are sufficient to solve (the decision version of) the Pattern Matching with Edits problem. However, the quantum time complexity of the underlying solution (that is, the computational overhead to recover the solution from the quantum queries) does not provide any improvement over classical computation. On the other hand, the state-of-the-art quantum algorithm for Pattern Matching with Mismatches [Jin and Nogler; SODA'23] achieves query complexity Ô( √ 𝑛𝑘 3/2 ) and time complexity Õ( √ 𝑛𝑘 2 ), falling short of a known unconditional lower bound of Ω( √ 𝑛𝑘) quantum queries. In this work, we present quantum algorithms with a time complexity of Õ( √ 𝑛𝑘 + 𝑛/𝑚 • 𝑘 2 ) for Pattern Matching with Mismatches and Ô( √ 𝑛𝑘 + 𝑛/𝑚 • 𝑘 3.5 ) for Pattern Matching with Edits; both algorithms use Ô( √ 𝑛𝑘) quantum queries. These running times are near-optimal for 𝑘 ≪ 𝑚 1/3 and 𝑘 ≪ 𝑚 1/6 , respectively, and they offer advantage over classical algorithms for 𝑘 ≪ (𝑚𝑛) 1/4 and 𝑘 ≪ (𝑚𝑛) 1/7 , respectively. Our solutions can also report the starting positions of all approximate occurrences of 𝑃 in 𝑇 (represented as collections of arithmetic progressions); in this case, both the unconditional lower bound and the complexities of our algorithms increase by a Θ( 𝑛/𝑚) factor.

As a major technical contribution, we give a faster algorithm to solve a system of 𝑏 substring equations of the

The goal is to construct a generic solution string whose characters are equal only when necessary. While this is known to be possible in 𝒪(𝑛 + 𝑏) time [Gawrychowski, Kociumaka, Radoszewski, Rytter, Wale ń; TCS'16], we show that Õ(𝑏 2 ) classical time is sufficient to obtain an Õ(𝑏)-size representation of 𝑆 that supports random access and other standard queries (of the so-called PILLAR model) in 𝒪(log 𝑛) time. We apply this tool to efficiently construct an Õ(𝑘)-size representation of strings 𝑃 # and 𝑇 # obtained from 𝑃 and 𝑇 by carefully masking out some characters so that the output to the studied approximate pattern matching problems does not change.

1 Throughout this paper, the Õ(•) and Ô(•) notations hide poly-logarithmic factors (log 𝑁) 𝒪(1) and sub-polynomial factors 𝑁 𝑜(1) , respectively, with respect to the total input size 𝑁 of the considered problems.