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.