A Caltech Library Service

Tight Bounds on the Convergence of Noisy Random Circuits to the Uniform Distribution

Deshpande, Abhinav and Niroula, Pradeep and Shtanko, Oles and Gorshkov, Alexey V. and Fefferman, Bill and Gullans, Michael J. (2022) Tight Bounds on the Convergence of Noisy Random Circuits to the Uniform Distribution. PRX Quantum, 3 (4). ISSN 2691-3399. doi:10.1103/prxquantum.3.040329.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


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 has been thought prior to this work.

Item Type:Article
Related URLs:
URLURL TypeDescription
Deshpande, Abhinav0000-0002-6114-1830
Niroula, Pradeep0000-0001-8941-7774
Gorshkov, Alexey V.0000-0003-0509-3421
Fefferman, Bill0000-0002-9627-0210
Gullans, Michael J.0000-0003-3974-2987
Additional Information:We thank Alex Dalzell for helpful and inspiring discussions. We thank Igor Boettcher, Dominik Hangleiter, and Grace Sommers for helpful comments on the manuscript. M.J.G., A.V.G., and P.N. acknowledge support from the National Science Foundation (NSF) Quantum Leap Challenge Institutes (QLCI) (Grant No. OMA-2120757). A.D., A.V.G., P.N., and O.S. were supported in part by the U.S. Department of Energy (DOE) Quantum Systems Accelerator (QSA), the DOE Advanced Scientific Computing Research (ASCR) Accelerated Research in Quantum Computing program (Award No. DE-SC0020312), the DOE ASCR Quantum Testbed Pathfinder program (Award No. DE-SC0019040), the NSF Practical Fully-Connected Quantum Computer (PFCQC) program, the Air Force Office of Scientific Research (AFOSR), the DOE (Award No. DE-SC0019449), the Army Research Office (ARO) Multidisciplinary University Research Initiative (MURI), the AFOSR MURI, and the Defense Advanced Research Projects Agency (DARPA) Science of Atomic Vapors for New Technologies (SAVaNT) ADVENT. A.D. also acknowledges support from the NSF under Award No. 1839204 and the National Science Foundation under Grant No. NSF PHY-1748958. B.F. acknowledges support from the AFOSR (Grants No. YIP FA9550-18-1-0148 and FA9550-21-1-0008). This material is based upon work partially support from the NSF under Award CAREER and by the DOE, Office of Science, National Quantum Information Science Research Centers. The Institute for Quantum Information and Matter is an NSF Physics Frontiers Center (PHY-1733907).
Group:Institute for Quantum Information and Matter
Funding AgencyGrant Number
Department of Energy (DOE)DE-SC0020312
Department of Energy (DOE)DE-SC0019040
Department of Energy (DOE)DE-SC0019449
Army Research Office (ARO)UNSPECIFIED
Defense Advanced Research Projects Agency (DARPA)UNSPECIFIED
Air Force Office of Scientific Research (AFOSR)FA9550-18-1-0148
Air Force Office of Scientific Research (AFOSR)FA9550-21-1-0008
Issue or Number:4
Record Number:CaltechAUTHORS:20230117-369491100.13
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:118819
Deposited By: Research Services Depository
Deposited On:10 Feb 2023 20:09
Last Modified:10 Feb 2023 20:09

Repository Staff Only: item control page