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/2sqrt{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.