Abstract
The permanent of a Gaussian matrix is known to be #P-hard to approximate in the worst case. It is also #P-hard to compute exactly on average. Should we expect that it remains #P-hard to approximate on average? In this work we take a first step towards resolving this question: We present a quasipolynomial time deterministic algorithm for approximating the permanent of a typical n x n random matrix with unit variance and vanishing mean µ = 1/ polyloglog (n) to within inverse polynomial multiplicative error. Alternatively, one can achieve permanent approximation for matrices with mean µ=1/polylog(n) in sub-exponential time. The proposed algorithm significantly extends the regime of matrices for which efficient approximation of the permanent is known. This is because unlike previous algorithms which require a stringent correlation between the signs of the entries of the matrix it can tolerate random ensembles in which this correlation is negligible (albeit non-zero). Among important special cases we note: 1. Biased Gaussian: each entry is a complex Gaussian with unit variance 1 and mean µ. 2. Biased Bernoulli: each entry is ?1 + µ with probability 1/2, and 1 with probability 1/2. These results counter the common intuition that the difficulty of computing the permanent, even approximately, stems merely from our inability to treat matrices with many opposing signs. The Gaussian ensemble approaches the threshold of a conjectured hardness of computing the permanent of a zero-mean Gaussian matrix. This conjecture is one of the baseline assumptions of the BosonSampling paradigm that has received vast attention in recent years in the context of quantum supremacy experiments. We furthermore show that the permanent of the biased Gaussian ensemble is #P-hard to compute exactly on average. To our knowledge, this is the first natural example of a counting problem that becomes easy only when average case and approximation are combined. On a technical level, our approach stems from a recent approach taken by Barvinok who used Taylor series approximation of the logarithm of a certain univariate polynomial related to the permanent. Our main contribution is to introduce an average-case analysis of such related polynomials.