Approximate Unitary t-Designs by Short Random Quantum Circuits Using Nearest-Neighbor and Long-Range Gates
Explore this paper's citation graph
Summary
It is proved that poly ( t) · n 1 / D -depth local random quantum circuits with two qudit nearest-neighbor gates on a D -dimensional lattice with n qudits are approximate t -designs in various measures, and introduces the norm corresponding to anti-concentration.
- Type
- article
- Published
- 2018-09-18
- Cited by
- 181
- References
- 53
- Access
- Open access
- OpenAlex
- https://openalex.org/W2891685619
- Semantic Scholar
- https://api.semanticscholar.org/CorpusID:119485576
Keywords
Mathematics, Discrete mathematics, Electronic circuit, Quantum, Upper and lower bounds
References
- The Church of the Symmetric Subspace
- Representations and Invariants of the Classical Groups
- A Two-dimensional Growth Process
- Average-case complexity versus approximate simulation of commuting quantum computations
- Markov Chains and Mixing Times
- Scrambling speed of random quantum circuits
- Exact and approximate unitary 2-designs and their application to fidelity estimation
- Random Walk and the Theory of Brownian Motion
- The computational complexity of linear optics
- Random Measurement Bases, Quantum State Distinction and Applications to the Hidden Subgroup Problem
- Generic entanglement can be generated efficiently.
- Integration with Respect to the Haar Measure on Unitary, Orthogonal and Symplectic Group
- Comment on “Random Quantum Circuits are Approximate 2-designs” by A.W. Harrow and R.A. Low (Commun. Math. Phys. 291, 257–302 (2009))
- Convergence rates for arbitrary statistical moments of random quantum circuits.
- A Spectral Gap Theorem in SU(d)
- Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
- Random Quantum Circuits are Approximate 2-designs
- Computational complexity and black hole horizons
- Decoupling with Random Quantum Circuits
- Exact convergence times for generation of random bipartite entanglement
Cited by
- Separation of Out-Of-Time-Ordered Correlation and Entanglement
- Correlation Length in Random MPS and PEPS
- Models of Quantum Complexity Growth
- Adiabatic ground state preparation in an expanding lattice
- Expressibility of the alternating layered ansatz for quantum computation
- Trainability of Dissipative Perceptron-Based Quantum Neural Networks
- Entanglement formation in continuous-variable random quantum networks
- Time-periodic dynamics generates pseudo-random unitaries
- The Quantum Supremacy Tsirelson Inequality
- How Dynamical Quantum Memories Forget
- Quantum Coding with Low-Depth Random Circuits
- Fluctuations of subsystem entropies at late times
- Entanglement Induced Barren Plateaus
- One-shot quantum error correction of classical and quantum information
- Reaching the speed limit of classical block ciphers via quantum-like operator spreading
- Effect of barren plateaus on gradient-free optimization
- Random Quantum Circuits Anticoncentrate in Log Depth
- On barren plateaus and cost function locality in variational quantum algorithms
- Improved spectral gaps for random quantum circuits: Large local dimensions and all-to-all interactions
- Fermion Sampling: A Robust Quantum Computational Advantage Scheme Using Fermionic Linear Optics and Magic Input States
Related papers
- Monomial bases and polynomial system solving (extended abstract)
- MONOMIAL CHARACTERS OVER FINITE GROUPS
- Detecting monomials with k distinct variables
- On super-monomial characters and groups having two irreducible monomial character degrees
- The monomial method and asymptotic properties of algebraic systems
- Level 0 Monomial Crystals
- Quasismooth hypersurfaces in toric varieties
- Monomial principalization in the singular setting