This work presents a comprehensive analysis of quantum algorithms for the Generalized Degenerate String Matching (SMGD) problem, which involves finding occurrences of a pattern P of length m in a generalized degenerate text \(\mathcal{T}\) consisting of n sets containing s strings of total length N. The proposed work first explores an algorithm combining existing approaches such as the Aho-Corasick automaton and quantum techniques like Grover search to achieve a query complexity of \(O(m + N + m\sqrt{sHn})\), where H is the maximum number of strings in any set of \(\mathcal{T}\). To demonstrate a definitive quantum advantage over the state-of-the-art classical algorithm which has a running time of O(mn + N) (Ascone et al., WABI 2024), this work extends to a strategy based on alignment-shift that fully exploits the quantum model of computation by simulating parallel shifts. This algorithm achieves a running time of \(\tilde{O}(\sqrt{mnN})\), which represents a sub-linear query complexity and establishes a potential theoretical quantum speed-up for generalized degenerate strings.
This work presents a comprehensive analysis of quantum algorithms for the Generalized Degenerate String Matching (SMGD) problem, which involves finding occurrences of a pattern P of length m in a generalized degenerate text (\mathcal{T}) consisting of n sets containing s strings of total length N. The proposed work first explores an algorithm combining existing approaches such as the Aho-Corasick automaton and quantum techniques like Grover search to achieve a query complexity of (O(m + N + m\sqrt{sHn})), where H is the maximum number of strings in any set of (\mathcal{T}). To demonstrate a definitive quantum advantage over the state-of-the-art classical algorithm which has a running time of O(mn + N) (Ascone et al., WABI 2024), this work extends to a strategy based on alignment-shift that fully exploits the quantum model of computation by simulating parallel shifts. This algorithm achieves a running time of (\tilde{O}(\sqrt{mnN})), which represents a sub-linear query complexity and establishes a potential theoretical quantum speed-up for generalized degenerate strings.
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.
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.
Text searching is a fundamental problem in computer science, and it finds applications in several scientific fields. The string matching problem is the common framework for the class of text searching problems where the objective is to find all, possibly approximate, occurrences of a given pattern of length m within a larger text of length n . This paper introduces the quantum path parallelism approach, that is, a general strategy based on quantum computation, which is easily adapted to a variety of nonstandard text-searching problems. Our method translates a text-searching problem into an automata-based string-recognition problem, associating each possible approximation of the pattern with a different path accepted by the automaton. Under favorable conditions, our algorithm solves an approximate search problem in O ( n m log ( n ) ) -time, yielding a quadratic speed-up over classical solutions. In other cases, such a speed-up is achieved only for short patterns, i.e. whenever m = O ( log ( n ) ) . We show the flexibility of our method, giving explicit adaptations to some specific approximate string matching problems.
String matching stands as a cornerstone problem in computer science, finding extensive application in many fields, such as data mining, text retrieval, and bioinformatics, just to cite a few. Its essence lies in identifying all occurrences of a specified pattern, typically denoted by length m, within a text of length n. Despite its seemingly straightforward formulation, the problem has sparked a plethora of solutions, stemming from diverse computational paradigms and approaches. Classical solutions exhibit a worst-case time complexity of Θ(n), contrasting with the capability of quantum computation to achieve a [EQUATION] complexity using Grover search, thereby realizing a quadratic speed-up compared to classical methods. This article presents a first practical implementation of a quantum circuit tailored to address string matching, particularly focusing on binary strings. The exposition delves into the technical intricacies of the implementation, which leverages the Qiskit open-source toolkit developed by IBM. By elucidating various algorithmic nuances overlooked in prior theoretical formulations, our solution serves as a conduit between the realms of text processing and quantum computing, fostering cross-disciplinary dialogue and innovation. While current real-world hardware lacks the capability to execute the proposed circuit, particularly when dealing with lengthy texts, this study presents experimental results from a simulation of the circuit on classical hardware, serving to validate the efficacy of the proposed implementation.
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.