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.
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.
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.
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.
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.
Gaussian boson sampling is a model of photonic quantum computing that has attracted attention as a platform for building quantum devices capable of performing tasks that are out of reach for classical devices. There is therefore significant interest, from the perspective of computational complexity theory, in solidifying the mathematical foundation for the hardness of simulating these devices. We show that, under the standard Anti-Concentration and Permanent-of-Gaussians conjectures, there is no efficient classical algorithm to sample from ideal Gaussian boson sampling distributions (even approximately) unless the polynomial hierarchy collapses. The hardness proof holds in the regime where the number of modes scales quadratically with the number of photons, a setting in which hardness was widely believed to hold but that nevertheless had no definitive proof. Crucial to the proof is a new method for programming a Gaussian boson sampling device so that the output probabilities are proportional to the permanents of submatrices of an arbitrary matrix. This technique is a generalization of Scattershot BosonSampling that we call BipartiteGBS. We also make progress towards the goal of proving hardness in the regime where there are fewer than quadratically more modes than photons (i.e., the high-collision regime) by showing that the ability to approximate permanents of matrices with repeated rows/columns confers the ability to approximate permanents of matrices with no repetitions. The reduction suffices to prove that GBS is hard in the constant-collision regime.