BosonSampling in the collision-dominated regime

BosonSampling is the computational problem of sampling from the output distribution of a linear-optical interferometer with n single-photon inputs and m output modes. The interferometer is designed to effect a Haar-random unitary transformation. BosonSampling is hard to solve classically for m much larger than n unless the polynomial hierarchy collapses to the third level, assuming highly plausible complexity-theoretic conjectures. Yet, even in the collision-dominated regime where m∼n, the case we consider in this work, the best-known classical algorithm has average-case time complexity exponential with respect to n. Using a combination of numerical and analytical methods, we analyze the joint photon-number distribution at the output of the interferometer effecting a Haar-random unitary transformation. Our results are compared against the special cases of interferometer outputs, such as the uniform distribution over all possible output states as well as output distribution that exhibit Bose enhancement.