A quantum algorithm for string matching
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 lengt...
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | article |
| Lenguaje: | EN |
| Publicado: |
Nature Portfolio
2021
|
| Materias: | |
| Acceso en línea: | https://doaj.org/article/6828c2dd1cda4927b745961345585041 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| Sumario: | 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 $$\tilde{O}(\sqrt{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. |
|---|