Francisca Vasconcelos (Berkeley) — On the Pauli Spectrum of QAC^0

Title: On the Pauli Spectrum of QAC^0

Abstract
The circuit class QAC^0 was introduced by Moore (1999) as a model for constant depthquantum circuits where the gate set includes many-qubit Toffoli gates. Proving lower boundsagainst such circuits is a longstanding challenge in quantum circuit complexity; in particular, showing that polynomial-size QAC^0cannot compute the parity function has remained an openquestion for over 20 years. 

In this work, we identify a notion of the Pauli spectrum of QAC^0 circuits, which can be viewed as the quantum analogue of the Fourier spectrum of classical AC^0 circuits. We conjecture that the Pauli spectrum of QAC^0 circuits satisfies low-degree concentration, in analogy to the famous Linial, Nisan, Mansour theorem on the low-degree Fourier concentration of AC^0 circuits. If true, this conjecture immediately implies that polynomial-size QAC^0 circuits cannot compute parity. 

We prove this conjecture for the class of depth-d, polynomial-size QAC^0 circuits with at most n^{O(1/d)} auxiliary qubits. We obtain new circuit lower bounds and learning results as applications: this class of circuits cannot correctly compute 
• the n-bit parity function on more than ( 1/2 + 2^{−Ω(n^{1/d})} )-fraction of inputs, and 
• the n-bit majority function on more than ( 1/2 + O(n^{−1/4}))-fraction of inputs.
Additionally we show that this class of QAC^0 circuits with limited auxiliary qubits can be learned with quasipolynomial sample complexity, giving the first learning result for QAC^0 circuits. More broadly, our results add evidence that “Pauli-analytic” techniques can be a powerful tool in studying quantum circuits. 

Date of talk: 2024-04-12