Complexity-Theoretic Foundations of BosonSampling with a Linear Number of Modes

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 particles to modes—all current hardness evidence assumes a “dilute” regime in which the number of linear optical modes scales at least quadratically in the number of particles. By contrast, current experiments operate in a “saturated” regime with a linear number of modes. In this paper, we bridge this gap, bringing the hardness evidence for experiments in the saturated regime to the same level as had been previously established for the dilute regime. This involves proving a worst-to-average-case reduction for computing the permanent, which is robust both to large numbers of row repetitions and also to distributions over matrices with correlated entries. We also apply similar arguments to give evidence for hardness of Gaussian BosonSampling in the saturated regime.