arXiv:2410.06808 · Society for Industrial and Applied Mathematics eBooks

Near-Optimal-Time Quantum Algorithms for Approximate Pattern Matching

Tomasz Kociumaka, Jakob Nogler, Philip Wellnitz

Published Jan 1, 2025• 1 citation

Abstract

Approximate Pattern Matching is among the most fundamental string-processing tasks. Given a text T of length n, a pattern P of length m, and a threshold k, the task is to identify the fragments of T that are at distance at most k to P. We consider the two most common distances: Hamming distance (the number of mismatches or character substitutions) in Pattern Matching with Mismatches and edit distance (the minimum number of character insertions, deletions, and substitutions) in Pattern Matching with Edits. We revisit the complexity of these two problems in the quantum setting.

DOI: 10.1137/1.9781611978322.15

Related papers

Simple Quantum Algorithm for Approximate $k$ -Mismatch Problem

Ruhan Habib, Shahriar, Shadman

arXiv:2510.02399Oct 1, 20250 citations

Near-Optimal Quantum Algorithms for Bounded Edit Distance and Lempel-Ziv Factorization

Daniel Gibney, Ce Jin, Tomasz Kociumaka +1 more

Measuring sequence similarity and compressing texts are among the most fundamental tasks in string algorithms. In this work, we develop near-optimal quantum algorithms for the central problems in these two areas: computing the edit distance of two strings [Levenshtein, 1965] and building the Lempel-Ziv factorization of a string [Ziv & Lempel, 1977], respectively.

Society for Industrial and Applied Mathematics eBooksJan 1, 20247 citations

A quantum algorithm for string matching

Pradeep Niroula, Yunseong Nam

npj Quantum InformationFeb 16, 202142 citations

Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce

Mahdi Boroujeni, Soheil Ehsani, Mohammad Ghodsi +2 more

arXiv:1804.04178Society for Industrial and Applied Mathematics eBooksJan 1, 201869 citations

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

Simone Faro, Arianna Pavone, Caterina Viola

Theoretical Computer ScienceMay 25, 20260 citations

Quantum Pattern Matching in Generalised Degenerate Strings

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

quant-pharXiv:2603.16297Mar 18, 20260 citations

arXiv:2410.06808 · Society for Industrial and Applied Mathematics eBooks

Near-Optimal-Time Quantum Algorithms for Approximate Pattern Matching

Tomasz Kociumaka, Jakob Nogler, Philip Wellnitz

Published Jan 1, 2025• 1 citation

arXiv HTML PDF

Abstract

DOI: 10.1137/1.9781611978322.15

Related papers

Simple Quantum Algorithm for Approximate $k$ -Mismatch Problem

Ruhan Habib, Shahriar, Shadman

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

Near-Optimal Quantum Algorithms for Bounded Edit Distance and Lempel-Ziv Factorization

Daniel Gibney, Ce Jin, Tomasz Kociumaka +1 more

Society for Industrial and Applied Mathematics eBooksJan 1, 20247 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.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 InformationFeb 16, 202142 citations

Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce

Mahdi Boroujeni, Soheil Ehsani, Mohammad Ghodsi +2 more

The edit distance between two strings is defined as the smallest number of insertions, deletions, and substitutions that need to be made to transform one of the strings to another one. Approximating edit distance in subquadratic time is “one of the biggest unsolved problems in the field of combinatorial pattern matching” [21]. Our main result is a quantum constant approximation algorithm for computing the edit distance in truly subquadratic time. More precisely, we give an O(n1.858) quantum algorithm that approximates the edit distance within a factor of 7. We further extend this result to an O(n1.781) quantum algorithm that approximates the edit distance within a larger constant factor. Our solutions are based on a framework for approximating edit distance in parallel settings. This framework requires as black box an algorithm that computes the distances of several smaller strings all at once. For a quantum algorithm, we reduce the black box to metric estimation and provide efficient algorithms for approximating it. We further show that this framework enables us to approximate edit distance in distributed settings. To this end, we provide a MapReduce algorithm to approximate edit distance within a factor of 3, with sublinearly many machines and sublinear memory. Also, our algorithm runs in a logarithmic number of rounds.The edit distance between two strings is defined as the smallest number of insertions, deletions, and substitutions that need to be made to transform one of the strings to another one. Approximating edit distance in subquadratic time is “one of the biggest unsolved problems in the field of combinatorial pattern matching” [21]. Our main result is a quantum constant approximation algorithm for computing the edit distance in truly subquadratic time. More precisely, we give an O(n1.858) quantum algorithm that approximates the edit distance within a factor of 7. We further extend this result to an O(n1.781) quantum algorithm that approximates the edit distance within a larger constant factor. Our solutions are based on a framework for approximating edit distance in parallel settings. This framework requires as black box an algorithm that computes the distances of several smaller strings all at once. For a quantum algorithm, we reduce the black box to metric estimation and provide efficient algorithms for approximating it. We further show that this framework enables us to approximate edit distance in distributed settings. To this end, we provide a MapReduce algorithm to approximate edit distance within a factor of 3, with sublinearly many machines and sublinear memory. Also, our algorithm runs in a logarithmic number of rounds.

arXiv:1804.04178Society for Industrial and Applied Mathematics eBooksJan 1, 201869 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 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.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.16297Mar 18, 20260 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)

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

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.