  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\times k}$ be the
distribution of $k\times k$ submatrices of $d\times d$ random unitary matrices,
and $G^{k\times k}$ be the distribution of $k\times 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\times k}$ or $G^{k\times k}$. (2) We prove a surprising size-moment
duality: the $2t$-th moment of the permanent of random $k\times k$ matrices is
equal to the $2k$-th moment of the permanent of $t\times 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\times 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.
