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.

This is the second version with minor updates on the previous article

References in corpus (10)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Cost Function Dependent Barren Plateaus in Shallow Parametrized Quantum Circuits
• Quantum Computational Supremacy
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Quantum computing and the entanglement frontier
• Exact convergence times for generation of random bipartite entanglement
• Comment on the paper "Random Quantum Circuits are Approximate 2-designs"
• 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 (84)

• 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
• 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
• Noise and the frontier of quantum supremacy
• Classical shadows with Pauli-invariant unitary ensembles
• 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
• Entanglement entropy production in Quantum Neural Networks
• Entangled Datasets for Quantum Machine Learning
• Engineered dissipation to mitigate barren plateaus
• Quantum supremacy and random circuits
• Correlation length in random MPS and PEPS
• Classically estimating observables of noiseless quantum circuits
• Isometric tensor network optimization for extensive Hamiltonians is free of barren plateaus
• Computing exact moments of local random quantum circuits via tensor networks
• Quantum neural networks form Gaussian processes
• Designs via Free Probability
• Fluctuations of subsystem entropies at late times
• Randomized Benchmarking in the Analogue Setting
• High-dimensional entanglement witnessed by correlations in arbitrary bases
• Entanglement asymmetry dynamics in random quantum circuits
• Benchmarking quantum gates and circuits
• 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
• Constrained and Vanishing Expressivity of Quantum Fourier Models
• Mixing and localisation in random time-periodic quantum circuits of Clifford unitaries
• Designs from Local Random Quantum Circuits with SU(d) Symmetry
• Absence of localization in two-dimensional Clifford circuits
• Unitary k-designs from random number-conserving quantum circuits
• On the generic increase of observational entropy in isolated systems
• Barren plateaus are swamped with traps
• Operational Quantum Average-Case Distances
• Linear Cross Entropy Benchmarking with Clifford Circuits
• Approximate Unitary $k$-Designs from Shallow, Low-Communication Circuits
• Absence of barren plateaus and scaling of gradients in the energy optimization of isometric tensor network states
• Saturation and recurrence of quantum complexity in random local quantum dynamics
• Analyzing the quantum approximate optimization algorithm: ansätze, symmetries, and Lie algebras
• Optimal Conversion from Classical to Quantum Randomness via Quantum Chaos
• Holographic deep thermalization for secure and efficient quantum random state generation
• Efficient Construction of Quantum Physical Unclonable Functions with Unitary t-designs
• Bounds on the ground state energy of quantum $p$-spin Hamiltonians
• Maximising Quantum-Computing Expressive Power through Randomised Circuits
• A Hierarchy for Replica Quantum Advantage
• Phase transitions in sampling and error correction in local Brownian circuits
• Unitary $t$-designs from $relaxed$ seeds
• Projected ensemble in a system with conserved charges with local support
• Fast pseudorandom quantum state generators via inflationary quantum gates
• The Quantum Supremacy Tsirelson Inequality
• Non-Clifford Cost of Random Unitaries
• Approximate inverse measurement channel for shallow shadows
• Non-Haar random circuits form unitary designs as fast as Haar random circuits
• Randomized measurements for multi-parameter quantum metrology
• Quantum Local Differential Privacy and Quantum Statistical Query Model
• Architectures and random properties of symplectic quantum circuits
• Exact spectral gaps of random one-dimensional quantum circuits
• Entanglement dynamics and Page curves in random permutation circuits
• 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
• Experimental measurement and a physical interpretation of quantum shadow enumerators
• Generalized Cross-Entropy Benchmarking for Random Circuits with Ergodicity
• Circuit complexity and functionality: a thermodynamic perspective
• Sampling and the complexity of nature
• Revealing quantum operator scrambling via measuring Holevo information on digital quantum simulators
• Moments of Quantum Channel Ensembles
• More global randomness from less-random local gates
• Optimal quantum (tensor product) expanders from unitary designs
• Quantum Private Broadcasting
• Sample Optimal and Memory Efficient Quantum State Tomography
• Shallow quantum circuit for generating extremely low-entangled approximate state designs
• Anticoncentration is (almost) all you need