Computer Science/Discrete Mathematics Seminar I

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 $QAC^0$ 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 $QAC^0$ circuits exhibit a form of Fourier concentration that can be leveraged to prove computational lower-bounds as well as obtain efficient algorithms for learning $QAC^0$ unitaries and channels. I will also describe how the implementation of pseudorandom functions/unitaries in $QAC^0$ 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 $QAC^0$?

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