  Gaussian Boson sampling (GBS) provides a highly efficient approach to make
use of squeezed states from parametric down-conversion to solve a classically
hard-to-solve sampling problem. The GBS protocol not only significantly
enhances the photon generation probability, compared to standard boson sampling
with single photon Fock states, but also links to potential applications such
as dense subgraph problems and molecular vibronic spectra. Here, we report the
first experimental demonstration of GBS using squeezed-state sources with
simultaneously high photon indistinguishability and collection efficiency. We
implement and validate 3-, 4- and 5-photon GBS with high sampling rates of 832
kHz, 163 kHz and 23 kHz, respectively, which is more than 4.4, 12.0, and 29.5
times faster than the previous experiments. Further, we observe a quantum
speed-up on a NP-hard optimization problem when comparing with simulated
thermal sampler and uniform sampler.
