Sampling from a quantum distribution can be exponentially hard for classical computers and yet could be performed efficiently by a noisy intermediate-scale quantum device. A prime example of a distribution that is hard to sample is given by the output states of a linear interferometer traversed by N identical boson particles. Here, we propose a scheme to implement such a boson sampling machine with ultracold atoms in a polarization-synthesized optical lattice. We experimentally demonstrate the basic building block of such a machine by revealing the Hong-Ou-Mandel interference of two bosonic atoms in a four-mode interferometer. To estimate the sampling rate for large N, we develop a theoretical model based on a master equation. Our results show that a quantum advantage compared to today's best supercomputers can be reached with N≳40.

}, Author = {Robens, C. AND Arrazola, I. AND Alt, W. AND Meschede, D. AND Lamata, L. AND Solano, E. AND Alberti, A.}, Journal = {arXiv:2208.12253 [quant-ph]}, Pages = {}, Title = {{Boson Sampling with Ultracold Atoms}}, Volume = {}, Year = {2022} }