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

Davide Pastorello

Machine learningDec 16, 20220 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.