Approximating the Permanent of a Random Matrix with Polynomially Small Mean: Zeros and Universality

We study algorithms for approximating the permanent of a random matrix when the entries are slightly biased away from zero. This question is motivated by the goal of understanding the classical complexity of linear optics and boson sampling (Aaronson and Arkhipov '11; Eldar and Mehraban '17). Barvinok's interpolation method enables efficient approximation of the permanent, provided one can establish a sufficiently large zero-free region for the polynomial per(zJ + W), where J is the all-ones matrix and W is a random matrix with independent mean-zero entries. We show that when the entries of W are standard complex Gaussians, all zeros of the random polynomial per(zJ + W) lie within a disk of radius {O}\(n^-1/3\), which yields an approximation algorithm when the bias of the entries is Ω\(n^-1/3\). Previously, there were no efficient algorithms at biases smaller than 1/polylog(n), and it was unknown whether there typically exist zeros z with |z| ge 1. As a complementary result, we show that the bulk of the zeros, namely (1 - ε)n of them, have magnitude Θ\(n^-1/2\). This prevents our interpolation method from contradicting the conjectured average-case hardness of approximating the permanent. We also establish analogous zero-free regions for the hardcore model on general graphs with complex vertex fugacities. In addition, we prove universality results establishing zero-free regions for random matrices W with i.i.d. subexponential entries.