Local random quantum circuits are approximate polynomial-designs

DOI10.1007/S00220-016-2706-8zbMATH Open1367.81035arXiv1208.0692OpenAlexW3123208069WikidataQ59711908 ScholiaQ59711908MaRDI QIDQ506483FDOQ506483

Authors: Fernando G. S. L. Brandão, Aram W. Harrow, M. Horodecki 

Publication date: 1 February 2017

Published in: Communications in Mathematical Physics (Search for Journal in Brave)

Abstract: We prove that local random quantum circuits acting on n qubits composed of O(t^{10} n^2) many nearest neighbor two-qubit gates form an approximate unitary t-design. Previously it was unknown whether random quantum circuits were a t-design for any t > 3. The proof is based on an interplay of techniques from quantum many-body theory, representation theory, and the theory of Markov chains. In particular we employ a result of Nachtergaele for lower bounding the spectral gap of frustration-free quantum local Hamiltonians; a quasi-orthogonality property of permutation matrices; a result of Oliveira which extends to the unitary group the path-coupling method for bounding the mixing time of random walks; and a result of Bourgain and Gamburd showing that dense subgroups of the special unitary group, composed of elements with algebraic entries, are infty-copy tensor-product expanders. We also consider pseudo-randomness properties of local random quantum circuits of small depth and prove that circuits of depth O(t^{10}n) constitute a quantum t-copy tensor-product expander. The proof also rests on techniques from quantum many-body theory, in particular on the detectability lemma of Aharonov, Arad, Landau, and Vazirani. We give applications of the results to cryptography, equilibration of closed quantum dynamics, and the generation of topological order. In particular we show the following pseudo-randomness property of generic quantum circuits: Almost every circuit U of size O(n^k) on n qubits cannot be distinguished from a Haar uniform unitary by circuits of size O(n^{(k-9)/11}) that are given oracle access to U.

Full work available at URL: https://arxiv.org/abs/1208.0692

Recommendations

• Local random quantum circuits are approximate polynomial-designs: numerical results
• Random quantum circuits are approximate 2-designs
• Efficient unitary designs with a system-size independent number of non-Clifford gates
• (Pseudo) random quantum states with binary phase
• Comment on ``Random quantum circuits are approximate 2-designs by A.W. Harrow and R.A. Low (Commun. Math. Phys. 291, 257-302 (2009))

zbMATH Keywords

Haar measureapproximate unitary t-designquantum randomnessrandom unitaries

Mathematics Subject Classification ID

Random matrices (probabilistic aspects) (60B20) Cryptography (94A60) Quantum computation (81P68) Quantum coherence, entanglement, quantum correlations (81P40) Quantum information, communication, networks (quantum-theoretic aspects) (81P45) Design techniques (robust design, computer-aided design, etc.) (93B51) Analytic circuit theory (94C05) Set functions and measures on topological groups or semigroups, Haar measures, invariant measures (28C10) Quantum cryptography (quantum-theoretic aspects) (81P94)

Cites Work

