The permanent is #P-hard to compute exactly on average for natural random matrices including matrices over finite fields or Gaussian ensembles. Should we expect that it remains #P-hard to compute on average if we only care about approximation instead of exact computation? In this work we take a first step towards resolving this question: We present a quasi-polynomial time deterministic algorithm for approximating the permanent of a typical n × n random matrix with unit variance and vanishing mean μ = O(ln ln n)-1/8to within inverse polynomial multiplicative error. (alternatively, one can achieve permanent approximation for matrices with mean μ = 1/polylog(n) in time 2n(ε), for arbitrarily small ε>0). 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 [1], [2] 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 [3] 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 analysis and approximation are combined. On a technical level, our approach stems from a recent approach taken by Barvinok [1], [4], [5], [6] 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. We complement our approach with a new technique for iteratively computing a Taylor series approximation of a function that is analytical in the vicinity of a curve in the complex plane. This method can be viewed as a computational version of analytic continuation in complex analysis.
Recent demonstrations of quantum computational advantage have been driven largely by sampling problems. A prominent model, boson sampling, involves sampling from the output distribution of a linear optical network. However, its classical hardness hinges on two plausible yet less-studied conjectures: the average-case hardness of approximating Gaussian permanents, and the permanent anti-concentration conjecture (PACC). The PACC is a purely mathematical assertion regarding the distributional properties of random Gaussian matrices. While the typical magnitude of the permanent has been established for discrete random matrices, the complex Gaussian case, which governs transition amplitudes in linear optical networks, has remained open. Here, we establish a weak anti-concentration bound by upper-bounding the probability that a random Gaussian permanent is superexponentially smaller than its standard deviation. Tightening this bound to an inverse-polynomial fraction would prove the original PACC. As a corollary, we establish the typical magnitude of Gaussian permanents, on par with Tao and Vu's seminal result for Bernoulli matrices. Combined with the Aaronson-Arkhipov framework, our result implies that classically simulating boson sampling to within a superexponentially small total variation distance would collapse the polynomial hierarchy, assuming the remaining conjectures hold.
The algorithm and complexity of approximating the permanent of a matrix is an extensively studied topic. Recently, its connection with quantum supremacy and more specifically BosonSampling draws a special attention to the average-case approximation problem of the permanent of random matrices with zero or small mean value for each entry. Eldar and Mehraban (FOCS 2018) gave a quasi-polynomial time algorithm for random matrices with mean at least 1/polyloglog(n). In this paper, we improve the result by designing a deterministic quasi-polynomial time algorithm and a PTAS for random matrices whose module of mean is at least 1/ polylog(n). We note that if the algorithm can be further improved to work with a mean value that is a sufficiently small 1/poly(n), it will disprove a central conjecture for quantum supremacy. Our algorithm is also much simpler and has a better and flexible trade-off for running time. The running time can be quasi-polynomial in both n and 1/∊, or PTAS (polynomial in n but exponential in 1/∊), where ∊ is the approximation parameter.
Around 2002, Leonid Gurvits gave a striking randomized algorithm to approximate the permanent of an
n×n matrix A. The algorithm runs in
O(n2/ε2) time, and approximates
Per(A) to within
±ε∥A∥n additive error. A major advantage of Gurvits's algorithm is that it works for arbitrary matrices, not just for nonnegative matrices. \ This makes it highly relevant to quantum optics, where the permanents of bounded-norm complex matrices play a central role. (In particular,
n×n permanents arise as the transition amplitudes for
n identical photons.) Indeed, the existence of Gurvits's algorithm is why, in their recent work on the \textit{hardness} of quantum optics, Aaronson and Arkhipov (AA) had to talk about sampling problems rather than ordinary decision problems. In this paper, we improve Gurvits's algorithm in two ways. First, using an idea from quantum optics, we generalize the algorithm so that it yields a better approximation when the matrix A has either repeated rows or repeated columns. Translating back to quantum optics, this lets us classically estimate the probability of any outcome of an AA-type experiment -- even an outcome involving multiple photons "bunched" in the same mode -- at least as well as that probability can be estimated by the experiment itself. It also yields a general upper bound on the probabilities of "bunched" outcomes, which resolves a conjecture of Gurvits and might be of independent physical interest. Second, we use
ε-biased sets to derandomize Gurvits's algorithm, in the special case where the matrix A is nonnegative. More interestingly, we generalize the notion of
ε-biased sets to the complex numbers, construct "complex
ε-biased sets", then use those sets to derandomize even our generalization of Gurvits's algorithm to the case (again for nonnegative A) where some rows or columns are identical. Whether Gurvits's algorithm can be derandomized for general A remains an outstanding problem.
We report on a computational and experimental study of permanents. On the computational side, we use the GPU to greaatly accelerate the computation of permanents over
C, R, Fp and
Q. First, for Haar-distributed unitary matrices~
U, the permanent $\perm(U)$ follows a circularly-symmetric complex Gaussian distribution
CN(0,σ2) -- we confirm this via a number of tests for
n up to~23 with
50,000 samples. The DFT matrix permanent is an extreme outlier for every prime
n≥7. In contrast, for Haar-random \emph{orthogonal} matrices~
O, the permanent $\perm(O)$ is approximately real Gaussian but with positive excess kurtosis that decays as~
O(1/n), indicating slower convergence. For matrices with Gaussian entries (GUE, GOE, Ginibre), the permanent follows an
α-stable distribution with stability index
α≈1.0--
1.4, well below the Gaussian value
α=2. We test Aaronson's conjecture that $|\perm(X)|^2$ is asymptotically lognormal for Gaussian~
X: it is plausible for the complex Ginibre and GOE ensembles, but appears to fail for GUE and real Ginibre, where the
α-stable tails prevent convergence. Anti-concentration, however, holds for all Gaussian ensembles and is more robust than for Haar unitaries.
Secondly, we study the permanent along geodesics on the unitary group. For the geodesic from the identity to the
n-cycle permutation matrix, we find a universal scaling function $f(t)=\frac{1}{n}\ln|\perm(γ(t))|$ that is independent of~
n in the large-
n limit, with a midpoint value \[
\perm(γ({\textstyle\frac12}))
= (-1)^{(n-1)/2}\cdot 2e^{-n}\bigl(1+\tfrac{1}{3n}+O(n^{-2})\bigr) \] for odd~
n and zero for even~
n. We also study the geodesic forom the identity to the DFT matrix.
Since the celebrated work of Jerrum, Sinclair, and Vigoda [J. ACM, 51 (2004), pp. 671–697], we have known that the permanent of a matrix with entries in
{0,1} can be approximated in randomized polynomial time by using a rapidly mixing Markov chain to sample perfect matchings of a bipartite graph. A separate strand of the literature has pursued the possibility of an alternate, algebraic polynomial-time approximation scheme. These schemes work by replacing each 1 with a random element of an algebra
A and considering the determinant of the resulting matrix. In the case where
A is noncommutative, this determinant can be defined in several ways. We show that for some estimators based on the conventional determinant, the critical ratio of the second moment to the square of the first—and therefore the number of trials we need to obtain a good estimate of the permanent—is
(1+O(1/d))n when
A is the algebra of
d×d matrices. These results can be extended to group algebras and semisimple algebras in general. We also study the symmetrized determinant of Barvinok, showing that the resulting estimator has small variance when d is large enough. However, if d is constant—the only case in which an efficient algorithm is known—we show that the critical ratio exceeds
2n/nO(d). Thus our results do not provide a new polynomial-time approximation scheme for the permanent. Indeed, they suggest that the algebraic approach to approximating the permanent faces significant obstacles. We obtain these results using diagrammatic techniques in which we express matrix products as contractions of tensor products. When these matrices are chosen randomly according to the Gaussian distribution, we can evaluate the trace of these products in terms of the cycle structure of a suitably random permutation. In the symmetrized case, our estimates are then derived by a connection with the character theory of the symmetric group.