A Caltech Library Service

Models of quantum complexity growth

Brandão, Fernando G. S. L. and Chemissany, Wissam and Hunter-Jones, Nicholas and Kueng, Richard and Preskill, John (2019) Models of quantum complexity growth. . (Unpublished)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


The concept of quantum complexity has far-reaching implications spanning theoretical computer science, quantum many-body physics, and high energy physics. The quantum complexity of a unitary transformation or quantum state is defined as the size of the shortest quantum computation that executes the unitary or prepares the state. It is reasonable to expect that the complexity of a quantum state governed by a chaotic many-body Hamiltonian grows linearly with time for a time that is exponential in the system size; however, because it is hard to rule out a short-cut that improves the efficiency of a computation, it is notoriously difficult to derive lower bounds on quantum complexity for particular unitaries or states without making additional assumptions. To go further, one may study more generic models of complexity growth. We provide a rigorous connection between complexity growth and unitary k-designs, ensembles which capture the randomness of the unitary group. This connection allows us to leverage existing results about design growth to draw conclusions about the growth of complexity. We prove that local random quantum circuits generate unitary transformations whose complexity grows linearly for a long time, mirroring the behavior one expects in chaotic quantum systems and verifying conjectures by Brown and Susskind. Moreover, our results apply under a strong definition of quantum complexity based on optimal distinguishing measurements.

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Brandão, Fernando G. S. L.0000-0003-3866-9378
Chemissany, Wissam0000-0002-9113-4463
Hunter-Jones, Nicholas0000-0001-8578-1958
Preskill, John0000-0002-2421-4762
Additional Information:The authors would like thank Dorit Aharonov, Thom Bohdanowicz, Elizabeth Crosson, Felix Haehl, Aram Harrow, Tomas Jochym-O'Connor, Hugo Marrochio, Grant Salton, Eugene Tang, and Thomas Vidick for inspiring discussions and valuable feedback. All authors acknowledge funding provided by the Institute for Quantum Information and Matter, an NSF Physics Frontiers Center (NSF Grant PHY-1733907). JP is supported in part by DOE Award DE-SC0018407 and by the Simons Foundation It from Qubit Collaboration. RK is supported in part by the Office of Naval Research (Award N00014-17-1-2146) and the Army Research Office (Award W911NF121054). NHJ would like to thank the IQIM at Caltech, McGill University, and UC Berkeley for their hospitality during the completion of this work. Research at Perimeter Institute is supported by the Government of Canada through the Department of Innovation, Science and Economic Development Canada and by the Province of Ontario through the Ministry of Research, Innovation and Science.
Group:Institute for Quantum Information and Matter, Walter Burke Institute for Theoretical Physics
Funding AgencyGrant Number
Institute for Quantum Information and Matter (IQIM)UNSPECIFIED
Department of Energy (DOE)DE-SC0018407
Simons FoundationUNSPECIFIED
Office of Naval Research (ONR)N00014-17-1-2146
Army Research Office (ARO)W911NF121054
Perimeter Institute for Theoretical PhysicsUNSPECIFIED
Department of Innovation, Science and Economic Development (Canada)UNSPECIFIED
Ontario Ministry of Research, Innovation and ScienceUNSPECIFIED
Record Number:CaltechAUTHORS:20210512-095238258
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:109092
Deposited By: Tony Diaz
Deposited On:12 May 2021 17:03
Last Modified:12 May 2021 17:03

Repository Staff Only: item control page