Approximate unitary $t$-designs by short random quantum circuits using nearest-neighbor and long-range gates

Abstract

We prove that $poly(t)\cdot 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. These include the "monomial" measure, meaning that the monomials of a random circuit from this family have expectation close to the value that would result from the Haar measure. Previously, the best bound was $poly(t)\cdot n$ due to Brandao-Harrow-Horodecki (BHH) for $D=1$. We also improve the "scrambling" and "decoupling" bounds for spatially local random circuits due to Brown and Fawzi. One consequence of our result is that assuming the polynomial hierarchy (PH) is infinite and that certain counting problems are $\#P$-hard on average, sampling within total variation distance from these circuits is hard for classical computers. Previously, exact sampling from the outputs of even constant-depth quantum circuits was known to be hard for classical computers under the assumption that PH is infinite. However, to show the hardness of approximate sampling using this strategy requires that the quantum circuits have a property called "anti-concentration", meaning roughly that the output has near-maximal entropy. Unitary 2-designs have the desired anti-concentration property. Thus our result improves the required depth for this level of anti-concentration from linear depth to a sub-linear value, depending on the geometry of the interactions. This is relevant to a recent proposal by the Google Quantum AI group to perform such a sampling task with 49 qubits on a two-dimensional lattice and confirms their conjecture that $O(\sqrt{n})$ depth suffices for anti-concentration. We also prove that anti-concentration is possible in depth O(log(n) loglog(n)) using a different model.

arXiv commentThis is the second version with minor updates on the previous article

References in corpus (32)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Barren plateaus in quantum neural network training landscapes
• Logic gates at the surface code threshold: Superconducting qubits poised for fault-tolerant quantum computing
• Characterizing Quantum Supremacy in Near-Term Devices
• Cost Function Dependent Barren Plateaus in Shallow Parametrized Quantum Circuits
• Quantum Computational Supremacy
• Demonstration of a small programmable quantum computer with atomic qubits
• Exact and Approximate Unitary 2-Designs: Constructions and Applications
• Integration with respect to the Haar measure on unitary, orthogonal and symplectic group
• Quantum advantage with shallow circuits
• Random Quantum Circuits are Approximate 2-designs
• Local random quantum circuits are approximate polynomial-designs
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Average-case complexity versus approximate simulation of commuting quantum computations
• Quantum Supremacy and the Complexity of Random Circuit Sampling
• Achieving quantum supremacy with sparse and noisy commuting quantum computations
• Quantum Supremacy through the Quantum Approximate Optimization Algorithm
• Quantum computing and the entanglement frontier
• Fault-tolerant quantum computation with few qubits
• Efficient Generation of Generic Entanglement
• Decoupling with random quantum circuits
• Convergence rates for arbitrary statistical moments of random quantum circuits
• Exact convergence times for generation of random bipartite entanglement
• The Church of the Symmetric Subspace
• Anticoncentration theorems for schemes showing a quantum speedup
• Scrambling speed of random quantum circuits
• Unitary $2$-designs from random $X$- and $Z$-diagonal unitaries
• Comment on the paper "Random Quantum Circuits are Approximate 2-designs"
• Demonstrating Quantum Error Correction that Extends the Lifetime of Quantum Information
• Fourier analysis of sampling from noisy chaotic quantum circuits
• Can Chaotic Quantum Circuits Maintain Quantum Supremacy under Noise?
• The Computational Complexity of Ball Permutations

Cited by in corpus (86)

