Prague Stringology Conference 2024
Arianna Pavone and Caterina Viola
A Quantum Circuit for the Cyclic String Matching Problem
| Abstract: |
| The cyclic string matching problem aims to detect an occurrence of any cyclical shift of a given sequence of characters within a (usually larger) one. This variant of the (classical) string matching problem arises in several real-world problems, such as DNA analysis and spoken natural language recognition, in which it is necessary to deal with sequences that lack a precise beginning or end and are equivalent up to cyclical shifting. We present a quantum algorithm, in the form of a quantum circuit, for solving the cyclic string matching problem. This algorithm requires quadratically fewer time steps than the most efficient counterpart algorithm running on a classical machine. Additionally, we provide a practical implementation of the presented algorithm using the Qiskit toolkit. |
| Download paper: |  |
 |
 |
| PostScript | BibTeX reference |
| Download presentation: |  |