Quantum advantage with noisy boson sampling and density of bosons
V. S. Shchesnovich · arXiv (Cornell University) · 2019
Inevitable noise is the main problem in demonstration of computational advantage of quantum devices, such as boson sampling, over digital computers. Can a noisy realization of boson sampling be efficiently and faithfully simulated classically? It is shown how one can distinguish the output distribution of noisy $N$-boson sampling from that of classical approximations with mixtures of quantum interferences of up to $K\ll \sqrt{N}$ bosons, with a number of samples that depends solely on $K$, noise amplitude and density of bosons $\rho = N/M$, where $M$ is network size. The surprising result is that noisy boson sampling in a regime of finite density of bosons $\rho\le 1$, i.e., on a small network $M = N/\rho$, retains scalable quantum advantage to arbitrary large number of bosons despite the presence of finite noise.