11-23
Special Quantum Seminar - Complexity growth and efficient compilation of quantum circuits

Simple quantum gates can generate complex dynamics. In this talk, I will explore this relationship in two settings: complexity growth in random quantum circuits and compilation into a fault-tolerant gate set.

First, if a quantum system undergoes a long sequence of local random interactions, could the same evolution be produced by a much shorter sequence? We show that the circuit complexity of random quantum circuits grows linearly with the number of gates applied, even allowing constant approximation error. In other words, random quantum circuits are incompressible. This growth persists for exponentially long time, resolving the robust Brown–Susskind conjecture for random quantum circuits [arXiv:2406.07478].

Second, how much additional cost arises when we implement a quantum computation using a fault-tolerant gate set? Standard compilation of a circuit with G arbitrary one- and two-qubit gates into {H,T,CNOT} uses O(G log(G/ϵ)) gates to achieve error ϵ. We show that, by allowing intermediate measurements and feedforward, this logarithmic overhead can be eliminated: O(G) gates suffice for any target error ϵ = 1/poly(G) [arXiv:2609.39092].

Date and Time
Monday November 23, 2026 1:30pm - 2:30pm
Location
Computer Science Small Auditorium (Room 105)
Speaker
Norah Tan, from MIT

Contributions to and/or sponsorship of any event does not constitute departmental or institutional endorsement of the specific program, speakers or views presented.

CS Talks Mailing List