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