From Classical to Quantum Circuit Complexity: The Tale of (Q)AC0

In the NISQ era, where noise limits device coherence times, we are fundamentally constrained to shallow quantum computation. This talk will explore the power, limitations, and learnability of the QAC0

circuit class--i.e. the family of constant-depth circuits composed of arbitrary single-qubit gates and unbounded CZ/Toffoli gates. In particular, I will explain how QAC0

circuits exhibit a form of Fourier concentration that can be leveraged to prove computational lower-bounds as well as obtain efficient algorithms for learning QAC0

unitaries and channels. I will also describe how the implementation of pseudorandom functions/unitaries in QAC0

implies (nearly matching) learning lower-bounds. Throughout the talk, I will highlight how these results relate to a long-standing open problem in quantum complexity: is Parity/Fan-Out in QAC0?

The talk is based on joint work with Ben Foxman, Hsin-Yuan Huang, Shivam Nadimpalli, Natalie Parham, and Henry Yuen