Jianan Li

Weak Permanent Anti-Concentration for Random Gaussian Matrices in Boson Sampling

A weak anti-concentration bound is established by upper-bounding the probability that a random Gaussian permanent is superexponentially smaller than its standard deviation, which implies that classically simulating boson sampling to within a superexponentially small total variation distance would collapse the polynomial hierarchy.