Abstract
We describe boson sampling of interacting atoms from the noncondensed fraction of Bose-Einstein-condensed (BEC) gas confined in a box trap as a new platform for studying computational #P-hardness and quantum supremacy of many-body systems. We calculate the characteristic function and statistics of atom numbers via newly found hafnian master theorem. Using Bloch-Messiah reduction, we find that interatomic interactions give rise to two equally important entities - eigen-squeeze modes and eigen-energy quasiparticles - whose interplay with sampling atom states determines behavior of the BEC gas. We infer that two necessary ingredients of #P-hardness, squeezing and interference, are self-generated in the gas and, contrary to Gaussian boson sampling in linear interferometers, external sources of squeezed bosons are not required.