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

arXiv:2604.01367v1 Announce Type: new
Abstract: 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 emph{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 $mathrm{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 $mathrm{per}(zJ + W)$ lie within a disk of radius $tilde{O}(n^{-1/3})$, which yields an approximation algorithm when the bias of the entries is $tilde{Omega}(n^{-1/3})$. Previously, there were no efficient algorithms at biases smaller than $1/mathrm{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 – epsilon)n$ of them, have magnitude $Theta(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.