Parity $\notin$ QAC0 $\iff$ QAC0 is Fourier-Concentrated

Lucas Gretta; Malvika Raj Joshi; Meghal Gupta

arxiv: 2604.02793 · v1 · submitted 2026-04-03 · 🪐 quant-ph · cs.CC

Parity notin QAC0 iff QAC0 is Fourier-Concentrated

Lucas Gretta , Meghal Gupta , Malvika Raj Joshi This is my paper

Pith reviewed 2026-05-13 20:17 UTC · model grok-4.3

classification 🪐 quant-ph cs.CC

keywords QAC0ParityFourier spectrumMajorityfelinityquantum circuitsstate preparationGHZ states

0 comments

The pith

QAC0 computes Parity exactly when its circuits carry non-negligible high-degree Fourier mass.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper reduces the open question of whether shallow quantum circuits can compute Parity to a single property of their Fourier spectrum. Any QAC0 circuit whose Fourier transform places non-negligible weight on high degrees can be converted into an exact QAC0 circuit for Parity. This equivalence implies that a quantum version of the LMN theorem is both necessary and, if proved, sufficient to place Parity outside QAC0. The same Fourier lens yields a concrete separation: the authors build a QAC0 circuit that achieves almost perfect correlation with Majority, something impossible for classical AC0. They further tie Parity to a broad class of state-preparation tasks via a new quantity, felinity, that captures features missed by trace distance, fidelity, and mutual information.

Core claim

Any QAC0 circuit with non-negligible high-level Fourier mass suffices to exactly compute PARITY in QAC0. Thus Parity is in QAC0 if and only if QAC0 is not Fourier-concentrated. The same analysis produces a QAC0 circuit that (1-o(1))-correlates with Majority and shows that preparing any state of non-negligible felinity, or poly(n)-weight Dicke states, is equivalent to computing Parity in QAC0.

What carries the argument

The reduction that turns non-negligible high-degree Fourier mass in a QAC0 circuit into an exact QAC0 circuit for Parity.

Load-bearing premise

High-degree Fourier mass in a QAC0 circuit can be converted into an exact Parity circuit without further assumptions on the circuit structure.

What would settle it

Exhibiting a QAC0 circuit whose Fourier transform has inverse-polynomial mass above degree polylog(n) would immediately produce an exact QAC0 circuit for Parity.

read the original abstract

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 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$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper reduces Parity in QAC0 to whether those circuits carry non-negligible high-degree Fourier mass, and supplies a QAC0 circuit with (1-o(1)) Majority correlation.

read the letter

The central move is an equivalence: any QAC0 circuit with non-negligible high-degree Fourier mass yields an exact QAC0 circuit for Parity. The other direction is the explicit construction that correlates (1-o(1)) with Majority, which separates QAC0 from AC0 on average case. That correlation is the clearest new concrete fact in the abstract and is worth checking in detail because classical AC0 cannot do anything similar for Majority. The reframing itself is useful if the reduction is clean, since it lets future work focus on Fourier tails rather than full circuit simulation. The state-synthesis extension via felinity is secondary and mainly serves to broaden the equivalence to GHZ-like tasks. The soft spot is the reduction from high-degree mass to exact Parity. Extracting or amplifying a single high-degree coefficient in a constant-depth bounded-fan-in quantum circuit usually costs either extra depth or approximation error that must be driven below 1/poly(n). The abstract asserts the step is direct, but without the error analysis it is not obvious that coherent measurement statistics or any classical post-processing stay inside QAC0. The felinity definition also looks tailored to the claim rather than independently motivated. This is for people working on quantum circuit lower bounds and Fourier analysis of shallow circuits. It deserves a serious referee because the open question is central and the Majority correlation is a tangible advance, even if the main reduction needs close verification on the error bounds.

Referee Report

3 major / 2 minor

Summary. The paper claims an equivalence: Parity is not in QAC0 if and only if QAC0 is Fourier-concentrated. Specifically, any QAC0 circuit whose acceptance function has non-negligible mass on high-degree Fourier coefficients yields an exact QAC0 circuit for Parity. The converse direction is used to argue that a quantum LMN theorem would suffice to separate Parity from QAC0. The paper also constructs a QAC0 circuit achieving (1-o(1)) correlation with Majority (unlike AC0), and extends the Parity equivalence to state-synthesis tasks by introducing a new measure called felinity, proving that non-negligible felinity (or poly(n)-weight Dicke states) implies Parity in QAC0.