• Title not available (Why is that?)
• The concentration of measure phenomenon
• Title not available (Why is that?)
• Asymptotic theory of finite dimensional normed spaces. With an appendix by M. Gromov: Isoperimetric inequalities in Riemannian manifolds
• Fault-tolerant quantum computation by anyons
• Title not available (Why is that?)
• Computational complexity and black hole horizons
• Towards the fast scrambling conjecture
• Aspects of generic entanglement
• Finitely correlated states on quantum spin chains
• The spectral gap for some spin chains with discrete symmetry breaking
• On the convergence to equilibrium of Kac's random walk on matrices
• An introduction to the mathematics of Anderson localization
• Derandomized constructions of \(k\)-wise (almost) independent permutations
• A spectral gap theorem in SU\((d)\)
• Quantum complexity theory
• Random quantum circuits are approximate 2-designs
• Randomizing quantum states: constructions and applications
• Non-abelian anyons and topological quantum computation
• The mother of all protocols: restructuring quantum information's family tree
• Matrix product state representations
• A quantum central limit theorem for non-equilibrium systems: exact local relaxation of correlated states
• Quantum logarithmic Sobolev inequalities and rapid mixing
• Linear trimmed means for the linear regression with AR(1) errors model
• Evenly distributed unitaries: On the structure of unitary designs
• Large deviation bounds for \(k\)-designs
• Title not available (Why is that?)
• Pseudo-random unitary operators for quantum information processing
• Cryptography in the Bounded-Quantum-Storage Model
• Feller processes on nonlocally compact spaces
• Unitary designs and codes
• Simple permutations mix well
• Simple permutations mix even better
• Superpolynomial Speedups Based on Almost Any Quantum Circuit
• Classical and quantum tensor product expanders
• Efficient Quantum Tensor Product Expanders and k-Designs
• Nonmalleable encryption of quantum information
• Symmetric groups and expanders
• Thermalization under randomized local Hamiltonians
• The emergence of typical entanglement in two-party random processes
• Comment on ``Random quantum circuits are approximate 2-designs by A.W. Harrow and R.A. Low (Commun. Math. Phys. 291, 257-302 (2009))
• Subsystem dynamics under random Hamiltonian evolution

Cited In (42)

• Approximate Unitary n^2/3-Designs Give Rise to Quantum Channels with Super Additive Classical Holevo Capacity
• Mixing properties of stochastic quantum Hamiltonians
• On the explicit constructions of certain unitaryt-designs
• Chaos in quantum channels
• Chaos and complexity by design
• Linear growth of circuit complexity from Brownian dynamics
• Rescuing complementarity with little drama
• Chaos, complexity, and random matrices
• Spectral decoupling in many-body quantum chaos
• Mixing and localization in random time-periodic quantum circuits of Clifford unitaries
• Local random quantum circuits: Ensemble completely positive maps and swap algebras
• Explicit construction of exact unitary designs
• Approximate orthogonality of permutation operators, with application to quantum information
• Entanglement, quantum randomness, and complexity beyond scrambling
• Efficient simulation of random states and random unitaries
• Random quantum circuits are approximate 2-designs
• Decoupling with random quantum circuits
• Random quantum circuits transform local noise into global white noise
• Pseudorandom isometries
• On barren plateaus and cost function locality in variational quantum algorithms
• A random unitary circuit model for black hole evaporation
• Tensor networks for black hole interiors: non-isometries, quantum extremal surfaces, and wormholes
• Approximate unitary \(t\)-designs by short random quantum circuits using nearest-neighbor and long-range gates
• Correlation length in random MPS and PEPS
• Certified randomness from quantum supremacy
• Efficient unitary designs with a system-size independent number of non-Clifford gates
• An efficient superpostional quantum Johnson-Lindenstrauss lemma via unitary \(t\)-designs
• Small violations of Bell inequalities for multipartite pure random states
• Thermalization and canonical typicality in translation-invariant quantum lattice systems
• Analysing quantum systems with randomised measurements
• Complete entropic inequalities for quantum Markov chains
• Complexity theory. Abstracts from the workshop held June 2--7, 2024
• Propagation of correlations in local random quantum circuits
• Comment on ``Random quantum circuits are approximate 2-designs by A.W. Harrow and R.A. Low (Commun. Math. Phys. 291, 257-302 (2009))
• Pseudorandom (function-Like) quantum state generators: new definitions and applications
• Erratum to: Onset of random matrix behavior in scrambling systems
• Can the macroscopic fluctuation theory be quantized?
• Complexity growth in integrable and chaotic models
• Quantifying scrambling in quantum neural networks
• Quantum statistical mechanics of encryption: reaching the speed limit of classical block ciphers
• Thermalization in Kitaev’s quantum double models via tensor network techniques
• Large deviation bounds for \(k\)-designs

This page was built for publication: Local random quantum circuits are approximate polynomial-designs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q506483)