  A famously hard graph problem with a broad range of applications is computing
the number of perfect matchings, that is the number of unique and complete
pairings of the vertices of a graph. We propose a method to estimate the number
of perfect matchings of undirected graphs based on the relation between
Gaussian Boson Sampling and graph theory. The probability of measuring zero or
one photons in each output mode is directly related to the hafnian of the
adjacency matrix, and thus to the number of perfect matchings of a graph. We
present encodings of the adjacency matrix of a graph into a Gaussian state and
show strategies to boost the sampling success probability. With our method, a
Gaussian Boson Sampling device can be used to estimate the number of perfect
matchings significantly faster and with lower energy consumption compared to a
classical computer.
