
From Classical to Quantum Circuit Complexity: The Tale of (Q)AC0
Francisca Vasconcelos, a researcher at UC Berkeley, presents this Institute for Advanced Study seminar on the complexity class QAC0, the constant-depth quantum circuits built from arbitrary single-qubit gates plus unbounded CZ and Toffoli gates. She explains why near-term noisy quantum devices force computation into shallow circuits, then shows how QAC0 circuits exhibit Fourier concentration, a property that yields both computational lower bounds and efficient algorithms for learning QAC0 unitaries and channels. She describes how implementing pseudorandom functions and unitaries within QAC0 produces nearly matching learning lower bounds, and connects the results to a long-standing open question in quantum complexity theory: whether Parity and Fan-Out belong to QAC0. The talk draws on joint work with Ben Foxman, Hsin-Yuan Huang, Shivam Nadimpalli, Natalie Parham, and Henry Yuen, and is pitched at a seminar audience already familiar with circuit complexity and quantum computing basics.