Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published March 2022 | Submitted + Published
Journal Article Open

Random Quantum Circuits Anticoncentrate in Log Depth

Abstract

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.

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.

Attached Files

Published - PRXQuantum.3.010333.pdf

Submitted - 2011.12277.pdf

Files

2011.12277.pdf
Files (2.3 MB)
Name Size Download all
md5:bfcbe70d64d5e187c813c04b03525d77
670.8 kB Preview Download
md5:077f0ff7c3ee887260d7a19589640421
1.6 MB Preview Download

Additional details

Created:
August 20, 2023
Modified:
October 23, 2023