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. We modify this algorithm to work under a quantum model of computation, achieving running time $\tilde{O}(\sqrt{mnN})$.
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. We modify this algorithm to work under a quantum model of computation, achieving running time O~(mnN).
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 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+msHn), where H is the maximum number of strings in any set of 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 O~(mnN), which represents a sub-linear query complexity and establishes a potential theoretical quantum speed-up for generalized degenerate strings.
In the search with wildcards problem [Ambainis, Montanaro, Quantum Inf.~Comput.'14], one's goal is to learn an unknown bit-string x∈{−1,1}n. An algorithm may, at unit cost, test equality of any subset of the hidden string with a string of its choice. Ambainis and Montanaro showed a quantum algorithm of cost O(nlogn) and a near-matching lower bound of Ω(n). Belovs [Comput.~Comp.'15] subsequently showed a tight O(n) upper bound.
We consider a natural generalization of this problem, parametrized by a subset Q⊆2[n], where an algorithm may test whether xS=b for an arbitrary S∈Q and b∈{−1,1}S of its choice, at unit cost. We show near-tight bounds when Q is any of the following collections: bounded-size sets, contiguous blocks, prefixes, and only the full set.
All of these results are derived using a framework that we develop. Using symmetries of the task at hand we show that the quantum query complexity of learning x is characterized, up to a constant factor, by an optimization program, which is succinctly described as follows: `maximize over all odd functions f:{−1,1}n→R the ratio of the maximum value of f to the maximum (over T∈Q) standard deviation of f on a subcube whose free variables are exactly T.'
To the best of our knowledge, ours is the first work to use the primal version of the negative-weight adversary bound (which is a maximization program typically used to show lower bounds) to show new quantum query upper bounds without explicitly resorting to SDP duality.
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.
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.
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.
Many problems that can be solved in quadratic time have bit-parallel speed-ups with factor w, where w is the computer word size. A classic example is computing the edit distance of two strings of length n, which can be solved in O(n2/w) time. In a reasonable classical model of computation, one can assume w=Θ(logn), and obtaining significantly better speed-ups is unlikely in the light of conditional lower bounds obtained for such problems. In this paper, we study the connection of bit-parallelism to quantum computation, aiming to see if a bit-parallel algorithm could be converted to a quantum algorithm with better than logarithmic speed-up. We focus on string matching in labeled graphs, the problem of finding an exact occurrence of a string as the label of a path in a graph. This problem admits a quadratic conditional lower bound under a very restricted class of graphs (Equi et al. ICALP 2019), stating that no algorithm in the classical model of computation can solve the problem in time O(∣P∣∣E∣1−ε) or O(∣P∣1−ε∣E∣). We show that a simple bit-parallel algorithm on such restricted family of graphs (level DAGs) can indeed be converted into a realistic quantum algorithm that attains subquadratic time complexity O(∣E∣∣P∣).