  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.
