- Tutorials
- About This Project
- How to Give Feedback
- Contribution Guidelines
- Acknowledgements
- References
- License
The present work is a Qiskit-based implementation of a method for solving the sub-graph isomorphism problem on a gate-based quantum computer. The method relies on a new representation of the adjacency matrices of the underlying graphs and it requires a number of qubits that scales logarithmically with the number of vertices of the graphs. Given two undirected graphs A and B (the former with equal or larger number of vertices than the latter), the sub-graph isomorphism problem is the problem of finding occurrences of graph B into graph A. If the two graphs have the same number of vertices, then the problem is known as graph isomorphism, which is therefore a special case. More details can be found in the following paper [1]. The sub-graph isomorphism problem has numerous applications when data can be represented as networks, and notably in graph databases, biochemistry, computer vision, social network analysis, knowledge graph query, among many others.
The main demo, which also manages the requirements, is located here. A brief overview of the problem, proposed solution and some results can be found in the poster presented at the European Quantum Technology Conference, Nov 29th - Dec 2nd, 2021, Dublin, Ireland.
We encourage your feedback! You can share your thoughts with us by:
- Opening an issue in the repository
- Starting a conversation on GitHub Discussions
For information on how to contribute to this project, please take a look at CONTRIBUTING.MD.
This module is based on the theory and experiment described in [1].
The code on which this module is based was written by Nicola Mariella.
We are highly thankful to Dr. Andrea Simonetto, Dr. Claudio Gambella (both were at IBM Research Europe - Dublin), Dr. Martin Mevissen (IBM Research Europe - Dublin) and Prof. Jiri Vala (Maynooth University - Dep. of Theoretical Physics) for their precious suggestions.
[1] Nicola Mariella, Andrea Simonetto, A Quantum Algorithm for the Sub-Graph Isomorphism Problem, https://arxiv.org/abs/2111.09732