Using Gaussian Boson Sampling for dense subgraph finding with error

Naomi R. Solomons

Naomi R. Solomons, O. Thomas, Dara P. S. McCutcheon

Recent claims of achieving exponential quantum advantage have attracted attention to Gaussian boson sampling (GBS), a potential application of which is dense subgraph finding. We investigate the effects of sources of error including loss and spectral impurity on GBS applied to dense subgraph finding algorithms. We find that the effectiveness of these algorithms is remarkably robust to errors, to such an extent that there exist efficient classical algorithms that can simulate the underlying GBS. These results imply that the speedup of GBS-based algorithms for the dense subgraph problem over classical approaches is at most polynomial, though this could be achieved on a quantum device with dramatically less stringent requirements on loss and photon purity than general GBS.

Naomi R. Solomons

Juan Miguel Arrazola, Thomas R. Bromley

Boson sampling devices are a prime candidate for exhibiting quantum supremacy, yet their application for solving problems of practical interest is less well understood. Here we show that Gaussian boson sampling (GBS) can be used for dense subgraph identification. Focusing on the NP-hard densest k-subgraph problem, we find that stochastic algorithms are enhanced through GBS, which selects dense subgraphs with high probability. These findings rely on a link between graph density and the number of perfect matchings-enumerated by the Hafnian-which is the relevant quantity determining sampling probabilities in GBS. We test our findings by constructing GBS-enhanced versions of the random search and simulated annealing algorithms and apply them through numerical simulations of GBS to identify the densest subgraph of a 30 vertex graph.

Samaneh Bagheri Novir

Naomi R. Solomons, O. Thomas, Dara P. S. McCutcheon

We investigate the effects of photon loss and spectrally impure sources on Gaussian boson sampling (GBS) when used in dense-subgraph-finding algorithms. We find that the effectiveness of these algorithms is remarkably robust to such errors, to such an extent that there exist classical algorithms that can efficiently simulate the underlying GBS. These results suggest that, unlike the GBS problem itself, the speed-up of GBS-based algorithms over classical approaches when applied to the dense-subgraph problem is not exponential. They do suggest, however, that any advantage offered could be achieved on a quantum device with far less stringent requirements on photon loss and purity than general GBS.