Quantum pattern matching fast on average

Abstract

The $d$-dimensional pattern matching problem is to find an occurrence of a pattern of length $m\times \cdots \times m$ within a text of length $n\times \cdots \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 $\tilde{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 $\tilde{\Omega }((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.

22 pages, 2 figures; v3: further minor changes, essentially published version

References in corpus (4)

• Quantum random access memory
• A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space
• A Survey of Quantum Property Testing
• Easy and hard functions for the Boolean hidden shift problem

Cited by in corpus (1)

• Quantum algorithms: an overview