Local random quantum circuits are approximate polynomial-designs (Q506483)

The article is an important reference for anyone working on quantum computation, quantum cryptography, quantum information and complex quantum systems science. Indeed, while random unitary matrices, drawn from the Haar measure on the unitary group, have major applications in quantum information and communications as well as quantum cryptography, in order to implement a random Haar unitary, an exponential number of two-qubit gates and random bits are needed. An alternative is to use an approximate unitary t-design as a distribution of unitaries that mimic properties of the Haar measure for polynomials of degree up to t in the entries of the unitaries. The article addresses the efficient constructions of quantum t-designs, namely, the authors prove that local random quantum circuits acting on n qubits composed of polynomially many nearest neighbor two-qubit gates form an approximate unitary poly(n)-design. The proof itself makes contributions to different research areas by combining techniques from quantum many-body theory, representation theory and the theory of Markov chains, in this sense, it provides for a relevant reference for researchers working on these different fields. A particularly relevant contribution of the authors' work is the realization that one may connect the problem of showing that random quantum circuits are t-unitary designs to lower bounding the spectral gap of a many-body quantum Hamiltonian, which is of interest for anyone working in complex quantum systems science. The article is divided in ten sections. Section 1 introduces the article, providing and overview of the main work and addresses the main concepts of tensor-product expanders and approximate unitary design. In section 2, the authors present the main results and address their optimality. In section 3, the authors address applications of their results. Sections 4 to 9 are devoted the proofs, and section 10 concludes with a discussion and open questions. The applications section is of particular interest for the physics and computer science communities, namely, four applications are provided and are of major interest for both quantum computer science and complex quantum systems science. The first application regards the mimicking of properties of the Haar measure by approximate quantum t-designs. The second application is related to the pseudo-randomness properties of efficiently generated states and unitaries, namely, data hiding where one is unable to distinguish between a pure state or a maximally mixed state. A consequence of the article's work is that it is possible to find a state which can be generated by a circuit of size s but that is indistinguishable from a maximally mixed state by any measurement implementable by circuits of size r, for r sufficiently smaller than s. The authors show this in corollary 10 and apply this corollary to the problem of quantum circuit minimization. The third and fourth applications are of particular interest to those working in complex quantum systems. The third application regards the dynamical equilibration of subsystems of a time-evolving quantum system under unitary state transition. That is, when a large quantum system undergoes unitary state transition, even though information is conserved under this state transition, locally, due to the building up of entanglement, there takes place local equilibration over small subsystems. The main contribution of the article's results for this problem regards the limits of equilibration in such cases. This is linked to the authors' work on the second application. Namely, corollary 10 implies that, in generic quantum dynamics given by quantum circuits, the system equilibrates with respect to all measurements of low complexity. A second consequence of the article's work is that it strengthens the connection between the time of equilibration of small subsystems of a closed quantum system and the circuit complexity of the unitary that diagonalizes the system's Hamiltonian. The article's results confirm that random circuits form an approximate unitary 4-design and that most such circuits have large circuit complexity. The fourth application regards the generation of topological order. Which is of importance for both condensed matter physics and quantum technologies. The authors begin by reviewing the concept of topologically ordered states and then prove (in corollary 15) that almost every local dynamics in 1D generates topological order at the fastest possible rate. An implication of the corollary is also that one dimensional parallel random circuits scramble in linear time. In its whole, the work provides an important contribution for quantum computer science, mathematics and physics that may fuel future research on this subject matter. Regarding this last point, the authors indicate some open research directions in section 10, specifically: -- The first open point is the extension of the article's results to an arbitrary universal set of gates; -- The second open point comes from the authors' conjecture that, while for nearest-neighbor circuits in one dimension, the results are near-optimal, in other geometries, the results may be far from optimal, namely, for interactions on general graphs, according to the authors, it is plausible that parallel random circuits mix in time comparable to the diameter of the graph, a point that the authors establish only in the case of graphs of linear diameter; -- The third open point is the strengthening of the article's results to prove the incompressibility of quantum circuits, a point that is addressed in the article, and that is an important venue of future research with importance for quantum computer science; -- A fourth open point regards random time-independent Hamiltonians, rather than sequences of unitaries, for which the phenomenon of Anderson localization prevents mixing in many cases. The authors also point as future venue of research the cases in which rapid mixing nevertheless occurs, and to give a plausible derivation of the observed phenomenon of thermalization.