On the Pauli Spectrum of QAC0

Shivam Nadimpalli, Natalie Parham, Francisca Vasconcelos +1

The circuit class ${\mathsf{QAC}}^0$ was introduced by Moore (1999) as a model for constant depth quantum circuits where the gate set includes many-qubit Toffoli gates. Proving lower…