Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Theoretical Computer Science

A general quantum circuit for string matching: Unleashing quantum path parallelism

Simone Faro, Arianna Pavone, Caterina Viola

Published May 25, 2026• 0 citations
Publisher

Abstract

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.

DOI
10.1016/j.tcs.2026.116059

Related papers

Quantum Bit-Parallel Swap Matching

Simone Faro, Francesco Pio Marino, Arianna Pavone +2 more

Pattern matching with swaps is a well-known non-standard variant of the string matching problem in which adjacent characters of the pattern may be swapped, under the constraint that each character participates in at most one swap. This problem has received considerable attention in the stringology literature due to its applications in areas such as computational biology, error-tolerant text processing, and pattern discovery. In this paper we investigate the problem in the quantum computing model. Building upon the recently introduced framework of quantum bit-parallelism, which provides a systematic way to translate classical bit-parallel string matching algorithms into quantum circuits, we develop the first quantum algorithm for swap matching based on this paradigm. Our approach adapts the classical cross-sampling technique for swap matching into a reversible quantum procedure that simulates the evolution of two interacting automata configurations using quantum registers and bitwise quantum operations. While the resulting quantum circuit preserves the near-linear behavior of its classical counterpart in terms of circuit depth, its integration with Grover’s search enables a quadratic speedup. By embedding the verification procedure within a quantum search framework and carefully controlling the size of the search space, we obtain a quantum algorithm that solves the swap matching problem in \(\tilde{O}(\sqrt {n})\) time. This result extends the applicability of quantum bit-parallelism to non-standard string matching problems and provides further evidence that a broad class of classical text searching techniques can be systematically lifted to the quantum setting while preserving their structural efficiency.

ACM International Symposium on High-Performance Parallel and Distributed Computing (HPDC)•Jul 11, 2026•0 citations

Classical Equivalent Quantum Based Pattern Matching Algorithms

Kapil Kumar Soni, Akhtar Rasool

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.

International Conference on Computing, Communication and Networking Technologies (ICCCNT)•Jul 1, 2019•0 citations

Practical Implementation of a Quantum String Matching Algorithm

Francesco Pio Marino, Simone Faro, Antonio Scardace

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.

•Jun 3, 2024•5 citations

A quantum algorithm for string matching

Pradeep Niroula, Yunseong Nam

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 $$\tilde{O}(\sqrt{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.

npj Quantum Information•Feb 16, 2021•42 citations

Quantum Pattern Matching in Generalised Degenerate Strings

Massimo Equi, Md Rabiul Islam Khan, Veli Mäkinen

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 $\tilde{O}(\sqrt{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.

quant-pharXiv:2603.16297•Mar 18, 2026•0 citations

Quantum Circuits for Fixed Substring Matching Problems

Domenico Aldo Cantone, Simone Faro, Arianna Pavone +1 more

Quantum computation represents a computational paradigm whose distinctive attributes confer the ability to devise algorithms with asymptotic performance levels significantly superior to those achievable via classical computation. Recent strides have been taken to apply this computational framework in tackling and resolving various issues related to text processing. The resultant solutions demonstrate marked advantages over their classical counterparts. This study employs quantum computation to efficaciously surmount text processing challenges, particularly those involving string comparison. The focus is on the alignment of fixed-length substrings within two input strings. Specifically, given two input strings, $x$ and $y$, both of length $n$, and a value $d \leq n$, we want to verify the following conditions: the existence of a common prefix of length $d$, the presence of a common substring of length $d$ beginning at position $j$ (with $0 \leq j < n$) and, the presence of any common substring of length $d$ beginning in both strings at the same position. Such problems find applications as sub-procedures in a variety of problems concerning text processing and sequence analysis. Notably, our approach furnishes polylogarithmic solutions, a stark contrast to the linear complexity inherent in the best classical alternatives.

arXiv:2308.11758•Aug 22, 2023•0 citations
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.
Pattern matching with swaps is a well-known non-standard variant of the string matching problem in which adjacent characters of the pattern may be swapped, under the constraint that each character participates in at most one swap. This problem has received considerable attention in the stringology literature due to its applications in areas such as computational biology, error-tolerant text processing, and pattern discovery. In this paper we investigate the problem in the quantum computing model. Building upon the recently introduced framework of quantum bit-parallelism, which provides a systematic way to translate classical bit-parallel string matching algorithms into quantum circuits, we develop the first quantum algorithm for swap matching based on this paradigm. Our approach adapts the classical cross-sampling technique for swap matching into a reversible quantum procedure that simulates the evolution of two interacting automata configurations using quantum registers and bitwise quantum operations. While the resulting quantum circuit preserves the near-linear behavior of its classical counterpart in terms of circuit depth, its integration with Grover’s search enables a quadratic speedup. By embedding the verification procedure within a quantum search framework and carefully controlling the size of the search space, we obtain a quantum algorithm that solves the swap matching problem in O~(n)\tilde{O}(\sqrt {n})O~(n​) time. This result extends the applicability of quantum bit-parallelism to non-standard string matching problems and provides further evidence that a broad class of classical text searching techniques can be systematically lifted to the quantum setting while preserving their structural efficiency.
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.
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)\tilde{O}(\sqrt{N})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.
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)O(mn+N)O(mn+N) time (Ascone et al., WABI 2024), where mmm is the pattern length, nnn is the number of strings and NNN 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)\tilde{O}(\sqrt{mnN})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.
Quantum computation represents a computational paradigm whose distinctive attributes confer the ability to devise algorithms with asymptotic performance levels significantly superior to those achievable via classical computation. Recent strides have been taken to apply this computational framework in tackling and resolving various issues related to text processing. The resultant solutions demonstrate marked advantages over their classical counterparts. This study employs quantum computation to efficaciously surmount text processing challenges, particularly those involving string comparison. The focus is on the alignment of fixed-length substrings within two input strings. Specifically, given two input strings, xxx and yyy, both of length nnn, and a value d≤nd \leq nd≤n, we want to verify the following conditions: the existence of a common prefix of length ddd, the presence of a common substring of length ddd beginning at position jjj (with 0≤j<n0 \leq j < n0≤j<n) and, the presence of any common substring of length ddd beginning in both strings at the same position. Such problems find applications as sub-procedures in a variety of problems concerning text processing and sequence analysis. Notably, our approach furnishes polylogarithmic solutions, a stark contrast to the linear complexity inherent in the best classical alternatives.