Journal
ALGORITHMICA
Volume 77, Issue 1, Pages 16-39Publisher
SPRINGER
DOI: 10.1007/s00453-015-0060-4
Keywords
Quantum algorithms; Quantum query complexity; Pattern matching; Average-case complexity
Funding
- EPSRC [EP/L021005/1]
- Engineering and Physical Sciences Research Council [EP/L021005/1] Funding Source: researchfish
Ask authors/readers for more resources
The d-dimensional pattern matching problem is to find an occurrence of a pattern of length m x ... x m within a text of length n x ... x n, with n >= 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 (O) over tilde((n/m)(d/2)2(O)(d(3/2) root log m)). For large m this is super-polynomially faster than the best possible classical algorithm, which requires time (Omega) over tilde (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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available