Jens Eisert - Linear growth of quantum circuit complexity
CERN
Quantifying quantum states' complexity is a key problem in various subfields of science, from quantum computing to black-hole physics. In this talk, we prove a prominent conjecture by Brown and Susskind about how random quantum circuits' complexity increases [1]. Consider constructing a unitary from 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 have a brief look at the role entanglement plays here [2]. In a long outlook, we will have a look at what could be called a resource theory of quantum uncomplexity [3].
[1] J. Haferkamp, P. Faist, N. B. T. Kothakonda, J. Eisert, N. Yunger Halpern, Linear growth of quantum circuit complexity, arXiv:2106.05305, Nature Physics, in press (2022).
[2] J. Eisert, Entangling power and quantum circuit complexity, arXiv:2104.03332, Physical Review Letters 127, 020501 (2021).
[3] N. Yunger Halpern, N. B. T. Kothakonda, J. Haferkamp, A. Munson, J. Eisert, P. Faist, Resource theory of quantum uncomplexity, arXiv:2110.11371 (2021).
