Subgraph Isomorphism

The sub-graph isomorphism (SGI) problem is well known in combinatorics and finds many practical applications in graph databases, social network analysis, computer vision and biochemistry, to name a few.

From the computational standpoint, the SGI problem is NP-hard, meaning that practical algorithms must rely on some heuristic approach. The problem can be recast as a Quadratic Unconstrained Binary Optimization (QUBO) problem that can be solved on quantum computers using algorithms such as the Quantum Approximate Optimization Algorithm (QAOA) and the Variational Quantum Eigensolver (VQE). However, the QUBO formulation for SGI requires a polynomial number of qubits with respect to the number of vertices of the input graphs. We propose a new method that instead requires a logarithmic number of qubit with respect to the vertex count. This may open the possibility of employing the current quantum technology into solving the SGI problem for graphs on the scale of millions of vertices.