BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Nicole Yunger Halpern (QuICS\, NIST\, University of Maryland) DTSTART:20220308T203000Z DTEND:20220308T213000Z DTSTAMP:20260423T005714Z UID:HET/29 DESCRIPTION:Title: Lin ear growth of quantum circuit complexity\nby Nicole Yunger Halpern (Qu ICS\, NIST\, University of Maryland) as part of Purdue HET\n\n\nAbstract\n Quantifying quantum states' complexity is a key problem in various subfiel ds of science\, from quantum computing to black-hole physics. We prove a p rominent conjecture by Brown and Susskind about how random quantum circuit s' complexity increases. Consider constructing a unitary from Haar-random two-qubit quantum gates. Implementing the unitary exactly requires a circu it of some minimal number of gates—the unitary's exact circuit complexit y. We prove that this complexity grows linearly with the number of random gates\, with unit probability\, until saturating after exponentially many random gates. Our proof is surprisingly short\, given the established diff iculty of lower-bounding the exact circuit complexity. Our strategy combin es differential topology and elementary algebraic geometry with an inducti ve construction of Clifford circuits.\n\nReferences 1) Haferkamp\, Faist\, Kothakonda\, Eisert\, and NYH\, accepted by Nat. Phys. (in press) arXiv:2 106.05305. 2) NYH\, Kothakonda\, Haferkamp\, Munson\, Faist\, and Eisert\, arXiv:2110.11371 (2021).\n LOCATION:https://researchseminars.org/talk/HET/29/ END:VEVENT END:VCALENDAR