Parity is not in QAC0

Solved ID op_95fccb9df34a08b1 Last edited 6 November 2026
Edit

Problem

Is \(\mathrm{PARITY}\notin\mathsf{QAC}^0\)?

For \(x=(x_1,\ldots,x_n)\in\{0,1\}^n\), define

\begin{equation} \mathrm{PARITY}_n(x)=x_1\oplus x_2\oplus\cdots\oplus x_n. \tag{1} \end{equation}

A \(\mathsf{QAC}^0\) circuit family consists of polynomial-size quantum circuits of constant depth built from arbitrary single-qubit gates and generalized Toffoli gates, with polynomially many ancilla qubits initialized to a fixed computational-basis state.

The conjecture is that there do not exist a constant \(d\), a polynomial \(p\), and a family of depth-at-most-\(d\) \(\mathsf{QAC}^0\) circuits \(C_n\) of size and ancilla count at most \(p(n)\) such that, for every \(n\) and every \(x\in\{0,1\}^n\), measurement of a designated output qubit gives

\begin{equation} \Pr\bigl[\,C_n(x)\text{ outputs }\mathrm{PARITY}_n(x)\,\bigr]=1. \tag{2} \end{equation}

Equivalently, the conjecture asserts that no polynomial-size constant-depth \(\mathsf{QAC}^0\) family satisfies (2) for the function defined in (1).

Source

Moore explicitly posed the question whether ordinary \(\mathsf{QAC}^0\) can implement fanout; his constant-depth equivalence between fanout and parity makes this the foundational form of the problem [Moo99]. Later literature explicitly formulates the expected negative answer as the conjecture that \(\mathrm{PARITY}\notin\mathsf{QAC}^0\), and the statement above is a contributor-normalized formulation of that conjecture.

Progress

Reports do not certify correctness or automatically change the problem's status. Progress policy.

  • Moore introduced \(\mathsf{QAC}^0\) as a quantum analogue of classical \(\mathsf{AC}^0\) and showed that constant-depth quantum fanout and parity are equivalent up to constant-depth reductions; determining whether fanout can be implemented in ordinary \(\mathsf{QAC}^0\) is equivalent to determining whether parity belongs to \(\mathsf{QAC}^0\) [Moo99].

  • Rosenthal established strong lower bounds for depth-two \(\mathsf{QAC}^0\) circuits approximating parity and gave the principal known constant-depth upper bound for approximating parity with superpolynomially many resources; that result does not settle the polynomial-size arbitrary-constant-depth case [Ros21].

  • Nadimpalli, Parham, Vasconcelos, and Yuen defined the Pauli spectrum of a \(\mathsf{QAC}^0\) circuit and proved a quantum analogue of low-degree Fourier concentration for classical \(\mathsf{AC}^0\), together with strong parity lower bounds, when the number of auxiliary qubits is sufficiently restricted as a function of circuit depth [NPVY24].

  • For depth \(d\), Anshu, Dong, Ou, and Yao proved that computing functions of linear approximate degree, including parity, requires at least \(n^{1+3^{-d}}\) ancilla qubits; since \(\mathsf{QAC}^0\) permits an arbitrary polynomial number of ancillae, this does not by itself resolve the conjecture, but a sufficiently stronger depth-dependent exponent would imply \(\mathrm{PARITY}\notin\mathsf{QAC}^0\) [ADOY25].

  • Joshi, Tal, Vasconcelos, and Wright proved that depth-three \(\mathsf{QAC}^0\) circuits cannot compute parity, regardless of their size or number of ancilla qubits, and proved stronger approximation lower bounds at depth two; the separation is therefore established for depth at most three [JTVW26].

  • Gretta, Gupta, and Joshi proved that if a polynomial-size \(\mathsf{QAC}^0\) circuit family has non-negligible Fourier mass at sufficiently high levels, then parity can be computed exactly in \(\mathsf{QAC}^0\); in their formulation the corresponding Fourier-concentration statement is equivalent to separating parity from \(\mathsf{QAC}^0\) [GGJ26].

  • Any correlation with parity that is at least inverse-polylogarithmic in \(n\) can be amplified and, with constant-factor depth overhead and polynomial resources, converted into exact parity computation; a subsequent result of Gretta, Gupta, and Joshi shows that non-negligible, inverse-polynomial correlation also suffices. Average-case or approximation lower bounds at these thresholds can therefore contribute directly to resolving the exact conjecture [JTVW26], [GGJ26].

  • OpenAI reports a proof of \(\mathrm{PARITY}\notin\mathsf{QAC}^0\) (Theorem 1, p. 1) [OAI26]. For every fixed depth, polynomial bound on the total number of qubits, and fixed \(0<\varepsilon\leq1/2\), the theorem excludes circuits with success probability at least \(1/2+\varepsilon\) on every input for all sufficiently large input lengths. Zero-initialized ancillas and arbitrary discarded garbage are allowed; the claim therefore implies the exact-computation separation stated above.

  • Gao, Ji, and Liu give a self-contained simplification of OpenAI’s proof in ECCC preprint TR26-258, Theorem 1 [GJL26]. For every fixed depth \(d\), exponent \(c\geq1\), and \(0<\varepsilon\leq1/2\), every such circuit on \(n\leq N\leq n^c\) qubits fails to achieve success probability \(1/2+\varepsilon\) on at least one input for all sufficiently large \(n\). The theorem allows zero-initialized ancillas and unrestricted final garbage. Any fixed computational-basis initialization in the statement can be prepared from zeros by one layer of single-qubit gates, so the theorem also excludes exact computation in the stated model.

