Recent Theoretical and Experimental Progress on Boson Sampling

Boson sampling is a restricted model of quantum computation, designed to achieve quantum advantage using nonuniversal quantum systems. By harnessing the quantum interference of indistinguishable bosons (typically photons), it becomes possible to sample from a probability distribution, which is intractable for classical computers. This paper reviews the theoretical foundations of boson sampling and its variations, including Fock-state, scattershot, and Gaussian boson sampling, along with significant experimental progress, from early small-scale demonstrations to large-scale quantum supremacy claims. We further explore classical algorithms for simulating boson sampling, which are crucial for benchmarking the performance of experimental results. Finally we examine potential applications of boson sampling in various fields, including simulation of molecular vibronic spectra in quantum chemistry, and solution of graph-based problems in optimization. These applications demonstrate the wide-ranging impact that boson sampling could have on industries that rely on complex computational models, making it a promising quantum technology for near-term applications.