A Caltech Library Service

Random Quantum Circuits Anticoncentrate in Log Depth

Dalzell, Alexander M. and Hunter-Jones, Nicholas and Brandão, Fernando G. S. L. (2022) Random Quantum Circuits Anticoncentrate in Log Depth. PRX Quantum, 3 (1). Art. No. 010333. ISSN 2691-3399. doi:10.1103/PRXQuantum.3.010333.

[img] PDF - Published Version
Creative Commons Attribution.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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 anticoncentrated, roughly meaning that the probability mass is not too concentrated on a small number of measurement outcomes. An understanding of the conditions for anticoncentration is important for determining which quantum circuits are difficult to simulate classically, as anticoncentration 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 anticoncentration is that the expected collision probability of the distribution—that is, the probability that two independently drawn outcomes will agree—is only a constant factor larger than the collision probability for the uniform distribution. We show that when the two-local gates are each drawn from the Haar measure (or any 2-design), at least Ω(n log(n)) gates (and thus Ω(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 one-dimensional ring and the case where gates are long range, we show that 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.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Dalzell, Alexander M.0000-0002-3756-8500
Hunter-Jones, Nicholas0000-0001-8578-1958
Brandão, Fernando G. S. L.0000-0003-3866-9378
Alternate Title:Random quantum circuits anti-concentrate in log depth
Additional Information:© 2022 Published by the American Physical Society under the terms of the Creative Commons Attribution 4.0 International license. Further distribution of this work must maintain attribution to the author(s) and the published article’s title, journal citation, and DOI. Received 16 July 2021; accepted 4 January 2022; published 1 March 2022. We thank Hrant Gharibyan, Jonas Haferkamp, Aram Harrow, Richard Kueng, Saeed Mehraban, John Napp, Sepehr Nezami, and John Preskill for discussions and helpful comments on the draft. This work was done prior to A.D. joining the AWS Center for Quantum Computing. A.D. and F.B. acknowledge funding provided by the Institute for Quantum Information and Matter, a National Science Foundation (NSF) Physics Frontiers Center (NSF Grant No. PHY-1733907). This material is also based upon work supported by the NSF Graduate Research Fellowship under Grant No. DGE-1745301. N.H.J. would like to thank the Institute for Quantum Information and Matter at Caltech for its hospitality during the completion of part of this work. Research at Perimeter Institute is supported by the Government of Canada through the Department of Innovation, Science and Industry Canada and by the Province of Ontario through the Ministry of Colleges and Universities.
Group:AWS Center for Quantum Computing, Institute for Quantum Information and Matter
Funding AgencyGrant Number
Institute for Quantum Information and Matter (IQIM)UNSPECIFIED
NSF Graduate Research FellowshipDGE-1745301
Perimeter Institute for Theoretical PhysicsUNSPECIFIED
Department of Innovation, Science and Industry (Canada)UNSPECIFIED
Ontario Ministry of Colleges and UniversitiesUNSPECIFIED
Issue or Number:1
Record Number:CaltechAUTHORS:20210511-131126866
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:109084
Deposited By: Tony Diaz
Deposited On:11 May 2021 20:36
Last Modified:01 Jun 2023 23:28

Repository Staff Only: item control page