The $d$ -dimensional pattern matching problem is to find an occurrence of a pattern of length $m \times \dots \times m$ within a text of length $n \times \dots \times n$ , with $n \ge m$ . This task models various problems in text and image processing, among other application areas. This work describes a quantum algorithm which solves the pattern matching problem for random patterns and texts in time $\widetilde{O}((n/m)^{d/2} 2^{O(d^{3/2}\sqrt{\log m})})$ . For large $m$ this is super-polynomially faster than the best possible classical algorithm, which requires time $\widetildeΩ( (n/m)^d + n^{d/2} )$ . The algorithm is based on the use of a quantum subroutine for finding hidden shifts in $d$ dimensions, which is a variant of algorithms proposed by Kuperberg.The $d$-dimensional pattern matching problem is to find an occurrence of a pattern of length $m \times \dots \times m$ within a text of length $n \times \dots \times n$, with $n \ge m$. This task models various problems in text and image processing, among other application areas. This work describes a quantum algorithm which solves the pattern matching problem for random patterns and texts in time $\widetilde{O}((n/m)^{d/2} 2^{O(d^{3/2}\sqrt{\log m})})$. For large $m$ this is super-polynomially faster than the best possible classical algorithm, which requires time $\widetildeΩ( (n/m)^d + n^{d/2} )$. The algorithm is based on the use of a quantum subroutine for finding hidden shifts in $d$ dimensions, which is a variant of algorithms proposed by Kuperberg.

arXiv:1408.1816Aug 8, 20141 citation

Quantum Pattern Recognition

Carlo A. Trugenberger

arXiv:quant-ph/0210176Quantum Information ProcessingDec 1, 2002118 citations

Quantum Pattern Matching with Wildcards

Masoud Seddighin, Saeed Seddighin

Pattern matching is one of the fundamental problems in Computer Science. Both the classic version of the problem as well as the more sophisticated version where wildcards can also appear in the input can be solved in almost linear time $\tilde O(n)$ using the KMP algorithm and Fast Fourier Transform, respectively. In 2000, Ramesh and Vinay~\cite{ramesh2003string} give a quantum algorithm that solves classic pattern matching in sublinear time and asked whether the wildcard problem can also be solved in sublinear time? In this work, we give a quantum algorithm for pattern matching with wildcards that runs in time $\tilde O(\sqrt{n}\sqrt{k})$ when the number of wildcards is bounded by $k$ for $k \geq \sqrt{n}$ . This leads to an algorithm that runs in sublinear time as long as the number of wildcards is sublinear.Pattern matching is one of the fundamental problems in Computer Science. Both the classic version of the problem as well as the more sophisticated version where wildcards can also appear in the input can be solved in almost linear time $\tilde O(n)$ using the KMP algorithm and Fast Fourier Transform, respectively. In 2000, Ramesh and Vinay~\cite{ramesh2003string} give a quantum algorithm that solves classic pattern matching in sublinear time and asked whether the wildcard problem can also be solved in sublinear time? In this work, we give a quantum algorithm for pattern matching with wildcards that runs in time $\tilde O(\sqrt{n}\sqrt{k})$ when the number of wildcards is bounded by $k$ for $k \geq \sqrt{n}$. This leads to an algorithm that runs in sublinear time as long as the number of wildcards is sublinear.

arXiv:2507.13885Jul 18, 20250 citations

The

d

-dimensional pattern matching problem is to find an occurrence of a pattern of length

m \times \dots \times m

within a text of length

n \times \dots \times n

, with

n \ge m

. This task models various problems in text and image processing, among other application areas. This work describes a quantum algorithm which solves the pattern matching problem for random patterns and texts in time

\widetilde{O}((n/m)^{d/2} 2^{O(d^{3/2}\sqrt{\log m})})

. For large

m

this is super-polynomially faster than the best possible classical algorithm, which requires time

\widetildeΩ( (n/m)^d + n^{d/2} )

. The algorithm is based on the use of a quantum subroutine for finding hidden shifts in

d

dimensions, which is a variant of algorithms proposed by Kuperberg.

\tilde O(n)

using the KMP algorithm and Fast Fourier Transform, respectively. In 2000, Ramesh and Vinay~\cite{ramesh2003string} give a quantum algorithm that solves classic pattern matching in sublinear time and asked whether the wildcard problem can also be solved in sublinear time? In this work, we give a quantum algorithm for pattern matching with wildcards that runs in time

\tilde O(\sqrt{n}\sqrt{k})

when the number of wildcards is bounded by

k

for

k \geq \sqrt{n}

. This leads to an algorithm that runs in sublinear time as long as the number of wildcards is sublinear.