RSS icon
Twitter icon
Facebook icon
Vimeo icon
YouTube icon

A quantum algorithm for string matching

TitleA quantum algorithm for string matching
Publication TypeJournal Article
Year of Publication2021
AuthorsP. Niroula, and Y. Nam
Journalnpj Quantum Inform.
Volume7
Date Publishedfeb
Abstract

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 (O) over tilde root 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.

DOI10.1038/s41534-021-00369-3