Comment

The separation is established by the parity lower bound in [OAI26] and its self-contained simplification [GJL26], both preprints. The Solved designation concerns the full exact-computation question above, not merely a restriction on depth or ancillary space. The theorem also rules out any fixed positive worst-case advantage over random guessing with polynomially many qubits.

References

[Moo99]
Cristopher Moore, “Quantum Circuits: Fanout, Parity, and Counting” (1999).arXiv
[Ros21]
Gregory Rosenthal, “Bounds on the QAC\(^0\) Complexity of Approximating Parity,” in 12th Innovations in Theoretical Computer Science Conference (ITCS 2021), LIPIcs 185, 32:1–32:20 (2021).DOIarXiv
[NPVY24]
Shivam Nadimpalli, Natalie Parham, Francisca Vasconcelos, and Henry Yuen, “On the Pauli Spectrum of QAC0,” in Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC 2024), 1498–1506 (2024).DOIarXiv
[ADOY25]
Anurag Anshu, Yangjing Dong, Fengning Ou, and Penghui Yao, “On the Computational Power of QAC0 with Barely Superlinear Ancillae,” in Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC 2025), 1476–1487 (2025).DOIarXiv
[JTVW26]
Malvika Raj Joshi, Avishay Tal, Francisca Vasconcelos, and John Wright, “Improved Lower Bounds for QAC0,” in Proceedings of the 58th Annual ACM Symposium on Theory of Computing (STOC 2026), 2199–2209 (2026).DOIarXiv
[GGJ26]
Lucas Gretta, Meghal Gupta, and Malvika Raj Joshi, “Parity \(\notin\) QAC0 \(\Longleftrightarrow\) QAC0 is Fourier-Concentrated,” in 67th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2026) (2026).arXiv
[OAI26]
OpenAI, “Product-projection localization and the \(\mathrm{QAC}^0\) parity lower bound,” OpenAI Math Release preprint, 24 September 2026. manuscript (release version).link
[GJL26]
Minbo Gao, Zhengfeng Ji, and Chenghua Liu, “A simplified proof of \(\mathrm{PARITY}\notin\mathsf{QAC}^0\),” Electronic Colloquium on Computational Complexity, TR26-258, preprint (18 October 2026). ECCC TR26-258.link

Cite this problem

Please also cite the primary sources listed under References. Cite this page for the statement, status, and stable identifier.

BibTeX

@incollection{qiqcop_op_95fccb9df34a08b1,
  title = {Parity is not in QAC0},
  booktitle = {Quantum Information and Quantum Computation Open Problem Zoo (QIQCOP Zoo)},
  year = {2026},
  howpublished = {\url{https://qiqc-op.com/problem/op_95fccb9df34a08b1/}},
  note = {Stable ID op_95fccb9df34a08b1; status: Solved; accessed 2026-11-06}
}

Plain text

“Parity is not in QAC0,” Quantum Information and Quantum Computation Open Problem Zoo (QIQCOP Zoo), https://qiqc-op.com/problem/op_95fccb9df34a08b1/, ID op_95fccb9df34a08b1, accessed 2026-11-06.

Share this problem

Permanent link

Identifiers

op_95fccb9df34a08b1
01M20F505SW8RJ6Z0WK8B31TEH