Linear Growth of Quantum Circuit Complexity | Seminar Series with Nicole Yunger Halpern

Linear Growth of Quantum Circuit Complexity

Speaker: Nicole Yunger Halpern
Host: Zlatko Minev, PhD.

Abstract:
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 with
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.
References
1) Haferkamp, Faist, Kothakonda, Eisert, and NYH, accepted by Nat. Phys.
(in press) arXiv:2106.05305.
2) NYH, Kothakonda, Haferkamp, Munson, Faist, and Eisert,
arXiv:2110.11371 (2021).

--

The Qiskit Seminar Series is a deep dive into various academic and research topics within the quantum community. It will feature community members and leaders every Friday, 12 PM EDT.

[hanchisun]

How does the Haar measure got places in the proof? What happens if we assume the SU gates are not spread out evenly (according to Haar measure), for example if they are more concentrated around the pool?