Quantum computational advantage with Gaussian boson sampling

Quantum computers promise to perform certain tasks that are believed to be intractable to classical computers. Boson sampling is such a task and is considered a strong candidate to demonstrate the quantum computational advantage. Rather than being a single-shot event, the establishment of quantum computational advantage will be the result of a long-term competition between the quantum devices and the classical algorithms. We report Gaussian boson sampling (GBS) experiment which registered up to 113 photon-click events out of a on a 144-mode fully connected photonic circuit. Exploring the idea of stimulated emission of squeezed photons, a new high-brightness and scalable quantum light source is developed which has simultaneously near-unity purity and efficiency. The obtained samples are efficiently validated, ruling out the known classical mockup hypotheses. We measure and reveal the high-order correlations in the GBS samples, which are evidence of robustness against certain classical simulation schemes. This work yields a Hilbert space dimension up to ∼10^43, and a sampling rate ∼10^24 faster than using brute-force simulation on classical supercomputers, and an overwhelming advantage over the best known exact classical sampling algorithms.

In another aspect, Gaussian boson sampling (GBS) is not only a feasible protocol for demonstrating quantum computational advantage, but also mathematically associated with certain graph-related and quantum chemistry problems. In particular, it is proposed that the generated samples from the GBS could be harnessed to enhance the classical stochastic algorithms in searching some graph features. We investigate the open question of whether the GBS enhancement over the classical stochastic algorithms persists – and how it scales – with an increasing system size on Jiuzhang in the computationally interesting regime. We experimentally observe the presence of GBS enhancement with large photon-click number and a robustness of the enhancement under certain noise. Our work is a step toward testing real-world problems using the existing noisy intermediate-scale quantum computers.