• Cost Function Dependent Barren Plateaus in Shallow Parametrized Quantum Circuits
• Quantum Computational Supremacy
• Connecting ansatz expressibility to gradient magnitudes and barren plateaus
• Diagnosing Barren Plateaus with Tools from Quantum Optimal Control
• A flexible high-performance simulator for verifying and benchmarking quantum circuits implemented on real hardware
• Efficient classical simulation of random shallow 2D quantum circuits
• Computational advantage of quantum random sampling
• Introduction to Haar Measure Tools in Quantum Information: A Beginner's Tutorial
• Models of quantum complexity growth
• Random quantum circuits anti-concentrate in log depth
• Quantum Simulation of the Sachdev-Ye-Kitaev Model by Asymmetric Qubitization
• On the practical usefulness of the Hardware Efficient Ansatz
• Unitary designs from statistical mechanics in random quantum circuits
• Generative quantum machine learning via denoising diffusion probabilistic models
• Fermion Sampling: a robust quantum computational advantage scheme using fermionic linear optics and magic input states
• Classical shadows with Pauli-invariant unitary ensembles
• Noise and the frontier of quantum supremacy
• Random Matrix Theory of the Isospectral twirling
• Improved spectral gaps for random quantum circuits: large local dimensions and all-to-all interactions
• Spectral decoupling in many-body quantum chaos
• Guaranteed recovery of quantum processes from few measurements
• Entanglement entropy production in Quantum Neural Networks
• Entangled Datasets for Quantum Machine Learning
• Engineered dissipation to mitigate barren plateaus
• Correlation length in random MPS and PEPS
• Quantum supremacy and random circuits
• Classically estimating observables of noiseless quantum circuits
• Isometric tensor network optimization for extensive Hamiltonians is free of barren plateaus
• Designs via Free Probability
• Quantum neural networks form Gaussian processes
• Computing exact moments of local random quantum circuits via tensor networks
• Fluctuations of subsystem entropies at late times
• Randomized Benchmarking in the Analogue Setting
• Benchmarking quantum gates and circuits
• High-dimensional entanglement witnessed by correlations in arbitrary bases
• Efficient unitary designs and pseudorandom unitaries from permutations
• Efficient Unitary T-designs from Random Sums
• Efficient unitary paths and quantum computational supremacy: A proof of average-case hardness of Random Circuit Sampling
• Entanglement asymmetry dynamics in random quantum circuits
• Constrained and Vanishing Expressivity of Quantum Fourier Models
• Mixing and localisation in random time-periodic quantum circuits of Clifford unitaries
• Unitary k-designs from random number-conserving quantum circuits
• Designs from Local Random Quantum Circuits with SU(d) Symmetry
• Absence of localization in two-dimensional Clifford circuits
• Barren plateaus are swamped with traps
• On the generic increase of observational entropy in isolated systems
• Operational Quantum Average-Case Distances
• Absence of barren plateaus and scaling of gradients in the energy optimization of isometric tensor network states
• Linear Cross Entropy Benchmarking with Clifford Circuits
• Approximate Unitary $k$-Designs from Shallow, Low-Communication Circuits
• Holographic deep thermalization for secure and efficient quantum random state generation
• Saturation and recurrence of quantum complexity in random local quantum dynamics
• Optimal Conversion from Classical to Quantum Randomness via Quantum Chaos
• Analyzing the quantum approximate optimization algorithm: ansätze, symmetries, and Lie algebras
• Efficient Construction of Quantum Physical Unclonable Functions with Unitary t-designs
• Maximising Quantum-Computing Expressive Power through Randomised Circuits
• Bounds on the ground state energy of quantum $p$-spin Hamiltonians
• A Hierarchy for Replica Quantum Advantage
• Projected ensemble in a system with conserved charges with local support
• Unitary $t$-designs from $relaxed$ seeds
• Phase transitions in sampling and error correction in local Brownian circuits
• Fast pseudorandom quantum state generators via inflationary quantum gates
• The Quantum Supremacy Tsirelson Inequality
• Non-Haar random circuits form unitary designs as fast as Haar random circuits
• Non-Clifford Cost of Random Unitaries
• Approximate inverse measurement channel for shallow shadows
• Entanglement dynamics and Page curves in random permutation circuits
• Exact spectral gaps of random one-dimensional quantum circuits
• Randomized measurements for multi-parameter quantum metrology
• Architectures and random properties of symplectic quantum circuits
• Quantum Local Differential Privacy and Quantum Statistical Query Model
• On Computational Complexity of Unitary and State Design Properties
• Benchmarking the performance of a high-Q cavity qudit using random unitaries
• Pseudochaotic Many-Body Dynamics as a Pseudorandom State Generator
• Revealing quantum operator scrambling via measuring Holevo information on digital quantum simulators
• Generalized Cross-Entropy Benchmarking for Random Circuits with Ergodicity
• Sampling and the complexity of nature
• Experimental measurement and a physical interpretation of quantum shadow enumerators
• Circuit complexity and functionality: a thermodynamic perspective
• Anticoncentration is (almost) all you need
• Moments of Quantum Channel Ensembles
• Optimal quantum (tensor product) expanders from unitary designs
• More global randomness from less-random local gates
• Sample Optimal and Memory Efficient Quantum State Tomography
• Quantum Private Broadcasting
• Shallow quantum circuit for generating extremely low-entangled approximate state designs