Algorithms that search for a pattern within a larger data-set appear ubiquitously in text and image processing. Here, we present 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 . Our algorithm has a time complexity of Õ(√N) O ̃ ( N ) , while the space complexity remains modest at O ( N + M ). We report the quantum gate counts relevant for both pre-fault-tolerant and fault-tolerant regimes.
No takes yet. Share an insight, caveat, or question.
Niroula et al. (2021) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: