Improved spectral gaps for random quantum circuits: large local dimensions and all-to-all interactions

Abstract

Random quantum circuits are a central concept in quantum information theory with applications ranging from demonstrations of quantum computational advantage to descriptions of scrambling in strongly-interacting systems and black holes. The utility of random quantum circuits in these settings stems from their ability to rapidly generate quantum pseudo-randomness. In a seminal paper by Brandão, Harrow, and Horodecki, it was proven that the $t$-th moment operator of local random quantum circuits on $n$ qudits with local dimension $q$ has a spectral gap of at least $\Omega (n^{-1}{t}^{-5-3.1/\log (q)})$, which implies that they are efficient constructions of approximate unitary designs. As a first result, we use Knabe bounds for the spectral gaps of frustration-free Hamiltonians to show that $1D$ random quantum circuits have a spectral gap scaling as $\Omega (n^{-1})$, provided that $t$ is small compared to the local dimension: $t^2\le O(q)$. This implies a (nearly) linear scaling of the circuit depth in the design order $t$. Our second result is an unconditional spectral gap bounded below by $\Omega (n^{-1}{\log }^{-1}(n)t^{-\alpha (q)})$ for random quantum circuits with all-to-all interactions. This improves both the $n$ and $t$ scaling in design depth for the non-local model. We show this by proving a recursion relation for the spectral gaps involving an auxiliary random walk. Lastly, we solve the smallest non-trivial case exactly and combine with numerics and Knabe bounds to improve the constants involved in the spectral gap for small values of $t$.

arXiv comment27 pages, 2 figures

References in corpus (31)

• Exact and Approximate Unitary 2-Designs: Constructions and Applications
• Integration with respect to the Haar measure on unitary, orthogonal and symplectic group
• Evenly distributed unitaries: on the structure of unitary designs
• Random Quantum Circuits are Approximate 2-designs
• Local random quantum circuits are approximate polynomial-designs
• The Second Law of Quantum Complexity
• The mother of all protocols: Restructuring quantum information's family tree
• Approximate unitary $t$-designs by short random quantum circuits using nearest-neighbor and long-range gates
• Efficient Generation of Generic Entanglement
• Models of quantum complexity growth
• The spectral gap for some spin chains with discrete symmetry breaking
• Convergence Conditions for Random Quantum Circuits
• Convergence rates for arbitrary statistical moments of random quantum circuits
• On some properties of orthogonal Weingarten functions
• Efficient unitary designs with nearly time-independent Hamiltonian dynamics
• Exact convergence times for generation of random bipartite entanglement
• Unitary designs from statistical mechanics in random quantum circuits
• Large Deviation Bounds for k-designs
• Local gap threshold for frustration-free spin systems
• Entanglement, quantum randomness, and complexity beyond scrambling
• Mixing properties of stochastic quantum Hamiltonians
• Real Randomized Benchmarking
• Spectral gaps of frustration-free spin systems with boundary
• Closing gaps of a quantum advantage with short-time Hamiltonian dynamics
• Efficient Quantum Tensor Product Expanders and k-designs
• A simple proof of the detectability lemma and spectral gap amplification
• On the convergence to equilibrium of Kac's random walk on matrices
• Operator growth in random quantum circuits with symmetry
• Local random quantum circuits are approximate polynomial-designs - numerical results
• Fluctuations of subsystem entropies at late times
• Black Holes and Complexity Classes

Cited by in corpus (25)

• Linear growth of quantum circuit complexity
• Random quantum circuits are approximate unitary $t$-designs in depth $O\left(n{t}^{5+o(1)}\right)$
• Projected Least-Squares Quantum Process Tomography
• Entanglement entropy production in Quantum Neural Networks
• Efficient unitary designs and pseudorandom unitaries from permutations
• Efficient Unitary T-designs from Random Sums
• Designs from Local Random Quantum Circuits with SU(d) Symmetry
• Purity decay rate in random circuits with different configurations of gates
• Exploring Quantum Average-Case Distances: proofs, properties, and examples
• Complexity is not Enough for Randomness
• Complexity-constrained quantum thermodynamics
• Operational Quantum Average-Case Distances
• Quantitatively improved finite-size criteria for spectral gaps
• Approximate Unitary $k$-Designs from Shallow, Low-Communication Circuits
• Saturation and recurrence of quantum complexity in random local quantum dynamics
• Analyzing the quantum approximate optimization algorithm: ansätze, symmetries, and Lie algebras
• Designs from magic-augmented Clifford circuits
• Efficient approximate unitary designs from random Pauli rotations
• Non-Haar random circuits form unitary designs as fast as Haar random circuits
• On the average-case complexity of learning output distributions of quantum circuits
• Learning Quantum Processes with Quantum Statistical Queries
• Exact spectral gaps of random one-dimensional quantum circuits
• A Hierarchy of Spectral Gap Certificates for Frustration-Free Spin Systems
• Moments of Quantum Channel Ensembles
• Anticoncentration is (almost) all you need