A quantum algorithm for string matching

Circuit diagram for circular bitwise rotation operator

Algorithms that search for a pattern within a larger data-set appear ubiquitously in text and image processing.

Pattern matching algorithms are used ubiquitously used in image processing, the study of DNA sequences, and data compression and statistics, to name a few. Thus, accelerating pattern matching using a quantum computer would be a boon to all these areas.

Researchers at Joint Quantum Institute, NIST/University of Maryland and IonQ have developed an explicit, circuit-level implementation of a quantum pattern-matching algorithm that matches a search string (pattern) of length M inside a longer text of length N.

Their algorithm has a time complexity of 𝑂̃(√N), while the space complexity remains modest at O(N + M).

They also reported the quantum gate counts relevant for both pre-fault-tolerant and fault-tolerant regimes.

The paper has been published in npj quantum information.