Title | A quantum algorithm for string matching |
Publication Type | Journal Article |
Year of Publication | 2021 |
Authors | P. Niroula, and Y. Nam |
Journal | npj Quantum Inform. |
Volume | 7 |
Date Published | feb |
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. |
DOI | 10.1038/s41534-021-00369-3 |