title: Efficient Quantum Pseudorandomness.
abstract: Randomness is both a useful way to model natural systems and a useful tool for engineered systems, e.g., in computation, communication, and control. Fully random transformations require exponential time for either classical or quantum systems, but in many cases pseudorandom operations can emulate certain properties of truly random ones. Indeed, in the classical realm there is by now a well-developed theory regarding such pseudorandom operations. However, the construction of such objects turns out to be much harder in the quantum case. Here, we show that random quantum unitary time evolutions ("circuits") are a powerful source of quantum pseudorandomness. This gives for the first time a polynomial-time construction of quantum unitary designs, which can replace fully random operations in most applications, and shows that generic quantum dynamics cannot be distinguished from truly random processes. We discuss applications of our result to quantum information science, cryptography, and understanding the self-equilibration of closed quantum dynamics.
authors.affiliation: Quantum Architectures and Computation Group, Microsoft Research, Redmond 11728, Washington, USA.|Department of Computer Science, University College London, London, WC1E 6BT, United Kingdom.
authors.forename: Fernando G S L
authors.initials: FG
authors.lastname: Brandão
authors.affiliation: Center for Theoretical Physics, MIT, Cambridge MA 02139, USA.
authors.forename: Aram W
authors.initials: AW
authors.lastname: Harrow
authors.affiliation: National Quantum Information Center of Gdansk, 81-824 Sopot, Poland.
authors.forename: Michał
authors.initials: M
authors.lastname: Horodecki