Quantum Colloquium — Linear Growth of Quantum Circuit Complexity

Quantifying quantum states' complexity is a key problem in various subfields of science, ranging from quantum computing - where it is closely related to notions of computational complexity - to black-hole physics. In this talk, we discuss notions of circuit complexity from different perspectives. We start from classifying quantum states according to the preparation complexity. The main result presented in the talk is a proof of a prominent conjecture by Brown and Susskind about how random quantum circuits' complexity increases with the depth of the circuit [1]. For this, we discuss random circuits composed of Haar-random two-qubit quantum gates. Implementing the unitary exactly requires a circuit of some minimal number of gates - the unitary's exact circuit complexity. We prove that this complexity grows linearly in the number of random gates, with unit probability, until saturating after exponentially many random gates. Our proof is surprisingly short, given the established difficulty of lower-bounding the exact circuit complexity. Our strategy combines differential topology and elementary algebraic geometry with an inductive construction of Clifford circuits. We hint at approximate notions of complexity, and have a brief look at the role entanglement plays here [2]. We procrastinate briefly when stating that surprisingly, random Clifford circuits can be uplifted to approximate unitary designs by a number of T-gates that is independent of the system size [3]. In the last part of the talk, we discuss notions of quantum thermodynamics from the perspective of complexity, elaborate on notions of Landauer erasure and have a look at what could be called a resource theory of quantum uncomplexity [4].

[1] J. Haferkamp, P. Faist, N. B. T. Kothakonda, J. Eisert, N. Yunger Halpern, Linear growth of quantum circuit complexity, Nature Physics 18, 528–532 (2022).

[2] J. Eisert, Entangling power and quantum circuit complexity, Physical Review Letters 127, 020501 (2021).

[3] J. Haferkamp, F. Montealegre-Mora, M. Heinrich, J. Eisert, D. Gross, I. Roth, Efficient unitary designs with a system-size independent number of non-Clifford gates, arXiv:2002.09524, Communications in Mathematical Physics, in press (2022).

[4] N. Yunger Halpern, N. B. T. Kothakonda, J. Haferkamp, A. Munson, J. Eisert, P. Faist, Resource theory of quantum uncomplexity, arXiv:2110.11371 (2021).

Panel discussion: Nick Hunter-Jones (Stanford), Nicole Yunger Halpern (University of Maryland), Scott Aaronson (UT Austin), Vijay Balasubramanian (University of Pennsylvania), Umesh Vazirani (UC Berkeley; moderator)