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 $ε\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)$.

arXiv:2510.02399Oct 1, 20250 citations

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

Simone Faro, Arianna Pavone, Caterina Viola

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.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.

Theoretical Computer ScienceMay 25, 20260 citations

Quantum Pattern Recognition

Péter Wittek

Elsevier eBooksJan 1, 20143 citations

Quantum Algorithms and Applications

Melinda Andrews, Joseph Stephen Dulny, Andrew N. Glaudell +6 more

Sep 1, 20200 citations

Solving the Exact Pattern Matching Problem Constrained to Single Occurrence of Pattern P in String S Using Grover’s Quantum Search Algorithm

Brian Kenneth A. de Jesus, Jeffrey A. Aborot, Henry N. Adorna

Proceedings in information and communications technologyJan 1, 201310 citations

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)