Boson sampling with ultracold atoms in a programmable optical lattice

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 <a:math xmlns:a="http://www.w3.org/1998/Math/MathML"><a:mi>N</a:mi></a:math> 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 <b:math xmlns:b="http://www.w3.org/1998/Math/MathML"><b:mi>N</b:mi></b:math>, we develop a theoretical model based on a master equation that accounts for particle losses, but does not include technical errors. Our results show that atomic samplers have the potential to achieve a quantum advantage over today's best supercomputers with <c:math xmlns:c="http://www.w3.org/1998/Math/MathML"><c:mrow><c:mi>N</c:mi><c:mo>≳</c:mo><c:mn>40</c:mn></c:mrow></c:math>.