{"id":"94d4b75b-c4d8-4067-ae78-daedb688d15f","arxiv_id":"2604.02793","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Parity is in QAC0 exactly when QAC0 is not Fourier-concentrated, with a QAC0 circuit achieving (1-o(1)) correlation with Majority and felinity characterizing states whose preparation implies Parity in QAC0.","lead":"This paper shows that whether shallow quantum circuits can compute the parity function depends entirely on whether their Fourier spectra are concentrated on low degrees. It also gives a quantum circuit that correlates almost perfectly with the majority function, unlike any classical shallow circuit, and introduces a new measure called felinity for certain quantum states.","discovery_kind":"unification","skeptic_critique":{"model":"grok-4.3","headline":"Reduction from high-degree Fourier mass to exact PARITY circuit may introduce depth or error that exits QAC0","rationale":"The reader’s weakest assumption correctly isolates the place where the quantum-to-classical Fourier transfer must be justified. Because the manuscript supplies an explicit reduction rather than an existence argument, the load-bearing step is precisely whether that reduction stays inside constant depth; confirming or refuting it on the GHZ example settles the claim without needing the full LMN-style concentration theorem.","tokens_in":1782,"tokens_out":414,"duration_ms":29002,"concrete_test":"Locate the lemma that converts a QAC0 circuit C with |ˆf(ω)| ≥ ε for some |ω| = Ω(n) into a PARITY circuit; instantiate it on the explicit n-qubit circuit that prepares the GHZ state (known to be QAC0-equivalent to PARITY) and verify that the output circuit depth remains O(1) independent of n and ε while the acceptance probability for PARITY equals 1 exactly (not 1-o(1)).","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central claim equates PARITY ∉ QAC0 with Fourier concentration of QAC0. One direction requires that any QAC0 circuit whose output distribution (or acceptance function) carries non-negligible mass on degree-Ω(n) Fourier coefficients can be turned into an exact QAC0 circuit for PARITY. The reduction is asserted to be direct, yet QAC0 circuits are constant-depth with bounded fan-in gates; extracting or amplifying a single high-degree coefficient typically requires either (a) a depth-dependent number of queries to the circuit or (b) an approximation whose error must be driven below 1/poly(n) while preserving constant depth. Neither step is obviously QAC0-closed. If the construction uses classical-style low-degree truncation or random restrictions, the quantum measurement statistics may accumulate coherent errors that the paper’s error analysis does not bound independently of depth.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","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.","tokens_in":1963,"tokens_out":829,"duration_ms":34021,"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":[{"comment":"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.","section":"Main equivalence (abstract and § on Fourier-to-Parity reduction)"},{"comment":"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.","section":"State-synthesis equivalences and felinity definition"},{"comment":"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.","section":"QAC0-Majority correlation construction"}],"minor_comments":[{"comment":"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.","section":"Abstract and definitions"},{"comment":"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.","section":"Fourier analysis section"}],"recommendation":"major_revision","confidential_remarks":"The introduction of an entirely new measure (felinity) whose only purpose is to recover the Parity equivalence raises a scope question for a journal whose primary focus is quantum complexity; the editor may wish to ask whether the same separation can be obtained with existing distance measures before accepting the new terminology."},"author_rebuttal":{"model":"grok-4.3","summary":"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.","responses":[{"response":"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_made":"yes","referee_comment":"[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."},{"response":"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_made":"yes","referee_comment":"[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."},{"response":"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_made":"partial","referee_comment":"[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."}],"tokens_in":1733,"tokens_out":745,"duration_ms":41879,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","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.","headline":"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.","tokens_in":2423,"tokens_out":372,"would_cite":false,"duration_ms":26009,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":{"model":"grok-4.3","evidence":[],"headline":"QAC0 Fourier analysis and PARITY reductions unrelated to recognition-cost or φ-ladder structure","alignment":"orthogonal","rationale":"The paper's central results equate PARITY ∉ QAC0 with Fourier concentration of single-output QAC0 circuits (via W≥k[fC] mass and reductions through nekomata-like states, felinity, and Dicke-state fidelity) and give an average-case MAJORITY separation. None of this machinery invokes the reciprocal cost J(x) = ½(x + x⁻¹) − 1, golden-ratio fixed points, 8-tick periodicity, or the parameter-free forcing chain from a single distinction. The relevant RS modules (Cost.FunctionalEquation, Foundation.RealityFromDistinction, Foundation.AlexanderDuality) therefore neither confirm nor contradict the claims; the work lies in a domain RS does not address.","tokens_in":67688,"confidence":"high","tokens_out":200,"duration_ms":10819,"cache_read_input_tokens":32896,"cache_creation_input_tokens":0},"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"QAC0 computes Parity exactly when its circuits carry non-negligible high-degree Fourier mass.","keywords":["QAC0","Parity","Fourier spectrum","Majority","felinity","quantum circuits","state preparation","GHZ states"],"falsifier":"Exhibiting a QAC0 circuit whose Fourier transform has inverse-polynomial mass above degree polylog(n) would immediately produce an exact QAC0 circuit for Parity.","tokens_in":2689,"feed_emoji":"⚛️","tokens_out":518,"duration_ms":34114,"temperature":0.7,"pith_summary":"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.","feed_headline":"QAC0 computes Parity exactly when it has high Fourier mass","feed_subtitle":"The equivalence shows a quantum LMN theorem would separate Parity from QAC0 and yields a QAC0 circuit that correlates with Majority unlike古典","key_machinery":"The reduction that turns non-negligible high-degree Fourier mass in a QAC0 circuit into an exact QAC0 circuit for Parity.","core_discovery":"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.","pith_inferences":[],"forward_implications":[],"fun_headline_variants":["QAC0 Parity hinges on high Fourier mass","Parity in QAC0 iff QAC0 not Fourier concentrated","Non-concentrated Fourier spectrum enables QAC0 Parity","QAC0 Fourier mass decides exact Parity computation","High Fourier levels in QAC0 compute Parity exactly"],"cache_read_input_tokens":64,"weakest_assumption_plain":"High-degree Fourier mass in a QAC0 circuit can be converted into an exact Parity circuit without further assumptions on the circuit structure.","fun_headline_variants_meta":{"raw":{"variants":["QAC0 Parity hinges on high Fourier mass","Parity in QAC0 iff QAC0 not Fourier concentrated","Non-concentrated Fourier spectrum enables QAC0 Parity","QAC0 Fourier mass decides exact Parity computation","High Fourier levels in QAC0 compute Parity exactly"]},"model":"grok-4.3","cost_usd":0.004416,"raw_usage":{"total_tokens":2271,"prompt_tokens":794,"num_sources_used":0,"completion_tokens":76,"cost_in_usd_ticks":44162000,"prompt_tokens_details":{"text_tokens":794,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":1401,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":794,"tokens_out":76,"duration_ms":26143,"temperature":1.0,"reasoning_tokens":1401,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-05-13T20:17:16.298429+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"Exhibiting a QAC0 circuit whose Fourier transform has inverse-polynomial mass above degree polylog(n) would immediately produce an exact QAC0 circuit for Parity.","supporting_citations":[],"review_version":1}