Application of an efficient approximate Gaussian boson sampler to certain graph problems.

We consider the use of a recently developed efficient and scalable approximate Gaussian boson sampler (GBS) to the three computationally hard graph problems, finding the densest $k$-node subgraph, finding the maximum weighted clique, and graph isomorphism. Our approach uses improper complex Gaussian random variables to represent single-mode squeezed states and an amplitude threshold exceedance scheme to approximate single-photon detectors and produce a binary sample output. We make use of Xanadu's Strawberry Fields Python library to compare the performance of our approximate sampler to that of an exact GBS, for small-scale problems, and standard classical solver, for larger ones. For densest $k$-subgraph problems with up to 500 nodes, we find that our GBS performs almost as well as an exact solver and significantly outperforms a classical random seed or greedy algorithm. For the maximum weighted clique problem, our GBS outperforms a classical random seed for a benchmark 700-node graph problem. Finally, our GBS was compared to a classical random walk algorithm for solving graph isomorphisms and found to outperform it for benchmark problems of up to 500 nodes.