Advances and Improved Methods for Quantum Algorithms

Anticoncentration is a key property that underpins arguments for hardness of various quantum supremacy proposals. It has been proved for quantum supremacy proposals, such as Random Circuit Sampling, IQP, or Fermion Sampling. However, it remains unproven for the paradigmatic example of Boson Sampling for over 10 years since inception of this scheme.

Our work provides a proof for the anticoncentration conjecture in the Boson Sampling scheme in the low-mode regime, where the number of modes (m) grows linearly with the number of particles (n). Together with earlier findings, this result provides a strong hardness guarantee for the computational advantage of Boson Sampling over classical computers in this regime. To reach this conclusion, we carefully analyze the representation of SU(m) (describing linear optical transformations) on two copies of bosonic subspace. Specifically, we provide explicit expressions for the projections onto irreducible representations and express their matrix elements via purities and overlaps of q-particle reduced density matrices of Fock states. Furthermore, we give an explicit formula for the average purity over all n-particle Fock states, observing a Page curve-like behavior. Beside proving anticoncentration, we also use our findings to give an efficient algorithm for computation of averaged linear cross-entropy benchmarking score in  low-mode regime Boson Sampling, which can be used for the validation of the output distribution of sampling devices.