Quantum Pattern Matching Fast on Average

Research output: Contribution to journalArticle (Academic Journal)peer-review

48 Citations (Scopus)
338 Downloads (Pure)


The d-dimensional pattern matching problem is to find an occurrence of a pattern of length m×⋯×m within a text of length n×⋯×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˜((n/m)d/22O(d3/2logm√)). For large m this is super-polynomially faster than the best possible classical algorithm, which requires time Ω˜(nd/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.
Original languageEnglish
Pages (from-to)16-39
Number of pages24
Issue number1
Early online date27 Aug 2015
Publication statusPublished - Jan 2017

Structured keywords

  • QITG
  • Bristol Quantum Information Institute


  • quantum algorithms
  • Quantum query complexity
  • Pattern matching
  • Average-case complexity


Dive into the research topics of 'Quantum Pattern Matching Fast on Average'. Together they form a unique fingerprint.

Cite this