NOTICE: Due to a lapse in annual appropriations, most of this website is not being updated. Learn more.
Form submissions will still be accepted but will not receive responses at this time. Sections of this site for programs using non-appropriated funds (such as NVLAP) or those that are excepted from the shutdown (such as CHIPS and NVD) will continue to be updated.
An official website of the United States government
Here’s how you know
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
Secure .gov websites use HTTPS
A lock (
) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.
Tight Bounds on the Convergence of Noisy Random Circuits to the Uniform Distribution
Published
Author(s)
Michael Gullans, Abhinav Deshpande, Bill Fefferman, Alexey Gorshkov, Pradeep Niroula, Oles Shtanko
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 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.
Gullans, M.
, Deshpande, A.
, Fefferman, B.
, Gorshkov, A.
, Niroula, P.
and Shtanko, O.
(2022),
Tight Bounds on the Convergence of Noisy Random Circuits to the Uniform Distribution, PRX Quantum, [online], https://doi.org/10.1103/PRXQuantum.3.040329, https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=933913
(Accessed October 8, 2025)