Theory Seminar: Shivam Nadimpalli

The talk on 9/15 is by Shivam Nadimpalli. Talk details are included below.

Title: On the Pauli Spectrum of \mathsf{QAC}^0

Abstract: The circuit class \mathsf{QAC}^0 was introduced by Moore (1999) as a theoretical model for constant depth quantum circuits where many-qubit Toffoli gates are part of the gate set. Proving lower bounds against such circuits is a longstanding challenge in quantum circuit complexity; in particular, showing that polynomial-size \mathsf{QAC}^0 cannot compute the parity function has remained an open question for over 20 years.

In this work, we obtain the first average-case lower bounds against \mathsf{QAC}^0 circuits. We show that depth-d \mathsf{QAC}^0 circuits with n^{O(1/d)} auxiliary qubits cannot correctly compute

-The n-bit parity function on more than (1/2 + 1/\mathrm{poly}(n))-fraction of inputs, and

-The n-bit majority function on more than (1 - 1/\mathrm{poly}(n))-fraction of inputs.

We note that no lower bounds for the majority function against \mathsf{QAC}^0 circuits were known prior to this work.

At the heart of our lower bounds is a structural result on the Pauli spectrum of \mathsf{QAC}^0 circuits, which can be viewed as the quantum analogue of the Fourier spectrum of classical \mathsf{AC}^0 circuits. As a consequence we also obtain a learning algorithm for \mathsf{QAC}^0 circuits with quasipolynomial sample complexity. More broadly, our results add evidence that “Pauli-analytic” techniques can be a powerful tool in studying quantum circuits.

The talk will assume no quantum background and will be self-contained. Based on joint work with Natalie Parham, Francisca Vasconcelos, and Henry Yuen