Approximating the Permanent of a Random Matrix with Polynomially Small Mean: Zeros and Universality
This addresses the computational complexity of approximating permanents, relevant for quantum computing and statistical physics, but is incremental as it builds on Barvinok's interpolation method and prior work on zero-free regions.
The paper tackles the problem of approximating the permanent of a random matrix with slightly biased entries, motivated by understanding the classical complexity of boson sampling, and shows that zeros of the random polynomial lie within a disk of radius ̃O(n^{-1/3}), enabling an approximation algorithm for biases ̃Ω(n^{-1/3}), while also revealing that most zeros have magnitude Θ(n^{-1/2}) to avoid contradicting hardness conjectures.
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Ω(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 - ε)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.