Sampling complexity of interacting bosonic random walkers on a lattice

A central goal for modern quantum information science is to demonstrate computational speedup for experimentally feasible architectures in the noisy intermediate-scale regime. In a previous work, we studied this problem in the context of simulating boson sampling by noninteracting bosonic atoms on a one-dimensional lattice [1]. We extend these results to include Bose-Hubbard-type interactions. In the presence of weak interactions, we show that the output-sampling distribution is close to that of a free-boson sampler in the total variational distance. We calculate the scaling of the interaction-strength such that this total variational distance is bounded by a constant, demonstrating a regime where the sampling complexity is equivalent to that of the corresponding boson sampler. We close with some outlook for the possibility of applying worst-to-average-case reduction tools to extend these results beyond the perturbative regime.

[1] G. Muraleedharan et al. NJP, 21(5), 055003.