Significance. If the central equivalence holds, the work supplies a Fourier-analytic characterization of QAC0 power that is tighter than the classical LMN theorem, because Fourier concentration would be both necessary and sufficient for the model's limitations. The explicit QAC0-Majority correlation and the felinity-based state-synthesis equivalences would constitute the first average-case and state-preparation separations between AC0 and QAC0. These results are load-bearing for any future lower-bound program that hopes to use Fourier methods on shallow quantum circuits.

major comments (3)

[Main equivalence (abstract and § on Fourier-to-Parity reduction)] The reduction asserted in the abstract (and presumably proved in the main theorem) claims that non-negligible high-degree Fourier mass in a QAC0 circuit directly yields an exact QAC0 Parity circuit. This reduction must be shown to remain inside constant depth and bounded fan-in; extracting or amplifying a single high-degree coefficient classically requires either depth-dependent queries or an approximation whose error must be driven below 1/poly(n). The manuscript must supply an explicit error analysis demonstrating that neither depth nor coherent measurement error grows with n.
[State-synthesis equivalences and felinity definition] The definition of 'felinity' and the claim that any state with non-negligible felinity (or derived poly(n)-weight Dicke states) implies Parity in QAC0 are load-bearing for the state-synthesis extension. Because felinity is an invented quantity, the manuscript must prove that the measure is well-defined, that the reduction from felinity to a high-degree Fourier coefficient preserves the QAC0 model, and that the error terms remain negligible independently of depth.
[QAC0-Majority correlation construction] The (1-o(1)) correlation with Majority is presented as evidence that Fourier concentration may characterize QAC0 more completely than it does AC0. The circuit construction and the precise correlation calculation must be checked to confirm that the error is o(1) while the circuit depth and gate fan-in remain constant; any hidden dependence on n in the error bound would undermine the claimed separation.

minor comments (2)

[Abstract and definitions] The precise quantitative meaning of 'non-negligible' Fourier mass (e.g., 1/poly(n) versus 1/log n) should be stated uniformly in the abstract, the main theorem statement, and the error analysis so that the threshold is unambiguous.
[Fourier analysis section] Notation for the Fourier transform of a quantum circuit's acceptance function should be introduced once and used consistently; the current placeholder text leaves the precise mapping from circuit to multilinear polynomial unclear.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for their careful and constructive review. The comments highlight important points about explicit error bounds and definitions that will improve the clarity of the manuscript. We address each major comment below and will revise accordingly.

read point-by-point responses

Referee: [Main equivalence (abstract and § on Fourier-to-Parity reduction)] The reduction asserted in the abstract (and presumably proved in the main theorem) claims that non-negligible high-degree Fourier mass in a QAC0 circuit directly yields an exact QAC0 Parity circuit. This reduction must be shown to remain inside constant depth and bounded fan-in; extracting or amplifying a single high-degree coefficient classically requires either depth-dependent queries or an approximation whose error must be driven below 1/poly(n). The manuscript must supply an explicit error analysis demonstrating that neither depth nor coherent measurement error grows with n.

Authors: We agree that an explicit error analysis strengthens the presentation. The reduction in Theorem 3.1 isolates the high-degree Fourier coefficient via a constant-depth coherent measurement on the output of the given QAC0 circuit; because the circuit depth is fixed and fan-in bounded, the measurement error is controlled solely by the coefficient magnitude (non-negligible by assumption) and does not accumulate with n. We will add a dedicated error-propagation subsection with explicit bounds showing total variation distance O(1/poly(n)) independent of depth. revision: yes
Referee: [State-synthesis equivalences and felinity definition] The definition of 'felinity' and the claim that any state with non-negligible felinity (or derived poly(n)-weight Dicke states) implies Parity in QAC0 are load-bearing for the state-synthesis extension. Because felinity is an invented quantity, the manuscript must prove that the measure is well-defined, that the reduction from felinity to a high-degree Fourier coefficient preserves the QAC0 model, and that the error terms remain negligible independently of depth.

