Parity QAC0 QAC0 is Fourier-Concentrated
Lucas Gretta, Meghal Gupta, Malvika Raj Joshi
Abstract
A major open problem in understanding shallow quantum circuits (QAC) is whether they can compute Parity. We show that this question is solely about the Fourier spectrum of QAC: any QAC circuit with non-negligible high-level Fourier mass suffices to exactly compute PARITY in QAC. Thus, proving a quantum analog of the seminal LMN theorem for AC is necessary to bound the quantum circuit complexity of PARITY. In the other direction, LMN does not fully capture the limitations of AC. For example, despite MAJORITY having of its weight on low-degree Fourier coefficients, no AC circuit can non-trivially correlate with it. In contrast, we provide a QAC circuit that achieves correlation with MAJORITY, establishing the first average-case decision separation between AC and QAC. This suggests a uniquely quantum phenomenon: unlike in the classical setting, Fourier concentration may largely characterize the power of QAC. PARITY is also known to be equivalent in QAC 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 QAC.
AI Impact Assessments
(3 models)Scientific Impact Assessment
Core Contribution
This paper establishes a striking equivalence: PARITY ∉ QAC⁰ if and only if QAC⁰ circuits are Fourier-concentrated (the "QLMN" conjecture). This transforms a major open problem in quantum complexity theory—whether constant-depth quantum circuits can compute PARITY—into a purely Fourier-analytic question. The equivalence is quantitative: the paper shows that the size/depth lower bounds for PARITY in QAC directly correspond to the decay parameters of Fourier concentration.
The classical analog of this equivalence does not hold: the LMN theorem for AC⁰ is sufficient but not necessary for proving PARITY ∉ AC⁰, since AC⁰ augmented with approximate high-degree functions need not yield AC⁰[2]. The paper exploits a uniquely quantum phenomenon—the "all-or-nothing" behavior of QAC⁰—where any non-negligible high-degree Fourier mass can be bootstrapped to exact PARITY computation.
Methodological Rigor
The technical machinery is well-constructed and the proofs are carefully executed. Key innovations include:
1. Fourier mass to Hamming slice reduction (Lemma 4.1): A clever gadget that converts any QAC⁰ circuit with high-level Fourier mass into a "threshold-block nekomata" state, using the copy-uncompute technique combined with Hadamard transforms. The construction of the extraction vector |T_k⟩ from Fourier coefficients is elegant.
2. Felinity measure: The introduction of F_n(ρ) = 2Σ_y ⟨y|ρ|y⟩·⟨ȳ|ρ|ȳ⟩ is well-motivated. The paper demonstrates its monotonicity, Lipschitz continuity, and—critically—that it precisely captures the Fourier coefficient on the full set: f̂_{C'}([n]) = F_n(ρ_T). This clean connection between a state property and a circuit's correlation with PARITY is the paper's most technically satisfying result.
3. MAJORITY upper bound (Theorem 5.9): The construction achieving (1 - 1/polylog(n)) correlation with MAJORITY uses a "poor man's fanout" that creates weak copies |x_{1/n}⟩⊗n, combined with a weak copy test based on reflections about carefully chosen superpositions of |0^n⟩ and |W_n⟩. The analysis is detailed and the choice of thresholds is carefully optimized.
The proofs build systematically on established techniques (amplitude amplification, Rosenthal's nekomata amplification) while introducing genuinely new ideas at each step. The paper is honest about where prior techniques fall short and clearly delineates its novel contributions.
Potential Impact
Theoretical significance: The equivalence PARITY ∉ QAC⁰ ⟺ QLMN is a conceptual breakthrough that unifies multiple research threads. It tells us that:
QAC⁰_f-completeness results (Theorem 1.3) significantly expand the landscape of problems equivalent to PARITY in QAC⁰. The inclusion of poly-weight Dicke states is particularly notable, as Dicke state preparation is a problem of independent interest in quantum information.
Average-case separation (Theorem 1.4): The first average-case decision separation between AC⁰ and QAC⁰ is a milestone. While prior work established relational and worst-case separations, showing that QAC⁰ can achieve (1-o(1)) correlation with MAJORITY—impossible for AC⁰—is a clean, conceptually compelling result.
Practical implications: The completeness results imply that constructing even a crude approximation to various quantum tasks (weak nekomata, poly-weight Dicke states, non-negligible PARITY correlation) in constant depth would unlock the full power of QAC⁰_f, including modular arithmetic, QFT, and sorting.
Timeliness & Relevance
The paper arrives at an active moment for QAC⁰ research. Recent works (GMW26, JTVW26, JV26, ADOY25) have made rapid progress on both upper and lower bounds. This paper synthesizes and extends these threads, providing a unifying framework. The QLMN conjecture was informally discussed in prior work (NPVY24, ADOY25), but formalizing it and proving its necessity is a substantial advance.
The question of constant-depth quantum circuit power is increasingly relevant as near-term quantum devices operate at shallow depths. Understanding what is achievable in QAC⁰ has implications for quantum advantage demonstrations and circuit compilation.
Strengths & Limitations
Strengths:
Limitations:
Overall Assessment
This is an excellent paper that makes a fundamental conceptual contribution to quantum complexity theory. The equivalence between PARITY hardness and Fourier concentration is the kind of clean, surprising result that reshapes how a community thinks about an open problem. The supporting results (MAJORITY separation, felinity, Dicke state completeness) are individually significant and collectively paint a compelling picture of QAC⁰'s computational landscape.
Generated Apr 6, 2026
Comparison History (69)
Paper 1 provides a realistic experimental pathway to test the quantum nature of gravity—a major unsolved problem in physics—by relaxing the severe constraints of free-fall interferometry. While Paper 2 makes significant theoretical contributions to quantum complexity theory, Paper 1's potential to enable a groundbreaking experiment on quantum gravity promises broader, more transformative impact across fundamental physics.
Paper 2 has higher potential impact due to strong novelty in quantum complexity theory: it reframes the PARITY-in-QAC0 question via Fourier structure, establishes a first average-case decision separation between AC0 and QAC0, and extends equivalences to broad state-synthesis tasks while proposing a new quantitative measure (“felinity”). These results are methodologically rigorous and broadly relevant across quantum computing, circuit complexity, and Fourier analysis, and they target timely central open problems. Paper 1 is valuable and application-driven, but its contribution is a refinement/extension of an existing experimental paradigm with narrower cross-field reach.
Paper 2 addresses a major open problem in quantum complexity theory by linking the computational power of shallow quantum circuits (QAC0) to their Fourier spectrum. It establishes a fundamental average-case separation between classical and quantum circuits and introduces a novel mathematical metric ('felinity'). While Paper 1 presents a highly rigorous experimental milestone in quantum optomechanics, Paper 2 offers profound theoretical insights that will broadly impact our foundational understanding of quantum advantage, circuit capabilities, and state preparation limits, granting it a higher potential for foundational, long-term scientific impact.
Paper 2 addresses a major open problem in quantum complexity theory (whether QAC⁰ can compute Parity) and establishes deep structural connections between Fourier analysis and quantum circuit complexity. It provides the first average-case separation between AC⁰ and QAC⁰, introduces a novel measure (felinity), and connects circuit complexity to quantum state synthesis. These foundational theoretical contributions have broad implications across quantum computing theory, complexity theory, and Fourier analysis. Paper 1, while experimentally impressive (2% optical squeezing via levitated oscillators), represents an incremental advance in optomechanics with modest squeezing levels.
Paper 2 likely has higher impact due to clear experimental advancement with direct relevance to scalable quantum networks: integrating single T centres with p-i-n diodes enabling large Stark tuning, improved resonance yield, and quantified entanglement-rate gains. It is timely for on-chip spin–photon interfaces and has immediate applicability in device engineering and quantum information hardware. Paper 1 is novel and potentially deep for quantum complexity theory, but its impact depends on subsequent breakthroughs on Parity-in-QAC0/quantum LMN-type results and adoption of new metrics, making near-term, broad scientific/technological uptake less certain.
Paper 2 addresses a major open problem in quantum complexity theory, establishing the first average-case decision separation between classical and quantum AC0, and introduces a novel metric ('felinity'). In contrast, while Paper 1 presents a novel quantum decoding technique, it explicitly concludes with a null result regarding quantum advantage, limiting its broad transformative impact compared to the foundational theoretical breakthroughs in Paper 2.
Paper 1 addresses a major open problem in quantum complexity theory (whether QAC⁰ can compute Parity) and establishes a deep structural characterization linking this question to Fourier concentration, provides the first average-case separation between AC⁰ and QAC⁰, and introduces novel measures (felinity) with broad implications. Its results connect multiple areas—circuit complexity, Fourier analysis, and quantum state synthesis—with potential to reshape understanding of shallow quantum circuits. Paper 2 solves an important but more specialized representability problem for non-particle-conserving systems, with narrower immediate impact.
Paper 1 has higher impact potential: it reframes the central open problem PARITY vs QAC0 in terms of Fourier mass, links it to a quantum analogue of LMN, and provides the first average-case decision separation between AC0 and QAC0 via high-correlation MAJORITY—conceptually deep results likely to influence complexity theory and quantum circuits broadly. It also introduces a new state-complexity measure (“felinity”) and extends equivalences to state-synthesis tasks, widening cross-field relevance (circuits, Fourier analysis, quantum information). Paper 2 is timely and applied but reports no quantum advantage, limiting immediate impact.
Paper 1 targets a central open problem in shallow quantum circuit complexity (Parity in QAC0) and reframes it via a Fourier-spectrum equivalence, potentially reshaping how lower bounds for quantum circuits are pursued. It also gives a new average-case separation between AC0 and QAC0 and introduces a novel state metric (“felinity”) tied to broad state-synthesis tasks, connecting complexity, Fourier analysis, and quantum information. Paper 2 is rigorous and application-relevant (explicit integrand classes where QAE wins including oracle cost), but its impact is narrower to quantum algorithms for integration and depends on structured function classes.
Paper 2 targets a central, long-standing open problem in quantum circuit complexity (PARITY vs QAC0) and reframes it via an equivalence to Fourier concentration, potentially redirecting an entire line of lower-bound research. It also gives the first average-case decision separation between AC0 and QAC0 and introduces a new state-synthesis metric (“felinity”) linking complexity, Fourier analysis, and quantum state preparation. While Paper 1 is highly relevant for near-term analog simulators and applications, Paper 2’s conceptual novelty and cross-field theoretical ramifications suggest broader, longer-lasting impact.