Local random quantum circuits are approximate polynomial-designs
From MaRDI portal
(Redirected from Publication:506483)
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)
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.
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))
Cites work
- scientific article; zbMATH DE number 1160038 (Why is no real title available?)
- scientific article; zbMATH DE number 1775384 (Why is no real title available?)
- scientific article; zbMATH DE number 1776257 (Why is no real title available?)
- scientific article; zbMATH DE number 967931 (Why is no real title available?)
- A quantum central limit theorem for non-equilibrium systems: exact local relaxation of correlated states
- A spectral gap theorem in SU(d)
- An introduction to the mathematics of Anderson localization
- Aspects of generic entanglement
- Asymptotic theory of finite dimensional normed spaces. With an appendix by M. Gromov: Isoperimetric inequalities in Riemannian manifolds
- Classical and quantum tensor product expanders
- Comment on ``Random quantum circuits are approximate 2-designs by A.W. Harrow and R.A. Low (Commun. Math. Phys. 291, 257-302 (2009))
- Computational complexity and black hole horizons
- Cryptography in the Bounded-Quantum-Storage Model
- Derandomized constructions of \(k\)-wise (almost) independent permutations
- Efficient Quantum Tensor Product Expanders and k-Designs
- Evenly distributed unitaries: On the structure of unitary designs
- Fault-tolerant quantum computation by anyons
- Feller processes on nonlocally compact spaces
- Finitely correlated states on quantum spin chains
- Large deviation bounds for \(k\)-designs
- Linear trimmed means for the linear regression with AR(1) errors model
- Matrix product state representations
- Non-abelian anyons and topological quantum computation
- Nonmalleable encryption of quantum information
- On the convergence to equilibrium of Kac's random walk on matrices
- Pseudo-random unitary operators for quantum information processing
- Quantum complexity theory
- Quantum logarithmic Sobolev inequalities and rapid mixing
- Random quantum circuits are approximate 2-designs
- Randomizing quantum states: constructions and applications
- Simple permutations mix even better
- Simple permutations mix well
- Subsystem dynamics under random Hamiltonian evolution
- Superpolynomial Speedups Based on Almost Any Quantum Circuit
- Symmetric groups and expanders
- The concentration of measure phenomenon
- The emergence of typical entanglement in two-party random processes
- The mother of all protocols: restructuring quantum information's family tree
- The spectral gap for some spin chains with discrete symmetry breaking
- Thermalization under randomized local Hamiltonians
- Towards the fast scrambling conjecture
- Unitary designs and codes
Cited in
(45)- Thermalization in Kitaev’s quantum double models via tensor network techniques
- Large deviation bounds for \(k\)-designs
- Approximate Unitary n^2/3-Designs Give Rise to Quantum Channels with Super Additive Classical Holevo Capacity
- (Pseudo) random quantum states with binary phase
- Mixing properties of stochastic quantum Hamiltonians
- Local random quantum circuits are approximate polynomial-designs: numerical results
- Local random quantum circuits: ensemble completely positive maps and swap algebras
- On the explicit constructions of certain unitaryt-designs
- Chaos in quantum channels
- Chaos and complexity by design
- Rescuing complementarity with little drama
- Chaos, complexity, and random matrices
- Linear growth of circuit complexity from Brownian dynamics
- Spectral decoupling in many-body quantum chaos
- Mixing and localization in random time-periodic quantum circuits of Clifford unitaries
- Explicit construction of exact unitary designs
- Entanglement, quantum randomness, and complexity beyond scrambling
- Random quantum circuits are approximate 2-designs
- Efficient simulation of random states and random unitaries
- Approximate orthogonality of permutation operators, with application to quantum information
- Decoupling with random quantum circuits
- Diagonal-unitary 2-design and their implementations by quantum circuits
- Random quantum circuits transform local noise into global white noise
- Pseudorandom isometries
- A random unitary circuit model for black hole evaporation
- Symmetry enriched phases of quantum circuits
- On barren plateaus and cost function locality in variational quantum algorithms
- 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
- Thermalization and canonical typicality in translation-invariant quantum lattice systems
- Small violations of Bell inequalities for multipartite pure random states
- Analysing quantum systems with randomised measurements
- Complete entropic inequalities for quantum Markov chains
- 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))
- Complexity theory. Abstracts from the workshop held June 2--7, 2024
- Pseudorandom (function-Like) quantum state generators: new definitions and applications
- 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
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)
