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
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∣≥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.
(MATH) We study approximation algorithms for the permanent of an n x n (0,1) matrix A based on the following simple idea: obtain a random matrix B by replacing each 1-entry of A independently by ± e, where e is a random basis element of a suitable algebra; then output |det(B)|2. This estimator is always unbiased, but it may have exponentially large variance. In our first main result we show that, if we take the algebra to be a Clifford algebra of dimension polynomial in n, then we get an estimator with small variance. Hence only a constant number of trials suffices to estimate the permanent to good accuracy. The idea of using Clifford algebras is a natural extension of earlier work by Godsil and Gutman, Karmarkar et al., and Barvinok, who used the real numbers, complex numbers and quaternions respectively.(MATH) The above result implies that, in principle, this approach gives a fully-polynomial randomized approximation scheme for the permanent, provided |det(B)|2 can be efficiently computed in the Clifford algebras. Since these algebras are non-commutative it is not clear how to do this. However, our second main result shows how to compute in polynomial time an estimator with the same mean and variance over the 4-dimensional algebra (which is the quaternions, and is non-commutative); in addition to providing some hope that the computations can be performed in higher dimensions, this quaternion algorithm provides an exponential improvement in the variance over that of the 2-dimensional complex version studied by Karmarkar et al.
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.
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.
In this work, we study the computational complexity of quantum determinants, a
q-deformation of matrix permanents: Given a complex number
q on the unit circle in the complex plane and an
n×n matrix
X, the
q-permanent of
X is defined as
Perq(X)=∑σ∈Snqℓ(σ)X1,σ(1)…Xn,σ(n), where
ℓ(σ) is the inversion number of permutation
σ in the symmetric group
Sn on
n elements. The function family generalizes determinant and permanent, which correspond to the cases
q=−1 and
q=1 respectively. For worst-case hardness, by Liouville's approximation theorem and facts from algebraic number theory, we show that for primitive
m-th root of unity
q for odd prime power
m=pk, exactly computing
q-permanent is
ModpP-hard. This implies that an efficient algorithm for computing
q-permanent results in a collapse of the polynomial hierarchy. Next, we show that computing
q-permanent can be achieved using an oracle that approximates to within a polynomial multiplicative error and a membership oracle for a finite set of algebraic integers. From this, an efficient approximation algorithm would also imply a collapse of the polynomial hierarchy. By random self-reducibility, computing
q-permanent remains to be hard for a wide range of distributions satisfying a property called the strong autocorrelation property. Specifically, this is proved via a reduction from
1-permanent to
q-permanent for
O(1/n2) points
z on the unit circle. Since the family of permanent functions shares common algebraic structure, various techniques developed for the hardness of permanent can be generalized to
q-permanents.
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.