Random quantum circuits anti-concentrate in log depth

Abstract

We consider quantum circuits consisting of randomly chosen two-local gates and study the number of gates needed for the distribution over measurement outcomes for typical circuit instances to be anti-concentrated, roughly meaning that the probability mass is not too concentrated on a small number of measurement outcomes. Understanding the conditions for anti-concentration is important for determining which quantum circuits are difficult to simulate classically, as anti-concentration has been in some cases an ingredient of mathematical arguments that simulation is hard and in other cases a necessary condition for easy simulation. Our definition of anti-concentration is that the expected collision probability, that is, the probability that two independently drawn outcomes will agree, is only a constant factor larger than if the distribution were uniform. We show that when the 2-local gates are each drawn from the Haar measure (or any two-design), at least $\Omega (n\log (n))$ gates (and thus $\Omega (\log (n))$ circuit depth) are needed for this condition to be met on an $n$ qudit circuit. In both the case where the gates are nearest-neighbor on a 1D ring and the case where gates are long-range, we show $O(n\log (n))$ gates are also sufficient, and we precisely compute the optimal constant prefactor for the $n\log (n)$. The technique we employ relies upon a mapping from the expected collision probability to the partition function of an Ising-like classical statistical mechanical model, which we manage to bound using stochastic and combinatorial techniques.

arXiv comment46 pages, 7 figures. v2: Reformatted, fixed typos, added figure 3

References in corpus (34)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Black holes as mirrors: quantum information in random subsystems
• Characterizing Quantum Supremacy in Near-Term Devices
• Operator Spreading in Random Unitary Circuits
• Quantum Entanglement Growth Under Random Unitary Dynamics
• Operator hydrodynamics, OTOCs, and entanglement growth in systems without conservation laws
• Theory of the phase transition in random unitary circuits with measurements
• Measurement-induced criticality in random quantum circuits
• Holographic duality from random tensor networks
• Random Quantum Circuits are Approximate 2-designs
• Local random quantum circuits are approximate polynomial-designs
• Average-case complexity versus approximate simulation of commuting quantum computations
• Quantum Supremacy and the Complexity of Random Circuit Sampling
• Emergent statistical mechanics of entanglement in random unitary circuits
• Achieving quantum supremacy with sparse and noisy commuting quantum computations
• Onset of Random Matrix Behavior in Scrambling Systems
• Efficient classical simulation of random shallow 2D quantum circuits
• Approximate unitary $t$-designs by short random quantum circuits using nearest-neighbor and long-range gates
• Efficient Generation of Generic Entanglement
• Decoupling with random quantum circuits
• Convergence rates for arbitrary statistical moments of random quantum circuits
• Mean-field entanglement transitions in random tree tensor networks
• How many qubits are needed for quantum computational supremacy?
• Emergence of typical entanglement in two-party random processes
• Unitary designs from statistical mechanics in random quantum circuits
• Anticoncentration theorems for schemes showing a quantum speedup
• Mixing properties of stochastic quantum Hamiltonians
• Scrambling speed of random quantum circuits
• Hardness of classically sampling one clean qubit model with constant total variation distance error
• Closing gaps of a quantum advantage with short-time Hamiltonian dynamics
• Efficient classical simulation of noisy quantum computation
• Operator growth in random quantum circuits with symmetry
• Efficient unitary paths and quantum computational supremacy: A proof of average-case hardness of Random Circuit Sampling
• Additive-error fine-grained quantum supremacy

Cited by in corpus (8)

• Computational advantage of quantum random sampling
• A polynomial-time classical algorithm for noisy random circuit sampling
• Shallow shadows: Expectation estimation using low-depth random Clifford circuits
• Tight bounds on the convergence of noisy random circuits to the uniform distribution
• Noise and the frontier of quantum supremacy
• Volumetric Benchmarking of Error Mitigation with Qermit
• Generalized Cross-Entropy Benchmarking for Random Circuits with Ergodicity
• Basis dependence of Neural Quantum States for the Transverse Field Ising Model