REVIEW
Exact quantum Hamming-weight computation at optimal depth and minimum width
Quantum Physics · Submitted 18 Oct 2026 · 25 references
Pith's verdict: This paper resolves a clean open problem: exact Hamming-weight computation with optimal depth and minimal width. The constructions are rigorous and the pipelined Fourier addition is genuinely new. The main caveat is the reliance on all-to-all connectivity, which is standard in complexity theory but limits direct application on near-term devices.
Why Pith says this
Highlight any text to comment on it.
Referee report
The paper
The paper claims
This paper proves that an exact quantum circuit can compute the Hamming weight of n bits using only n input qubits and log n output qubits, with depth O(log n) and size O(n log n), both optimal.
The reading
What carries the argument
The central mechanism is the simultaneous modular addition (Lemma 1), which uses a binary tree of m-qubit registers. The construction first applies bottom-up subtractions to cancel the initial values of target registers, then top-down additions to propagate the source value to all targets. This is implemented via a pipelined Fourier schedule (Lemma 4) that decodes bits sequentially while supplying phase gates to children, overlapping operations across tree levels so that total depth is O(m + log r) rather than O(m log r). The schedule alternates Hadamards between neighboring non-root levels and uses a two-round spacing between successive decoded bits, ensuring constant-depth logical rounds.
Extended reading notes
Core claim
The paper proves Theorem 1: for any n, there exists an exact unitary circuit mapping |x⟩_X |0^m⟩_W to |x⟩_X | |x| ⟩_W, where m = ⌈log₂(n+1)⌉, using depth O(log n), size O(n log n), and no qubits beyond the n input qubits and the m output qubits. The depth is optimal because the least significant output bit computes parity, which requires at least ⌈log₂ n⌉ depth. The width is optimal because the output register must distinguish n+1 values. The circuit uses all-to-all connectivity and arbitrary one-qubit gates and CNOTs. The key technical ingredient is a simultaneous modular addition primitive (Lemma 1) implemented by a pipelined Fourier schedule on a binary tree, which overlaps addition and decoding across tree levels to achieve depth O(log n) without additional workspace.
Load-bearing premise
The pipeline schedule for the path-sum permutation assumes that controlled-phase gates between any pair of qubits can be executed in constant depth, which requires all-to-all connectivity and constant-duration gates; any deviation from this gate model would break the depth bound.
Editorial extensions
If this is right
- Exact circuits for every symmetric Boolean function are obtained with depth O(log n) and size O(n log n) using only m clean ancillary qubits, which is optimal in the worst case.
- The counter enables Hamming-weight measurements with only m ancillary qubits, improving the expected depth of measurement-assisted balanced Dicke-state preparation from O(log³ n) to O(log² n).
- Unitary Dicke-state preparation for any fixed classical weight k (1 ≤ k ≤ n-1) becomes possible in depth O(r^{1/4} log n) with r = min(k, n-k), using m ancillary qubits, through exact weight-selective reflections.
- The construction proves that the depth–space trade-off for exact Hamming-weight computation is fully characterized, with both depth and width achieving lower bounds.
Reading between the lines
- The pipelined tree technique may generalize to other reversible computations that require accumulating contributions from disjoint blocks using borrowed workspace, offering a template for space-optimal shallow circuits beyond counting.
- The size O(n log n) may not be optimal; achieving size O(n) while retaining depth O(log n) and minimum width is an open problem that the authors explicitly identify.
- All-to-all connectivity is assumed; applying these results to restricted architectures (e.g., nearest-neighbor) would likely require additional routing overhead, potentially increasing depth by a connectivity-dependent factor.
- The same construction could be adapted to compute weighted sums or other linear functions with similar resource bounds, provided the Fourier phases are adjusted accordingly.
Original abstract
Hamming-weight computation and symmetric Boolean functions are basic primitives for quantum arithmetic and state preparation, where circuit depth and qubit overhead matter. We construct an exact circuit computing the Hamming weight of an $n$-qubit register with depth $O(\log n)$ and size $O(n\log n)$, using only the $n$ input qubits and $m=\lceil\log_2(n+1)\rceil$ binary output qubits. The circuit uses arbitrary one-qubit gates and CNOTs with all-to-all connectivity. Both depth and total width are optimal. Our constructions combine tree structures and pipelining, temporarily using input qubits as workspace. We also give exact circuits for every symmetric Boolean function with the same depth and size bounds, using only $m$ ancillary qubits returned to zero. Finally, we apply the counter to exact preparation of balanced Dicke states for even $n$. With only $O(\log n)$ ancillary qubits, we obtain expected depth $O(\log^2 n)$ using measurements and classical feedforward, and depth $O(n^{1/4}\log n)$ using unitary gates alone.
The compiled record
The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
The abstract, sentence by sentence
Hamming-weight computation and symmetric Boolean functions are basic primitives for quantum arithmetic and state preparation, where circuit depth and qubit overhead matter. We construct an exact circuit computing the Hamming weight of an $n$-qubit register with depth $O(\log n)$ and size $O(n\log n)$, using only the $n$ input qubits and $m=\lceil\log_2(n+1)\rceil$ binary output qubits. The circuit uses arbitrary one-qubit gates and CNOTs with all-to-all connectivity. Both depth and total width are optimal. Our constructions combine tree structures and pipelining, temporarily using input qubits as workspace. We also give exact circuits for every symmetric Boolean function with the same depth and size bounds, using only $m$ ancillary qubits returned to zero. Finally, we apply the counter to exact preparation of balanced Dicke states for even $n$. With only $O(\log n)$ ancillary qubits, we obtain expected depth $O(\log^2 n)$ using measurements and classical feedforward, and depth $O(n^{1/4}\log n)$ using unitary gates alone.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | Hamming-weight computation and symmetric Boolean functions are basic primitives for quantum arithmetic and state preparation, where circuit depth and qubit overhead matter. | background 1.00 | 0.05 | 0.04 | asserted 1.00 |
| s1 | We construct an exact circuit computing the Hamming weight of an $n$-qubit register with depth $O(\log n)$ and size $O(n\log n)$, using only the $n$ input qubits and $m=\lceil\log_2(n+1)\rceil$ binary output qubits. | contribution 0.86 | 0.96 | 0.73 | asserted 1.00 |
| s2 | The circuit uses arbitrary one-qubit gates and CNOTs with all-to-all connectivity. | method 0.95 | 0.79 | 0.05 | asserted 1.00 |
| s3 | Both depth and total width are optimal. | result 0.87 | 0.87 | 0.49 | asserted 1.00 |
| s4 | Our constructions combine tree structures and pipelining, temporarily using input qubits as workspace. | method 1.00 | 0.94 | 0.06 | asserted 1.00 |
| s5 | We also give exact circuits for every symmetric Boolean function with the same depth and size bounds, using only $m$ ancillary qubits returned to zero. | contribution 0.89 | 0.95 | 0.14 | asserted 1.00 |
| s6 | Finally, we apply the counter to exact preparation of balanced Dicke states for even $n$. | contribution 0.83 | 0.93 | 0.05 | asserted 1.00 |
| s7 | With only $O(\log n)$ ancillary qubits, we obtain expected depth $O(\log^2 n)$ using measurements and classical feedforward, and depth $O(n^{1/4}\log n)$ using unitary gates alone. | result 0.62 | 0.90 | 0.09 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
Figures
Figures reproduced from arXiv:2610.25315 by the authors.
References
Discussion
Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.