A Caltech Library Service

Random quantum circuits anti-concentrate in log depth

Dalzell, Alexander M. and Hunter-Jones, Nicholas and Brandão, Fernando G. S. L. (2020) Random quantum circuits anti-concentrate in log depth. . (Unpublished)

[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 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 Ω(nlog(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 1D ring and the case where gates are long-range, we show O(nlog(n)) gates are also sufficient, and we precisely compute the optimal constant prefactor for the nlog(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:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Brandão, Fernando G. S. L.0000-0003-3866-9378
Additional Information:We thank Hrant Gharibyan, Jonas Haferkamp, Aram Harrow, Richard Kueng, Saeed Mehraban, John Napp, and Sepehr Nezami for discussions and helpful comments on the draft. AD and FB acknowledge funding provided by the Institute for Quantum Information and Matter, an NSF Physics Frontiers Center (NSF Grant PHY-1733907). This material is also based upon work supported by the National Science Foundation Graduate Research Fellowship under Grant No. DGE-1745301. NHJ would like to thank the IQIM 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
Province of Ontario Ministry of Colleges and UniversitiesUNSPECIFIED
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:11 May 2021 20:36

Repository Staff Only: item control page