Complexity of sampling bosonic atoms in the presence of weak interactions*

We study the complexity of sampling from the particle number distribution of interacting bosonic atoms described by the Bose-Hubbard model. In the noninteracting limit, the problem is equivalent to sampling from a linear optical network, whose complexity has been well studied in the framework of Boson Sampling. For neutral atoms trapped in an optical lattice, residual interactions may exist between the atoms, which could crucially alter the sampling complexity from the noninteracting case. When interactions are weak, we show that the sampling complexity is close to that of the noninteracting evolution in the total variation distance (TVD). Using Hubbard Stratonovich transformation, we express the transition amplitudes as an ensemble average of random permanents and show that TVD is upper bounded by a polynomial in interaction strength, evolution time, and particle number. Further, assuming that an efficient circuit implementation of the Bose-Hubbard evolution exists, we apply the worst-to-average-case hardness reduction technique to show that sampling with random interaction strength is also equivalent to the noninteracting case. We numerically verify our bounds in the settings of random hopping on an all-to-all geometry, and uniform nearest-neighbor hopping on a linear chain.