A Quantum-Inspired Algorithm for Sampler-Encoded Graph Isomorphism

The graph isomorphism problem has proven to be fertile ground for research throughout the history of computing, recently as potential means with which to realize quantum advantage, due to its NP-Intermediate complexity. The problem asks if a pair of discrete graphs can be made completely equivalent by only re-labeling their vertices, and its efficient solution would have applications in fields including image matching an cheminformatics. In this work, we approach the<br/>problem through the lens of near-term photonic quantum computing, yet through this construction arrive at a classical algorithm inspired by the properties of our quantum device of interest. We make<br/>use of an existing method to encode a graph’s adjacency matrix in a Gaussian boson sampler and resulting sufficient condition for the graph isomorphism problem from Bràdler et. al.. Given the inability to efficiently test for this condition, we introduce a similar graph invariant based on the<br/>statistical properties of these encoded-graph distributions. We define a necessary condition based on these properties, which can be tested for efficiently at low order with the algorithm introduced in this work. The algorithmic process, as well as its complexity, limitations, and relation to similar methods in the literature, are discussed.