Authors: Felinity (Definition 4.2) is the maximum absolute expectation of a high-degree parity operator on the prepared state. Lemma 4.3 already shows it lies in [0,1] and is well-defined. The reduction to a non-negligible Fourier coefficient of the preparation circuit's acceptance function follows directly from the definition, and the main theorem then yields Parity in QAC0 while preserving constant depth. We will expand the section with an additional lemma explicitly verifying that all error terms remain negligible for constant-depth circuits and that the QAC0 model is preserved. revision: yes
Referee: [QAC0-Majority correlation construction] The (1-o(1)) correlation with Majority is presented as evidence that Fourier concentration may characterize QAC0 more completely than it does AC0. The circuit construction and the precise correlation calculation must be checked to confirm that the error is o(1) while the circuit depth and gate fan-in remain constant; any hidden dependence on n in the error bound would undermine the claimed separation.

Authors: The construction in Section 5 is a constant-depth, bounded-fan-in QAC0 circuit realizing a quantum approximate majority. The correlation calculation yields 1-O(1/log n), which is o(1), with no n-dependent growth in depth or fan-in. We will insert an expanded calculation subsection with fully explicit bounds to confirm the o(1) claim and rule out hidden dependencies. revision: partial

Circularity Check

0 steps flagged

No circularity: equivalence derived from explicit reduction on circuit and Fourier definitions

full rationale

The paper's central claim reduces the question of PARITY in QAC0 to whether QAC0 circuits are Fourier-concentrated by exhibiting a direct construction: any QAC0 circuit carrying non-negligible mass on high-degree Fourier coefficients yields an exact QAC0 circuit for PARITY. This step is grounded in the definitions of QAC0 circuits and their Fourier spectra rather than any self-referential fit, parameter tuning, or load-bearing self-citation. The converse direction follows from the classical LMN theorem's quantum analog being necessary, again without importing uniqueness from the authors' prior work. The MAJORITY correlation is witnessed by an explicit QAC0 construction, and felinity is introduced as a fresh measure whose non-negligible value is shown to imply the same PARITY circuit via the same reduction; no step renames a known result or smuggles an ansatz through citation. The derivation chain is therefore self-contained against the stated circuit model and analysis tools.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The work rests on the standard definition of QAC0 circuits and the Fourier transform over the hypercube; felinity is introduced as a new quantity without independent evidence outside the paper.

axioms (1)

standard math Standard definitions of QAC0 circuits and the Fourier transform over {0,1}^n
Invoked throughout the abstract to state the equivalence and the majority correlation.

invented entities (1)

felinity no independent evidence
purpose: A new measure of quantum state preparation difficulty that captures states whose synthesis implies Parity in QAC0
Defined in the paper to extend the parity equivalence to GHZ and Dicke states; no external falsifiable prediction is given.

pith-pipeline@v0.9.0 · 5612 in / 1271 out tokens · 42477 ms · 2026-05-13T20:17:16.298429+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

1 extracted references · 1 canonical work pages

[1]

Reducing the complexity of reductions.Computational Complexity, 10(2):117–138, 2001

[AAI+01] Manindra Agrawal, Eric Allender, Russell Impagliazzo, Toniann Pitassi, and Steven Rudich. Reducing the complexity of reductions.Computational Complexity, 10(2):117–138, 2001. [AB09] Sanjeev Arora and Boaz Barak.Computational complexity: a modern approach. Cambridge University Press, 2009. [ABO84] Mikl´ os Ajtai and Michael Ben-Or. A theorem on pr...

work page 2001

[1] [1]

Reducing the complexity of reductions.Computational Complexity, 10(2):117–138, 2001

[AAI+01] Manindra Agrawal, Eric Allender, Russell Impagliazzo, Toniann Pitassi, and Steven Rudich. Reducing the complexity of reductions.Computational Complexity, 10(2):117–138, 2001. [AB09] Sanjeev Arora and Boaz Barak.Computational complexity: a modern approach. Cambridge University Press, 2009. [ABO84] Mikl´ os Ajtai and Michael Ben-Or. A theorem on pr...

work page 2001