Skip to content

antonioscardace/Practical-Quantum-ESM

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

9 Commits
 
 
 
 
 
 

Repository files navigation

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.

License Open Issues Open In Colab

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