From Classical to Quantum Circuit Complexity - The Tale of QAC0

Explore the power and limitations of quantum circuit complexity in this computer science seminar focusing on QAC0 circuits - constant-depth quantum circuits composed of arbitrary single-qubit gates and unbounded CZ/Toffoli gates. Discover how these circuits exhibit Fourier concentration properties that enable both computational lower-bound proofs and efficient learning algorithms for QAC0 unitaries and channels. Learn about the implementation of pseudorandom functions and unitaries in QAC0 and their implications for learning lower-bounds. Examine how these findings connect to the fundamental open question in quantum complexity theory: whether Parity/Fan-Out operations belong to QAC0. Understand the practical relevance of this research in the NISQ (Noisy Intermediate-Scale Quantum) era, where noise constraints limit quantum devices to shallow computation depths. The presentation draws from collaborative research with Ben Foxman, Hsin-Yuan Huang, Shivam Nadimpalli, Natalie Parham, and Henry Yuen, offering insights into both theoretical quantum complexity and practical quantum computing limitations.