Search

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., 52 pages, 21 figures

In [1] we discussed how quantum gravity may be simulated using quantum devices and gave a specific proposal -- teleportation by size and the phenomenon of size-winding. Here we elaborate on what it means to do 'Quantum Gravity in the Lab' and how size-winding connects to bulk gravitational physics and traversable wormholes. Perfect size-winding is a remarkable, fine-grained property of the size wavefunction of an operator; we show from a bulk calculation that this property must hold for quantum systems with a nearly-AdS_2 bulk. We then examine in detail teleportation by size in three systems: the Sachdev-Ye-Kitaev model, random matrices, and spin chains, and discuss prospects for realizing these phenomena in near-term quantum devices., Comment: 50 pages, 14 figures, Part II of arXiv:1911.06314

With the long-term goal of studying models of quantum gravity in the lab, we propose holographic teleportation protocols that can be readily executed in table-top experiments. These protocols exhibit similar behavior to that seen in the recent traversable wormhole constructions of [1,2]: information that is scrambled into one half of an entangled system will, following a weak coupling between the two halves, unscramble into the other half. We introduce the concept of teleportation by size to capture how the physics of operator-size growth naturally leads to information transmission. The transmission of a signal through a semi-classical holographic wormhole corresponds to a rather special property of the operator-size distribution we call size winding. For more general systems (which may not have a clean emergent geometry), we argue that imperfect size winding is a generalization of the traversable wormhole phenomenon. In addition, a form of signalling continues to function at high temperature and at large times for generic chaotic systems, even though it does not correspond to a signal going through a geometrical wormhole, but rather to an interference effect involving macroscopically different emergent geometries. Finally, we outline implementations feasible with current technology in two experimental platforms: Rydberg atom arrays and trapped ions., 33 pages, 5 figures. This paper has a companion paper (Part II) by the same authors

Significant work has gone into determining the minimal set of entropy inequalities that determine the holographic entropy cone. Holographic systems with three or more parties have been shown to obey additional inequalities that generic quantum systems do not. We consider a two dimensional conformal field theory that is a single boundary of a holographic system and find four additional non-linear inequalities which are derived from strong subadditivity and the formula for the entanglement entropy of a region on the conformal field theory. We also present an equality obtained by application of a hyperbolic extension of Ptolemy's theorem to a two dimensional conformal field theory., Comment: 5 pages, 3 figures