Permanent of random matrices from representation theory: moments, numerics, concentration, and comments on hardness of boson-sampling
AI Breakdown
Get a structured breakdown of this paper — what it's about, the core idea, and key takeaways for the field.
Abstract
Computing the distribution of permanents of random matrices has been an outstanding open problem for several decades. In quantum computing, “anti-concentration” of this distribution is an unproven input for the proof of hardness of the task of boson-sampling. Using a hybrid representation-theoretic and combinatorial approach, we study permanents of random i.i.d. complex Gaussian matrices, and more broadly, submatrices of random unitary matrices. We prove strong lower bounds for all moments of the permanent distribution. Moreover, we provide substantial evidence that our lower bounds are close to being tight, and therefore, constitute accurate estimates for the moments. Let U(d)k×k indicate the distribution of k × k submatrices of d× dHaar distributed random unitary matrices, and Gk×k be the distribution of k × k matrices with matrix elements being i.i.d. standard complex Gaussian random numbers. (1) Using the Schur-Weyl duality (or more precisely, the Howe’s GLk ×GLt duality), we provide an explicit expansion formula for the 2t-th moment of |Perm(M)|, i.e., E|Perm(M)|2t, whenM is drawn from U(d)k×k or Gk×k. (2) When the matrices are drawn from the above distributions, we prove a surprising size-moment duality: the 2t-th moment of the permanent of random k× kmatrices is equal to the 2k-th moment of the permanent of t× tmatrices, (3) We design an algorithm to exactly compute high moments of relatively small matrices. (4)We prove strong lower bounds for arbitrary moments of permanents of matrices drawn from Gk×k or U(k), and conjecture that our lower bounds are close to saturation up to a small multiplicative error. We provide extensive numerical and analytical evidence for our conjecture. (5) Assuming our conjectures, we use the large deviation theory to compute the tail of the log-permanent probability density function of Gaussian matrices for the first time. (6) We argue that it is unlikely that the permanent distribution can be uniquely determined from the integer moments and one may need to supplement the integer moment calculations with extra assumptions in order to prove the permanent anti-concentration conjecture.