QuICS Special Seminar

Tue, Aug 10, 2021 10:00 am - 11:00 am


Title: Linear growth of quantum circuit complexity
Speaker: Jonas Haferkamp (Freie Universität Berlin)
Time: Tuesday, August 10, 2021 - 10:00am
Location: Virtual Via Zoom: https://umd.zoom.us/j/91765577450?pwd=T1h1OXBmSVRvVVAreGZsK3pHRHpqUT09

Quantifying quantum states’ complexity is a key problem in various subfields of science, from quantum computing to black-hole physics. We prove a prominent conjecture by Brown and Susskind about how random quantum circuits’ complexity increases. 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. Reference: Haferkamp, Jonas, et al. "Linear growth of quantum circuit complexity." arXiv preprint arXiv:2106.05305 (2021).

This talk is part of the IQC-QuICS Math and Computer Science Seminar.

Upcoming Events

22 Sep
High Energy
Date Wed, Sep 22, 2021 4:00 pm - 5:30 pm
23 Sep
Online Nuclear Theory Seminar
Thu, Sep 23, 2021 11:00 am - 12:30 pm
24 Sep
Friday Quantum Seminar: Wade Hodson
Fri, Sep 24, 2021 12:00 pm - 12:45 pm
24 Sep
Materials Science and Engineering Seminar
Fri, Sep 24, 2021 1:00 pm - 2:00 pm
27 Sep
JQI Seminar
Mon, Sep 27, 2021 11:00 am - 12:00 pm