Let $S_1, S_2 \in Σ^*$ strings, we say that $S_1$ {\em jumble match} $S_2$ if they are permutations of each other. Given a text $T$ of size $N$ and a string $S \in Σ^*$, 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 $Ω(N^{2-ε})$ preprocessing time and space for $O(1)$ query time, or $Ω(N^{1-δ})$ query time in the online version, with $ε, δ>0$. In this paper, we present a quantum algorithm for the online JPM in $O(\sqrt{N})$ time.
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.
We propose a quantum algorithm for closest pattern matching which allows us to search for as many distinct patterns as we wish in a given string (database), requiring a query function per symbol of the pattern alphabet. This represents a significant practical advantage when compared to Grover's search algorithm as well as to other quantum pattern matching methods, which rely on building specific queries for particular patterns. Our method makes arbitrary searches on long static databases much more realistic and implementable. Our algorithm, inspired by Grover's, returns the position of the closest substring to a given pattern of size M with non-negligible probability in O(N) queries, where N is the size of the string. Furthermore, we give the full recipe to implement our algorithm (together with its total circuit complexity), thus offering an oracle-based quantum algorithm ready to be implemented.
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).
The pattern matching problem is imperative in diversified field of computer science, and it finds occurrences of the pattern string(s) of any arbitrary length “M” in the large text string of length “N”. Since past decades the solutions to a problem have been suggesting through efficient algorithms. Classical benchmark algorithms such as Knuth Morris Pratt and Boyer Moore locates such solution in O(N) time, equivalent quantum algorithms can utilize quantum computations which are inherently parallel and obtains computational speedup by providing the solution in O(√N) time. The quantum pattern matching algorithm uses Grover's search logic that finds an element existence in the large unstructured text data of “N” items in O(√N) time, instead classically it takes O(N) time. The article comprises of introductory pattern matching tactics, quantum basics, Grover's search method, quantum based pattern matching algorithms, their illustration followed by complexity analysis, and finally concludes with the possible algorithmic variations and relevant applications.
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.
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.
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.