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 case pseudorandom operations can emulate certain properties of truly random ones. Indeed in the classical realm there is by now a well-developed theory of 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 circuits are a powerful source of quantum pseudorandomness. This gives the for the first time a polynomialtime 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 to understanding self-equilibration of closed quantum dynamics.

arXiv comment6 pages, 1 figure. Short version of http://arxiv.org/abs/1208.0692

References in corpus (28)

• Many body localization and thermalization in quantum statistical mechanics
• Black holes as mirrors: quantum information in random subsystems
• Probing the relaxation towards equilibrium in an isolated strongly correlated 1D Bose gas
• Canonical Typicality
• Quantum mechanical evolution towards thermal equilibrium
• Strong and weak thermalization of infinite non-integrable quantum systems
• Aspects of generic entanglement
• Quantum Data Hiding
• Randomizing quantum states: Constructions and applications
• Random Quantum Circuits are Approximate 2-designs
• Proof of the Ergodic Theorem and the H-Theorem in Quantum Mechanics
• The mother of all protocols: Restructuring quantum information's family tree
• Random Quantum Circuits and Pseudo-Random Operators: Theory and Applications
• Approximation by Quantum Circuits
• Efficient Generation of Generic Entanglement
• The spectral gap for some spin chains with discrete symmetry breaking
• Convergence rates for arbitrary statistical moments of random quantum circuits
• Exact convergence times for generation of random bipartite entanglement
• Emergence of typical entanglement in two-party random processes
• Large Deviation Bounds for k-designs
• Comment on the paper "Random Quantum Circuits are Approximate 2-designs"
• Efficiency of Producing Random Unitary Matrices with Quantum Circuits
• Efficient algorithm for multi-qudit twirling for ensemble quantum computation
• Efficient Quantum Tensor Product Expanders and k-designs
• On the convergence to equilibrium of Kac's random walk on matrices
• Computational Complexity and Black Hole Horizons
• Local random quantum circuits are approximate polynomial-designs - numerical results
• Simple Permutations Mix Even Better

Cited by in corpus (42)

• Multiqubit Clifford groups are unitary 3-designs
• Linear growth of quantum circuit complexity
• Pseudorandom States, Non-Cloning Theorems and Quantum Money
• Exact emergent quantum state designs from quantum chaotic dynamics
• Random quantum circuits are approximate unitary $t$-designs in depth $O\left(n{t}^{5+o(1)}\right)$
• Random bosonic states for robust quantum metrology
• Dynamical purification and the emergence of quantum state designs from the projected ensemble
• Efficient unitary designs with nearly time-independent Hamiltonian dynamics
• Characterizing multipartite entanglement with moments of random correlations
• Unitary designs from statistical mechanics in random quantum circuits
• Entanglement, quantum randomness, and complexity beyond scrambling
• Efficient unitary designs with a system-size independent number of non-Clifford gates
• Generalized Entanglement Entropies of Quantum Designs
• Quantum complexity in gravity, quantum field theory, and quantum information science
• Characterizing complexity of many-body quantum dynamics by higher-order eigenstate thermalization
• Closing gaps of a quantum advantage with short-time Hamiltonian dynamics
• Fastest local entanglement scrambler, multistage thermalization, and a non-Hermitian phantom
• Quantum Pseudorandomness and Classical Complexity
• Translation symmetry restoration under random unitary dynamics
• Universal extensions of restricted classes of quantum operations
• Guaranteed recovery of quantum processes from few measurements
• Entanglement characterization using quantum designs
• Entropic uncertainty relations from quantum designs
• Postselection-free learning of measurement-induced quantum dynamics
• Growth of genuine multipartite entanglement in random unitary circuits
• Pseudorandom unitaries are neither real nor sparse nor noise-robust
• Designs via Free Probability
• Computational pseudorandomness, the wormhole growth paradox, and constraints on the AdS/CFT duality
• Observation of entanglement negativity transition of pseudo-random mixed states
• Experimental Implementation of Efficient Quantum Pseudorandomness on a 12-spin System
• Sampling and scrambling on a chain of superconducting qubits
• Estimating the randomness of quantum circuit ensembles up to 50 qubits
• Mixing and localisation in random time-periodic quantum circuits of Clifford unitaries
• Purity of thermal mixed quantum states
• On the explicit constructions of certain unitary $t$-designs
• Quantum and Classical Dynamics with Random Permutation Circuits
• Unitary k-designs from random number-conserving quantum circuits
• Purity decay rate in random circuits with different configurations of gates
• Quantifying multiparticle entanglement with randomized measurements
• Computational Notions of Quantum Min-Entropy
• Pseudoentanglement from tensor networks
• Realizing Unitary $k$-designs with a Single Quench