Sub-Graph Isomorphism

A computer system, comprising:

• one or more processors;
• and
• a memory comprising a plurality of program instructions which, when executed by the one or more processors, cause the one or more processors to:
• determine, by a computer device, a first adjacency matrix of a first graph and a second adjacency matrix of a second graph, wherein the first graph comprises a greater number of vertices than the second graph;
• determine, by the computer device, an objective optimization problem subject to one or more constraints, wherein the objective optimization problem is configured to determine a partial permutation matrix;
• determine, by the computer device, a QUBO matrix suitable for implementing the objective optimization problem;
• compute, by a quantum computer, a QUBO formulation including the QUBO matrix to generate the partial permutation matrix;
• and
• applying, by the computer device, the partial permutation matrix to the first adjacency matrix to generate a partially permuted first adjacency matrix, wherein the partially permuted first adjacency matrix corresponds to a sub-graph of the first graph that is isomorphic with the second graph.

A computer device, comprising:

• one or more processors;
• and
• a memory comprising a plurality of program instructions which, when executed by the one or more processors, cause the one or more processors to:
• determine a first adjacency matrix of a first graph and a second adjacency matrix of a second graph, wherein the first graph comprises a greater number of vertices than the second graph;
• determine an objective optimization problem subject to one or more constraints, wherein the objective optimization problem is configured to determine a partial permutation matrix;
• determine a QUBO matrix suitable for implementing the objective optimization problem;
• transmit the QUBO matrix to a quantum computer to generate the partial permutation matrix;
• receive from the quantum computer the partial permutation matrix;
• applying, by the computer device, the partial permutation matrix to the first adjacency matrix to generate a partially permuted first adjacency matrix, wherein the partially permuted first adjacency matrix corresponds to a sub-graph of the first graph that is isomorphic with the second graph.