Quantum Exact String Matching

The provided notebook tutorial contains a practical implementation of an initial Quantum Exact String Matching algorithm, proposed in our paper for the QUASAR 24 Workshop, part of the ACM HPDC conference.

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.

Citing

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