  BosonSampling is the leading candidate for demonstrating quantum
computational advantage in photonic systems. While we have recently seen many
impressive experimental demonstrations, there is still a formidable distance
between the complexity-theoretic hardness arguments and current experiments.
One of the largest gaps involves the ratio of photons to modes: all current
hardness evidence assumes a "high-mode" regime in which the number of linear
optical modes scales at least quadratically in the number of photons. By
contrast, current experiments operate in a "low-mode" regime with a linear
number of modes. In this paper we bridge this gap, bringing the hardness
evidence for the low-mode experiments to the same level as had been previously
established for the high-mode regime. This involves proving a new
worst-to-average-case reduction for computing the Permanent that is robust to
large numbers of row repetitions and also to distributions over matrices with
correlated entries.
