CaltechAUTHORS
  A Caltech Library Service

Permanent of random matrices from representation theory: moments, numerics, concentration, and comments on hardness of boson-sampling

Nezami, Sepehr (2021) Permanent of random matrices from representation theory: moments, numerics, concentration, and comments on hardness of boson-sampling. . (Unpublished) https://resolver.caltech.edu/CaltechAUTHORS:20210809-220321102

[img] PDF - Submitted Version
See Usage Policy.

3MB

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20210809-220321102

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. We study permanents of random i.i.d. complex Gaussian matrices, and more broadly, submatrices of random unitary matrices. Using a hybrid representation-theoretic and combinatorial approach, we prove strong lower bounds for all moments of the permanent distribution. We provide substantial evidence that our bounds are close to being tight and constitute accurate estimates for the moments. Let U(d)^(k×k) be the distribution of k×k submatrices of d×d random unitary matrices, and Gk×k be the distribution of k×k complex Gaussian matrices. (1) Using the Schur-Weyl duality (or the Howe duality), we prove an expansion formula for the 2t-th moment of |Perm(M)| when M is drawn from U(d)^(k×k) or G^(k×k). (2) We prove a surprising size-moment duality: the 2t-th moment of the permanent of random k×k matrices is equal to the 2k-th moment of the permanent of t×t matrices. (3) We design an algorithm to exactly compute high moments of the permanent of small matrices. (4) We prove lower bounds for arbitrary moments of permanents of matrices drawn from G^(k×k) or U(k), and conjecture that our lower bounds are close to saturation up to a small multiplicative error. (5) Assuming our conjectures, we use the large deviation theory to compute the tail of the distribution of log-permanent 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 moment calculations with extra assumptions to prove the anti-concentration conjecture.


Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription
http://arxiv.org/abs/2104.06423arXivDiscussion Paper
Additional Information:The author would like to thank Scott Aaronson, Alex Arkhipov, David Gross, Nick Hunter-Jones, Richard Keung, Saeed Mehraban, Terence Tao, Van Vu, and MichaelWalter for illuminating discussions. The author is supported by the Walter Burke Institute for Theoretical Physics and IQIM at Caltech.
Group:Walter Burke Institute for Theoretical Physics, Institute for Quantum Information and Matter
Funders:
Funding AgencyGrant Number
Walter Burke Institute for Theoretical Physics, CaltechUNSPECIFIED
Institute for Quantum Information and Matter (IQIM)UNSPECIFIED
Record Number:CaltechAUTHORS:20210809-220321102
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20210809-220321102
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:110185
Collection:CaltechAUTHORS
Deposited By: George Porter
Deposited On:10 Aug 2021 15:42
Last Modified:10 Aug 2021 15:42

Repository Staff Only: item control page