{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreicmsjqi45swybvtxlbohbsmpllywb5ri74i5bvd7kq43ino2bxydy",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mistwpfvmo22"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2604.02793v1",
  "publishedAt": "2026-04-06T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Lucas Gretta",
    "Meghal Gupta",
    "Malvika Raj Joshi"
  ],
  "textContent": "**Authors:** Lucas Gretta, Meghal Gupta, Malvika Raj Joshi\n\nA 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 coefficients, no AC$^0$ circuit can non-trivially correlate with it. In contrast, we provide a QAC$^0$ circuit that achieves $(1-o(1))$ correlation with MAJORITY, establishing the first average-case decision separation between AC$^0$ and QAC$^0$. This suggests a uniquely quantum phenomenon: unlike in the classical setting, Fourier concentration may largely characterize the power of QAC$^0$. PARITY is also known to be equivalent in QAC$^0$ to inherently quantum tasks such as preparing GHZ states to high fidelity. We extend this equivalence to a broad class of state-synthesis tasks. We demonstrate that existing metrics such as trace distance, fidelity, and mutual information are insufficient to capture these states and introduce a new measure, felinity. We prove that preparing any state with non-negligible felinity, or derived states such as poly(n)-weight Dicke states, implies PARITY $\\in$ QAC$^0$.",
  "title": "Parity $\\notin$ QAC0 $\\iff$ QAC0 is Fourier-Concentrated"
}