In the $k$-mismatch problem, given a pattern and a text of length $n$ and $m$ respectively, we have to find if the text has a sub-string with a Hamming distance of at most $k$ from the pattern. This has been studied in the classical setting since 1982 and recently in the quantum computational setting by Jin and Nogler and Kociumaka, Nogler, and Wellnitz. We provide a simple quantum algorithm that solves the problem in an approximate manner, given a parameter $ε\in (0, 1]$. It returns an occurrence as a match only if it is a $\left(1+ε\right)k$-mismatch. If it does not return any occurrence, then there is no $k$-mismatch. This algorithm has a time (size) complexity of $\tilde{O}\left( ε^{-1} \sqrt{\frac{mn}{k}} \right)$.
In the k-mismatch problem, given a pattern and a text of length n and m respectively, we have to find if the text has a sub-string with a Hamming distance of at most k from the pattern. This has been studied in the classical setting since 1982 and recently in the quantum computational setting by Jin and Nogler and Kociumaka, Nogler, and Wellnitz. We provide a simple quantum algorithm that solves the problem in an approximate manner, given a parameter ε∈(0,1]. It returns an occurrence as a match only if it is a (1+ε)k-mismatch. If it does not return any occurrence, then there is no k-mismatch. This algorithm has a time (size) complexity of O~(ε−1kmn).
Approximate Pattern Matching is among the most fundamental string-processing tasks. Given a text T of length n, a pattern P of length m, and a threshold k, the task is to identify the fragments of T that are at distance at most k to P. 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.
Longest Common Substring (LCS) is an important text processing problem, which has recently been investigated in the quantum query model. The decisional version of this problem, LCS with threshold d, asks whether two length-n input strings have a common substring of length d. The two extreme cases, d=1 and d=n, correspond respectively to Element Distinctness and Unstructured Search, two fundamental problems in quantum query complexity. However, the intermediate case 1≪d≪n was not fully understood. We show that the complexity of LCS with threshold d smoothly interpolates between the two extreme cases up to no(1) factors: LCS with threshold d has a quantum algorithm in n2/3+o(1)/d1/6 query complexity and time complexity, and requires at least Ω(n2/3/d1/6) quantum query complexity. Our result improves upon previous upper bounds O~(min{n/d1/2,n2/3}) (Le Gall and Seddighin ITCS 2022, Akmal and Jin SODA 2022), and answers an open question of Akmal and Jin. Our main technical contribution is a quantum speed-up of the powerful String Synchronizing Set technique introduced by Kempa and Kociumaka (STOC 2019). It consistently samples n/τ1−o(1) synchronizing positions in the string depending on their length-Θ(τ) contexts, and each synchronizing position can be reported by a quantum algorithm in O~(τ1/2+o(1)) time. As another application of our quantum string synchronizing set, we study the k-mismatch Matching problem, which asks if the pattern has an occurrence in the text with at most k Hamming mismatches. Using a structural result of Charalampopoulos, Kociumaka, and Wellnitz (FOCS 2020), we obtain a quantum algorithm for k-mismatch matching with k3/4n1/2+o(1) query complexity and O~(kn1/2) time complexity.
The d-dimensional pattern matching problem is to find an occurrence of a pattern of length m×⋯×m within a text of length n×⋯×n, with n≥m. This task models various problems in text and image processing, among other application areas. This work describes a quantum algorithm which solves the pattern matching problem for random patterns and texts in time O((n/m)d/22O(d3/2logm)). For large m this is super-polynomially faster than the best possible classical algorithm, which requires time Ω((n/m)d+nd/2). The algorithm is based on the use of a quantum subroutine for finding hidden shifts in d dimensions, which is a variant of algorithms proposed by Kuperberg.
A degenerate string is a sequence of sets of characters. A generalized degenerate (GD) string extends this notion to the sequence of sets of strings, where strings of the same set are of equal length. Finding an exact match for a pattern string inside a GD string can be done in O(mn+N) time (Ascone et al., WABI 2024), where m is the pattern length, n is the number of strings and N the total length of strings constituting the GD string. This is the best classical algorithm achieved so far, and no matching lower bound, neither unconditional nor conditional, has been shown. We make progress on this problem proposing a quantum algorithm that achieves running time O~(mnN), thus beating the current best classical solution. To the best of our knowledge, this is the first quantum algorithm proposed in the context of GD strings. We present our results starting from the framework of classical parallel computing, which we believe makes them intuitive to understand and possibly easy to generalise to other similar structures.
Abstract Algorithms that search for a pattern within a larger data-set appear ubiquitously in text and image processing. Here, we present an explicit, circuit-level implementation of a quantum pattern-matching algorithm that matches a search string (pattern) of length M inside a longer text of length N . Our algorithm has a time complexity of O~(N) O ̃ ( N ) , while the space complexity remains modest at O ( N + M ). We report the quantum gate counts relevant for both pre-fault-tolerant and fault-tolerant regimes.
Let S1,S2∈Σ∗ strings, we say that S1 {\em jumble match} S2 if they are permutations of each other. Given a text T of size N and a string S∈Σ∗, the problem of \emph{Jumbled Pattern Matching} (JPM) is to determine all substrings in T jumbled matching S. In classical computing, a widespread conjecture is that JPM requires Ω(N2−ε) preprocessing time and space for O(1) query time, or Ω(N1−δ) query time in the online version, with ε,δ>0. In this paper, we present a quantum algorithm for the online JPM in O(N) time.