Linear Growth of Complexity in Brownian Circuits

RQS-QuICS Special Seminar

Gregory Bentsen (Brandeis University)
Wednesday, December 14, 2022 - 11:00am
ATL 3100A and Virtual Via Zoom

Generating randomness efficiently is a key capability in both classical and quantum information processing applications. For example, Haar-random quantum states serve as primitives for applications including quantum cryptography, quantum process tomography, and randomized benchmarking. How quickly can these random states be generated? And how much randomness is really necessary for any given application? In this talk, I will address these questions in Brownian quantum circuit models, which admit a large-$N$ limit that can be solved exactly. Using path integrals methods I demonstrate that Brownian quantum systems have circuit complexity that grows linearly with time. In particular, I present a calculation of the $k$th Frame Potential in this model and show that it comes within $\epsilon$ of the Haar value after a time of order $t \sim k N + k \log k + \log \epsilon^{-1}$. This implies that the Brownian circuits come very close to a unitary $k$-design after a time of order $t \sim k N$. These same Brownian circuit models are also applicable to other salient problems in many-body dynamics, including measurement-induced phase transitions, dissipative quantum state engineering, and the design of new continuous-variable quantum error-correcting codes. I will conclude by reviewing some of these applications and suggesting some interesting future directions.