  Gaussian Boson Sampling (GBS) generate random samples of photon-click
patterns from a class of probability distributions that are hard for a
classical computer to sample from. Despite heroic demonstrations for quantum
supremacy using GBS, Boson Sampling, and instantaneous quantum polynomial (IQP)
algorithms, systematic evaluations of the power of these quantum-enhanced
random samples when applied to provably hard problems, and performance
comparisons with best-known classical algorithms have been lacking. We propose
a hybrid quantum-classical algorithm using the GBS for the NP-complete problem
of determining if two graphs are vertex minor of one another. The graphs are
encoded in GBS and the generated random samples serve as feature vectors in the
support vector machine (SVM) classifier. We find a graph embedding that allows
trading between the one-shot classification accuracy and the amount of input
squeezing, a hard-to-produce quantum resource, followed by repeated trials and
majority vote to reach an overall desired accuracy. We introduce a new
classical algorithm based on graph spectra, which we show outperforms various
well-known graph-similarity algorithms. We compare the performance of our
algorithm with this classical algorithm and analyze their time vs problem-size
scaling, to yield a desired classification accuracy. Our simulation suggests
that with a near-term realizable GBS device- $5$ dB pulsed squeezer, $12$-mode
unitary, and reasonable assumptions on coupling efficiency, on-chip losses and
detection efficiency of photon number resolving detectors-we can solve a
$12$-node vertex minor instances with about $10^3$ fold lower time compared to
a powerful desktop computer.
