Quantum Exact String Matching

The provided Jupyter Notebook tutorial contains a practical implementation of an initial Quantum Exact String Matching algorithm, proposed in our paper for the QUASAR'24 Workshop.

Overview

In our paper, we provide the implementation of a quantum ESM algorithm. Its essence lies in identifying an occurrence of a specified pattern $x$ of length $m$, within a text $y$ of length $n$ $\geq$ $m$, where both sequences are composed of characters taken from an alphabet $\Sigma$ of size $\sigma$. Our article presents an initial practical implementation of a quantum circuit tailored to address the ESM problem, particularly focusing on binary strings.

A classical naïve approach exhibits a worst-case time complexity of $\mathcal{O}(mn)$, contrasting with the capability of quantum computation to achieve a $\tilde{O}(\sqrt{n})$ complexity using Grover's search.

We use the Qiskit open-source toolkit developed by IBM. While current real-world hardware often struggles to produce valid results due to decoherence and quantum errors, this study presents experimental results from a circuit simulation on classical hardware, validating the proposed implementation's efficacy.

Reference

Please, reference this publication if you find this code useful:

@inproceedings{10.1145/3660318.3660327,
    author = {Marino, Francesco Pio and Faro, Simone and Scardace, Antonio},
    title = {Practical Implementation of a Quantum String Matching Algorithm},
    year = {2024},
    publisher = {Association for Computing Machinery},
    url = {https://doi.org/10.1145/3660318.3660327}
}

Authors

• Simone Faro
• Francesco Pio Marino
• Antonio Scardace