{"id":"a9142f6d-0c50-4d70-83e0-21d530fffebe","arxiv_id":"2608.04627","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"New quantum circuits for Hamming weight and symmetric Boolean functions: O(log n) depth with sublinear ancillas (all-to-all), optimal Θ(√n) depth with O(log^2 n) ancillas (2D), and constant depth with O(n^{1+ε}) ancillas (dynamic).","lead":"This paper derives new depth-ancilla tradeoffs for quantum circuits that compute Hamming weight and symmetric Boolean functions. It achieves logarithmic depth with sublinear ancillas on all-to-all hardware, optimal square-root depth with few ancillas on two-dimensional grids, and constant depth with near-linear ancillas when mid-circuit measurement and classical feedforward are allowed.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 4.12's clean decoder cannot preserve the non-orthogonal phase encoding |Φ_R(t)> while writing |t>, so the dynamic constructions' uncompute step fails as written.","rationale":"The single most load-bearing concern is exactly the one identified by the reader: the impossible clean decoder asserted in Lemma 4.12. The paper's dynamic constructions are built on a compute–copy–uncompute pattern that requires the redundant Fourier phase encoding |Φ_R(t)> to survive the decoding step. But the phase states |Φ_R(t)> for different t are not mutually orthogonal, while the output registers |t> are orthogonal. No linear quantum operation can map the non-orthogonal set {|Φ_R(t)>|0^q>} to the orthogonal set {|Φ_R(t)>|t>} while preserving the first factor, because inner products are not preserved. This is an internal inconsistency, not a disagreement with consensus. It directly undermines the proof of the constant-depth dynamic results in both all-to-all and 2D settings, which are part of the central claims of the paper. The standard 2D theorem and the standard all-to-all logarithmic-depth results are independent of this lemma and appear sound; the matching lower bound for 2D is also unaffected. The reader's proposed repair—treating the decoder as destructive and resetting the phase registers by classical corrections—is plausible, and the dynamic claims might be recoverable, but the paper does not supply the repair. Therefore the appropriate verdict is CONDITIONAL: accept only after the clean-decoder step is either replaced by a correct measurement-based reset procedure or dropped from the proof with the resource analysis revised accordingly. This agrees with the reader's verdict and does not change it.","tokens_in":31694,"tokens_out":5383,"duration_ms":63241,"concrete_test":"For R = 2, q = 2, explicitly compute the Gram matrix G(t,t′) = <Φ_R(t)|Φ_R(t′)> from the definitions in Lemma 4.12, and verify G(1,2) ≠ 0. Then compare with the Gram matrix of the claimed outputs, G(t,t′)·δ_{t,t′}, which has off-diagonal entries 0. The mismatch proves that no CPTP map implements the claimed decoder while preserving the phase encoding. As a second check, attempt to replace Lemma 4.12 by a destructive measurement-based decoder that resets the phase registers using classical data, and verify whether the depth and ancilla bounds of Theorems 4.14–4.17 still hold; if the reset requires extra registers or additional depth, the dynamic claims need revision.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The dynamic results (Lemmas 4.13, 4.15–4.18 and Corollaries 4.16–4.18) all invoke Lemma 4.12, which claims a constant-depth map |Φ_R(t)>|0^q> → |Φ_R(t)>|t> that preserves the redundant Fourier phase encoding. This is impossible as a quantum operation. For t ≠ t′, the input inner product <Φ_R(t)|Φ_R(t′)> = ∏_{k=0}^{q-1} ∏_{y∈{0,1}^k} (1 + e^{2πi(t−t′)/2^{k+1}})/2 is nonzero, e.g. for R = 2, q = 2. The claimed output states have inner product <Φ_R(t)|Φ_R(t′)>·<t|t′> = 0 because <t|t′> = 0. A linear (CPTP) map cannot change the Gram matrix of the input subspace in this way; hence no unitary or measurement-based deterministic procedure can implement the claimed transformation on all t and their superpositions. The proof of Lemma 4.12 therefore contains a hidden impossibility. The clean-subroutine step is essential: Lemma 4.13 first prepares the redundant phase states, then decodes S while keeping the encoding, then reverses the phase preparation. If the decoder is destructive and the phase states are measured and reset, the reversal step must be reworked with classical corrections; the paper does not provide this repair. Consequently the constant-depth dynamic Hamming-weight claims, including the near-linear ancilla statement, are not established as written. The standard 2D depth-optimal result (Theorem 4.8) and the standard all-to-all bounds do not rely on Lemma 4.12 and appear unaffected.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies depth-ancilla tradeoffs for Hamming weight computation and symmetric Boolean functions under all-to-all and two-dimensional nearest-neighbor square-grid connectivity, in both the standard and dynamic circuit models. The main results are: in the standard all-to-all model, depth O(log n) with sublinear ancillas; in the standard 2D model, depth O(√n) with O(log^2 n) ancillas and a matching Ω(√n) lower bound; in both dynamic models, constant depth with O(n^{1+ε} polylog n) ancillas for every fixed ε>0, with smooth depth-ancilla tradeoffs and extension to arbitrary symmetric Boolean functions. The constructions are based on blocking, Fourier phase encoding, carry-save summation, measurement-based fan-out, and the Takahashi–Tani decoder.","tokens_in":32035,"tokens_out":30380,"duration_ms":359292,"significance":"If correct, the results are significant: the standard 2D construction is depth-optimal with only polylogarithmic ancillas, and the dynamic results show that mid-circuit measurement and feedforward remove the 2D square-root depth barrier at near-linear ancillary cost. The paper is careful with clean-ancilla accounting, gives explicit layouts for the 2D constructions, and cites external primitives transparently. I also verified the specific concern raised in the review about Lemma 4.12: the states |Φ_R(t)> are not non-orthogonal; for distinct t and t′, the inner product vanishes at k=ν₂(t−t′), so a unitary clean decoder is not ruled out by linearity. The remaining issues are presentation-level and local.","major_comments":[],"minor_comments":[{"comment":"The proof states that a candidate qubit t^y_k is 'extracted' after phase correction, but it does not define the extraction gate or prove that it preserves the phase state; please specify the operation (for example, after correcting to |+⟩/|−⟩, apply H-CNOT-H) and state explicitly that it is unitary and is undone in the clean reversal.","section":"Lemma 4.12"},{"comment":"The sentence 'If temporary registers are produced, we use the standard compute–copy–uncompute procedure' assumes the Takahashi–Tani decoder is reversible on the phase encoding; this is the same property later proved in Lemma 4.12, so please add a cross-reference or a one-sentence justification here.","section":"Lemma 3.3"},{"comment":"It would help to state that the redundant phase states are mutually orthogonal for distinct t (the inner product vanishes at k=ν₂(t−t′)), which is what makes the clean isometry |Φ_R(t)>|0^q⟩ → |Φ_R(t)>|t⟩ possible.","section":"Lemma 4.12"},{"comment":"The proof ignores integer roundings in block sizes; this is standard, but a footnote saying that replacing sizes by ceilings changes only constant factors would improve readability.","section":"Theorem 4.17"},{"comment":"In the constant-bit splitting, please spell out why 2^{m−c+1} ≤ n for a fixed sufficiently large c; this is used to ensure that the borrowed workspace fits in the input register.","section":"Theorem 5.7"}],"recommendation":"minor_revision","confidential_remarks":"The reader's conditional verdict rested on the claim that Lemma 4.12 is impossible because the phase encoding is non-orthogonal. That claim is computationally false: for any distinct t and t′, the factor with k=ν₂(t−t′) in the inner product is zero. I therefore do not see a load-bearing error in the dynamic 2D constructions. The paper is a strong contribution; the requested clarifications in the minor comments are all local and can be addressed in a minor revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The headline: the standard-model results are solid, genuinely new, and worth taking seriously; the dynamic results are plausible and likely correct, and the stress-test's claimed impossibility does not hold up.\n\nWhat is actually new: the blocked all-to-all construction gives O(log n) depth with sublinear ancillas for HWC and symmetric functions, improving on the O(log^2 n) ancilla-free bound by trading a little workspace for logarithmic depth. The 2D result is the cleanest piece: O(sqrt n) depth with O(log^2 n) ancillas on a square grid, with a matching light-cone lower bound. The dynamic constant-depth constructions with near-linear ancillas, if correct, are a substantial improvement over the direct O(n^2) Takahashi-Tani translation. The multi-output phase-gadget lemma and the 2D dynamic layout are real techniques, not just parameter tuning.\n\nOn the stress-test: it claims Lemma 4.12 is impossible because the phase states are non-orthogonal. That is false as stated. For t != t', let d = |t-t'| and k = v_2(d). Since d < 2^q, we have k <= q-1, so the branch (k,y) exists. The factor for that branch is (1 + exp(2 pi i d / 2^{k+1}))/2 = (1 + exp(pi i * odd))/2 = 0. Hence the full inner product <Phi_R(t)|Phi_R(t')> is zero. The states are orthonormal, so a unitary decoder that writes |t> while preserving the encoding is not ruled out by inner-product preservation. The stress-test's small example also miscalculates: for R=2, q=2, t=0,1, the k=0 factor already vanishes. So the main reason for the CONDITIONAL verdict disappears.\n\nRemaining soft spots are minor in comparison. Lemma 4.12 is a high-level layout argument: bands, strips, fan-out intervals, and the claim that everything fits in O(R polylog R) area. That is credible but less formal than the rest of the paper, and a referee should ask for a more precise accounting of the measurement-based fan-out strips and their reversal. The dynamic constructions also rely on reversing circuits that contain mid-circuit measurements; the authors state this is handled by the leaf-recovery procedure, but the clean-subroutine composition deserves explicit proof. The self-citation to [40] is disclosed and used as an external black box, which is fine.\n\nWho this is for: anyone working on quantum arithmetic, shallow-circuit complexity, or NISQ-era depth-ancilla tradeoffs. It deserves a serious referee. I would send it to peer review, with the main request being to expand the dynamic decoder layout and clarify the reversibility of the measurement-based primitives.","headline":"The stress-test's core objection is wrong: the redundant phase states are orthonormal, so Lemma 4.12 is not impossible; the standard-model results are clean and new, and the dynamic constructions are credible but deserve tighter layout analysis.","tokens_in":849,"tokens_out":1149,"would_cite":true,"duration_ms":106316,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q12","81P68"],"pacs":["03.67.Lx"],"model":"deepseek-v4-flash","headline":"The paper establishes depth–ancilla tradeoffs for quantum Hamming weight computation: logarithmic depth with sublinear ancillas under all-to-all connectivity, optimal square-root depth on a 2D grid, and constant depth in dynamic models…","keywords":["Hamming weight computation","symmetric Boolean functions","depth-ancilla tradeoff","dynamic quantum circuits","2D nearest-neighbor architecture","measurement-based fan-out","constant-depth circuits"],"falsifier":"To test the 2D optimality claim, look for a measurement-free nearest-neighbor circuit on a square grid of depth $o(\\sqrt n)$ that computes the parity of all $n$ input bits; since parity is the least significant output bit of Hamming weight, any such circuit falsifies the matching lower bound. For the dynamic clean-subroutine claim, simulate the full compute–copy–uncompute cycle of the $n=4$ dynamic 2D construction on all 16 inputs and check that every ancillary qubit returns to $|0\\rangle$ and the output is exactly $|x|\\rangle$; any dependence on measurement outcomes in the restored registers would falsify the cleanup argument.","tokens_in":31484,"feed_emoji":"🔢","tokens_out":17204,"duration_ms":171261,"temperature":0.7,"pith_summary":"This paper asks how shallow a quantum circuit can be while still exactly computing the Hamming weight of an n-bit string, and how many ancilla qubits that costs under different hardware connectivities. It establishes that in the standard all-to-all model the task can be done in $O(\\log n)$ depth with $o(n)$ ancillas, and that on a two-dimensional nearest-neighbor grid the optimal depth is $\\Theta(\\sqrt n)$, attainable with only $O(\\log^2 n)$ ancillas. In the dynamic circuit model, where mid-circuit measurements and classical feedforward are allowed, the paper claims constant-depth implementations with $O(n^{1+\\varepsilon}\\operatorname{polylog} n)$ ancillas for every fixed $\\varepsilon>0$, in both connectivity models. Because any symmetric Boolean function reduces to computing the Hamming weight and then evaluating a function of that weight, all of these bounds transfer to symmetric functions such as OR, AND, majority, threshold, and parity.","feed_headline":"Quantum Hamming counting hits optimal sqrt(n) depth on 2D chips","feed_subtitle":"Dynamic circuits with mid-circuit measurement reach constant depth using near-linear ancillas.","key_machinery":"The load-bearing reduction is block decomposition into weighted counting: partition the input into blocks of size $B$, compute each local Hamming weight $w_\\ell$, write $w_\\ell=\\sum_j 2^j b_{\\ell,j}$, and reduce the global weight to $\\sum_{\\ell,j} 2^j b_{\\ell,j}$. The standard-model constructions implement local weights with the ancilla-free Fourier phase encoding of [40] and finish the weighted sum with carry-save population counting; the 2D version replaces each phase interaction by a multi-output phase gadget built from dirty fan-out along trees and a cyclic token tour around a corridor, so that one control qubit visits every data qubit exactly once. The dynamic constructions use measurement-based fan-out [2] to build cat states—equal superpositions of all zeros and all ones on the leaf qubits—and weighted controlled-phase gates to accumulate $S=\\sum_i a_i z_i$ in branch-specific phase states $|\\phi_{k,y}(S)\\rangle$, followed by a constant-depth Takahashi–Tani parallel decoder to extract the binary value $|S\\rangle$. The matching lower bound is the parity light cone: in depth $d$ on a 2D grid, the least significant output bit can depend on at most $O(d^2)$ inputs, and since it equals $x_1\\oplus\\cdots\\oplus x_n$, $d=\\Omega(\\sqrt n)$.","core_discovery":"The central discovery is that Hamming weight computation is governed by a simple reduction—block the input, compute local weights, then sum a weighted set of bits—and that each circuit model supplies a different optimal way to carry out the two stages. In the standard all-to-all model, blocking the ancilla-free Fourier-encoding construction of [40] and summing local weights with a carry-save adder yields depth $O(\\log n)$ with sublinear ancillas. In the standard 2D model, the same Fourier encoding is localized by multi-output phase gadgets routed around grid patches, giving depth $O(\\sqrt n)$ with $O(\\log^2 n)$ ancillas; the paper proves this depth is optimal because the least significant output bit is the XOR of all $n$ inputs, so its backward light cone on a 2D grid must have radius $\\Omega(\\sqrt n)$. In both dynamic models, measurement-based fan-out prepares redundant Fourier phase states for the weighted sum, a constant-depth parallel decoder writes out the binary answer, and an $r$-level pyramid of such steps achieves depth $O(r)$ with $O(r n^{1+1/r}\\operatorname{polylog} n)$ ancillas, giving constant depth with near-linear ancillas for fixed $\\varepsilon>0$. The paper claims the same tradeoffs for arbitrary symmetric Boolean oracles by computing $|x|$, evaluating the outer function on the weight register, and uncomputing.","pith_inferences":["A natural next step, suggested by the paper's own open problems, is to convert the dynamic primitives into fault-tolerant circuits and count non-Clifford resources; mid-circuit measurement may reduce $T$-depth as sharply as it reduces ordinary depth, but that is not shown here.","The same block-and-weighted-count decomposition could be applied to other additive aggregates, such as weighted sums, inner products, or low-degree polynomials, giving analogous depth–ancilla tradeoffs in these four models.","If the dynamic decoder turns out to be destructive rather than reversible, the constant-depth cleanup step would need a measurement-based reset with classical corrections; the paper does not supply that repair.","The 2D parity light-cone argument extends to any symmetric function whose value depends on all $n$ inputs, not just parity; the paper states the lower bound for Hamming weight, but the same counting applies to AND, majority, or threshold oracles."],"forward_implications":["On a measurement-free 2D nearest-neighbor chip, Hamming weight computation cannot be made faster than $\\Theta(\\sqrt n)$ depth, so the $O(\\sqrt n)$ construction is optimal up to constants.","Allowing mid-circuit measurements and classical feedforward removes the square-root barrier even when two-qubit gates remain nearest-neighbor: constant-depth Hamming weight circuits exist with $O(n^{1+\\varepsilon}\\operatorname{polylog} n)$ ancillas for every fixed $\\varepsilon>0$.","The $r$-level pyramid gives a smooth depth–ancilla tradeoff: depth $O(r)$ with $O(r n^{1+1/r}\\operatorname{polylog} n)$ ancillas, interpolating between the low-ancilla and low-depth regimes.","Every symmetric Boolean function oracle—majority, threshold, AND, OR, parity—inherits the same four bounds by composing Hamming weight computation with a small Boolean evaluation on the weight register.","In the standard all-to-all model, symmetric Boolean functions gain a logarithmic-depth construction with sublinear ancillas, improving on earlier $O(\\log^2 n)$-depth constructions."],"supporting_citations":[{"why":"Supplies the ancilla-free Fourier phase-encoding construction of Hamming weight that the standard-model block gadgets localize.","marker":"[40]"},{"why":"Supplies the exact constant-depth fan-out counting decoder that the dynamic weighted-counting primitive uses to write out the binary sum.","marker":"[35]"},{"why":"Supplies the constant-depth measurement-based fan-out primitive used to prepare cat states and copy values across rows and corridors in the dynamic constructions.","marker":"[2]"},{"why":"Supplies the carry-save (Wallace-tree) population-count summation used to finish the weighted sum in the standard models.","marker":"[10]"},{"why":"Supplies the light-cone and parallel-computation framework that underlies the 2D lower bound on parity.","marker":"[27]"},{"why":"Supplies the nearest-neighbor two-dimensional light-cone lower bound used to show $\\Theta(\\sqrt n)$ is optimal.","marker":"[33]"},{"why":"Supplies the X-basis recovery procedure that restores fan-out roots after measurement-based copies in the dynamic cleanup steps.","marker":"[39]"}],"fun_headline_variants":["Optimal sqrt(n) depth for Hamming weight on 2D grids","Dynamic circuits yield constant-depth Hamming weight with many ancillas","Depth-ancilla tradeoffs for symmetric Boolean functions settled","Quantum Hamming weight: optimal depth on 2D, constant with dynamic"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The constant-depth dynamic results depend on being able to undo every measurement-based primitive after its output has been copied, so that all phase and workspace registers return exactly to their initial states; a decoder or fan-out gadget that can only be run destructively would break the cleanup step and require a different construction.","fun_headline_variants_meta":{"raw":{"variants":["Optimal sqrt(n) depth for Hamming weight on 2D grids","Dynamic circuits yield constant-depth Hamming weight with many ancillas","Depth-ancilla tradeoffs for symmetric Boolean functions settled","Quantum Hamming weight: optimal depth on 2D, constant with dynamic"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000816,"raw_usage":{"total_tokens":3638,"prompt_tokens":1072,"completion_tokens":2566,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":688,"completion_tokens_details":{"reasoning_tokens":2490}},"tokens_in":688,"tokens_out":2566,"duration_ms":19079,"temperature":1.0,"reasoning_tokens":2490,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T20:30:36.512550+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"To test the 2D optimality claim, look for a measurement-free nearest-neighbor circuit on a square grid of depth $o(\\sqrt n)$ that computes the parity of all $n$ input bits; since parity is the least significant output bit of Hamming weight, any such circuit falsifies the matching lower bound. For the dynamic clean-subroutine claim, simulate the full compute–copy–uncompute cycle of the $n=4$ dynamic 2D construction on all 16 inputs and check that every ancillary qubit returns to $|0\\rangle$ and the output is exactly $|x|\\rangle$; any dependence on measurement outcomes in the restored registers would falsify the cleanup argument.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the ancilla-free Fourier phase-encoding construction of Hamming weight that the standard-model block gadgets localize."},{"cited_title":"Rosenbaum","cited_arxiv_id":null,"evidence_quote":"Supplies the nearest-neighbor two-dimensional light-cone lower bound used to show $\\Theta(\\sqrt n)$ is optimal."}],"review_version":1}