Tight bounds on the convergence of noisy random circuits to the uniform distribution

Abstract

We study the properties of output distributions of noisy, random circuits. We obtain upper and lower bounds on the expected distance of the output distribution from the "useless" uniform distribution. These bounds are tight with respect to the dependence on circuit depth. Our proof techniques also allow us to make statements about the presence or absence of anticoncentration for both noisy and noiseless circuits. We uncover a number of interesting consequences for hardness proofs of sampling schemes that aim to show a quantum computational advantage over classical computation. Specifically, we discuss recent barrier results for depth-agnostic and/or noise-agnostic proof techniques. We show that in certain depth regimes, noise-agnostic proof techniques might still work in order to prove an often-conjectured claim in the literature on quantum computational advantage, contrary to what was thought prior to this work.

21 pages, 1 figure; v2: 19 pages, 1 figure; v3: 23 pages, 1 figure

References in corpus (9)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Quantum computational advantage using photons
• Strong quantum computational advantage using a superconducting quantum processor
• Noise-Induced Barren Plateaus in Variational Quantum Algorithms
• Phase-Programmable Gaussian Boson Sampling Using Stimulated Squeezed Light
• Linear growth of quantum circuit complexity
• Random quantum circuits anti-concentrate in log depth
• Entanglement dynamics in hybrid quantum circuits
• Noise and the frontier of quantum supremacy

Cited by in corpus (30)

• Computational advantage of quantum random sampling
• A comprehensive review of Quantum Machine Learning: from NISQ to Fault Tolerance
• Cross Entropy Benchmark for Measurement-Induced Phase Transitions
• Solvable model of deep thermalization with distinct design times
• Classical algorithm for simulating experimental Gaussian boson sampling
• Simulating Noisy Variational Quantum Algorithms: A Polynomial Approach
• Error-mitigated fermionic classical shadows on noisy quantum devices
• Exponentially tighter bounds on limitations of quantum error mitigation
• Efficient sampling of noisy shallow circuits via monitored unraveling
• Fock-space delocalization and the emergence of the Porter-Thomas distribution from dual-unitary dynamics
• Dynamic-ADAPT-QAOA: An algorithm with shallow and noise-resilient circuits
• Analog information decoding of bosonic quantum LDPC codes
• Unitary k-designs from random number-conserving quantum circuits
• Unveiling quantum phase transitions from traps in variational quantum algorithms
• Approximate Unitary $k$-Designs from Shallow, Low-Communication Circuits
• Exploring Shallow-Depth Boson Sampling: Towards Scalable Quantum Supremacy
• Fault-tolerant compiling of classically hard IQP circuits on hypercubes
• Symmetric Clifford twirling for cost-optimal quantum error mitigation in early FTQC regime
• Scalability Challenges in Variational Quantum Optimization under Stochastic Noise
• The Second Moment of Hafnians in Gaussian Boson Sampling
• Noisy Quantum Trees: Infinite Protection Without Correction
• Q-fid: Quantum Circuit Fidelity Improvement with LSTM Networks
• Scalable projected entangled-pair state representation of random quantum circuit states
• Error Mitigation Thresholds in Noisy Random Quantum Circuits
• Robustness of optimized numerical estimation schemes for noisy variational quantum algorithms
• Integrals of motion as slow modes in dissipative many-body operator dynamics
• Effective dynamics of qubit networks via phase-covariant quantum ensembles
• Classical simulation of noisy quantum circuits via locally entanglement-optimal unravelings
• More global randomness from less-random local gates
• Sampling (noisy) quantum circuits through randomized rounding