G/SG Morph

The Graph/Subgraph Isomorphism Library for Quantum Annealers

G/SG Morph is an implementation of Calude, Dinneen, and Hua's "QUBO formulations for the graph isomorphism problem and related problems" (Quantum Unconstrained Binary Optimization) QUBO's for finding graph, subgraph, and induced subgraph isomorphisms on quantum annealers.

G/SG Morph also contains, with the permission of Richard Hua, a copy of his implementation of the Graph Isomorphism QUBO from his thesis "Adiabatic Quantum Computing with QUBO Formulations", Appendix E which is used for benchmarking (see "Benchmarking" in this README).

Installation

You can either

pip install gsgmorph

or clone this repository and run the following in the folder (and your choice of python environment!):

pip install .

High Level Overview

G/SG Morph consists of two modules, matrix_form and pyqubo_form, both of which contain three core functions, graph_isomorphism(), subgraph_isomorphism(), and translate_sample() that accomplish identical tasks but are implemented differently.

matrix_form relies on the usage of dictionaries to provide a matrix representing the QUBO, while pyqubo_form uses the PyQUBO library to express QUBOs. Note that pyqubo_form has been intentionally programmed to follow the math presented in Calude, Dineen, and Hua's paper as closely as possible (with minor adjustments made to satisfy Python syntax).

Both graph_isomorphism() and subgraph_isomorphism() take two NetworkX graphs (a "graph to embed" onto a "target graph") and will generate a QUBO suitable for running on a simulated annealer such as D-Wave Neal or actual hardware.

The above functions also return a dictionary that, in conjunction with a sample from an annelear, can be translated into a dictionary that maps nodes from the graph to embed to the target graph with the help of translate_sample().

subgraph_isomorphism() also has an additional induced argument that can be set to True indicating that you would like to generate a QUBO for the Induced Subgraph Isomorphism problem.

Examples

Please refer to the Jupyter Notebooks in the examples folder.

• gsgmorph_matrix_form_demo.ipynb shows the usage of the matrix_form module
• gsgmorph_pyqubo_form_demo.ipynb shows the usage of the pyqubo_form module

Benchmarking

Some benchmarking was conducted against Richard Hua's graph isomorphism QUBO generator and G/SG Morph's matrix_form implementation using Erdos-Renyi graphs in Google Colab. The results and techniques can be found in the Benchmarking folder.

Contributing

If you find a bug or have an idea to improve the library, please feel free to either make an Issue or a Pull Request with your suggested changes! If you are contributing code, please do note that this library attempts to follow the PEP-8 Style Guide for Python Code as well as using Google Style Python Docstrings

Credits

Although all the QUBO formulations used come from Calude, Dinneen, and Hua's "QUBO formulations for the graph isomorphism problem and related problems", this library would not have been possible without the following helpful sources:

• Wangfan Fu's answer to 'What is the square of summation?' on the Math Stackexchange site
• Dury and Matteo's code from their paper "A QUBO formulation for qubit allocation" https://arxiv.org/pdf/2009.00140.pdf served as inspiration for the usage of the Python product() function.
• PyQUBO Documentation: Integration with D-Wave Ocean for showing how to use D-Wave Neal with PyQUBO
• SilentGhost's answer to "Reverse / invert a dictionary mapping"
• ars' answer to "Get difference between two lists"
• Mccreesh, Prosser, Solnon, and Trimble's paper "When Subgraph Isomorphism is Really Hard, and Why This Matters for Graph Databases for providing a graph to test the Induced Subgraph Isomorphism problem on
• Dan D.'s answer to "what is diffrence between number and repeat in python timeit?"