Quantum pattern matching fast on average
arXiv:1408.1816
Abstract
The -dimensional pattern matching problem is to find an occurrence of a pattern of length within a text of length , with . 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 . For large this is super-polynomially faster than the best possible classical algorithm, which requires time . The algorithm is based on the use of a quantum subroutine for finding hidden shifts in dimensions, which is a variant of algorithms proposed by Kuperberg.
arXiv comment22 pages, 2 figures; v3: further minor changes, essentially published version
References in corpus (10)
- Quantum Mechanics helps in searching for a needle in a haystack
- Strengths and Weaknesses of Quantum Computing
- Quantum random access memory
- The quantum query complexity of the hidden subgroup problem is polynomial
- Quantum Search on Bounded-Error Inputs
- A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space
- A Survey of Quantum Property Testing
- Quantum algorithms to solve the hidden shift problem for quadratics and for functions of large Gowers norm
- Easy and hard functions for the Boolean hidden shift problem
- Quantum algorithms for highly non-linear Boolean functions