Caltech Logo

IQIM Postdoctoral and Graduate Student Seminar

Friday, October 1, 2021
11:00am to 12:00pm
Add to Cal
Online Event
Permanent of random matrices from representation theory: moments, numerics, concentration, and comments on hardness of boson-sampling
Sepehr Ghazi Nezami, Sherman Fairchild Postdoctoral Scholar, Preskill Group,

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 the 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. (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 a random Gaussian matrix, or a minor of a random unitary matrix. (2) We prove a surprising size-moment duality: the 2t-th moment of the permanent of random k by k matrices is equal to the 2k-th moment of the permanent of t by 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 random matrices, 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.

The talk will be based on: arXiv 2104.06423

Join Zoom Meeting

https://caltech.zoom.us/j/87824644586?pwd=VEZzUjZWTHppMUZ5bDE2eHQyRGowZz09

Meeting ID: 878 2464 4586

Passcode: 369456

For more information, please contact Marcia Brown by phone at 626-395-4013 or by email at marciab@caltech.edu.