.png){kind=icon}
.png){kind=icon}
Return
A quantum algorithm for string matching
.png){kind=icon}
OA
AI
DOI：10.1038/s41534-021-00369-3.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
8.3
Papers:
1.4K
Citations:
8.1K