{"id":"arxiv/2604.02793","url":"https://arxiv.org/abs/2604.02793","tags":["quant-ph","cs.CC"],"score":0,"title":"Parity $\\notin$ QAC0 $\\iff$ QAC0 is Fourier-Concentrated","domain":"quant-ph","source":"arxiv","authors":["Lucas Gretta","Meghal Gupta","Malvika Raj Joshi"],"reviews":0,"subject":"quant-ph","summary":"A major open problem in understanding shallow quantum circuits (QAC$^0$) is whether they can compute Parity. We show that this question is solely about the Fourier spectrum of QAC$^0$: any QAC$^0$ circuit with non-negligible high-level Fourier mass suffices to exactly compute PARITY in QAC$^0$. Thus, proving a quantum analog of the seminal LMN theorem for AC$^0$ is necessary to bound the quantum circuit complexity of PARITY. In the other direction, LMN does not fully capture the limitations of AC$^0$. For example, despite MAJORITY having $99\\%$ of its weight on low-degree Fourier…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-04-03","reactions":{}}