# Quantum pattern matching fast on average

arXiv: https://arxiv.org/abs/1408.1816 · HTML: https://mlsanity.com/paper/1408.1816/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Aug 2014.

## Built on by (most cited first, 3 of 3)

- [Experimental quantum pattern recognition in IBMQ and diamond NVs](https://mlsanity.com/paper/2205.00561/) (2022)
- [Provable advantages of kernel-based quantum learners and quantum preprocessing based on Grover's algorithm](https://mlsanity.com/paper/2309.14406/) (2023)
- [Quantum Algorithm for the Shortest Superstring Problem](https://mlsanity.com/paper/2112.13319/) (2021)

## Abstract (arXiv)

The d-dimensional pattern matching problem is to find an occurrence of a pattern of length m × dots × m within a text of length n × dots × 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 widetildeO((n/m)d/2 2^O(d3/2√log m)). For large m this is super-polynomially faster than the best possible classical algorithm, which requires time widetildeOmega( (n/m)d + nd/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.