Boson sampling of many-body quantum random walkers on a lattice

The Boson sampling problem introduced by Aaronson and Arkhipov, showed quantum supremacy in terms of sampling complexity for the output distribution of photons scattering from a linear optical network. We study here an analogous problem in case of multiple boson continuous-time quantum random walkers on a lattice, e.g., Bosonic atoms in an optical lattice. Results are presented for the special case of a 1 D lattice with nearest neighbor and uniform hopping amplitude. We demonstrate that the sampling problem is classically tractable until the time of evolution passes the logarithmic scale in the number of particles. We also conjecture that this problem is classically hard beyond the logarithmic scale. Periodic and hard wall boundary conditions lead to the same result when number of lattice sites are substantially larger than the number of particles. When extended to arbitrary hopping amplitudes and on-site interactions, this corresponds to sampling complexity for a general Bose-Hubbard model.