Quantum Pattern Matching Fast on Average.

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{\Omega }( n^{d/2} + (n/m)^d)$$ . 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. [ABSTRACT FROM AUTHOR]