Exact quantum Hamming-weight computation at optimal depth and minimum width
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(nlog n), using only the n input qubits and m=⌈log2(n+1)⌉ 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(log2 n) using measurements and classical feedforward, and depth O(n1/4log n) using unitary gates alone.
Related
- Doubly-polylog-time-overhead fault-tolerant quantum computation by a polylog-time parallel minimum-weight perfect matching decoder
- Efficient Depth--Ancilla Tradeoffs for Hamming Weight Computation and Symmetric Boolean Functions
- Effects of Trotter Error, Digitization Error, and Initial State Overlap on Tapered Quantum Phase Estimation for Minimum Eigenvalue Computation
- Warm-Start Quantum Computation: Spectral-Weight Resources for Energy Readout and State Preparation
- Optimal Fusion Strategies for Quantum Computation
BibTeX
@misc{zi2026exact,
title = {{Exact quantum Hamming-weight computation at optimal depth and minimum width}},
author = {Wei Zi and Pei Yuan and Junhong Nie},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.25315},
eprint = {2610.25315},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.25315},
}
RIS
TY - UNPB
TI - Exact quantum Hamming-weight computation at optimal depth and minimum width
AU - Wei Zi
AU - Pei Yuan
AU - Junhong Nie
PY - 2026
DA - 2026/10/18
PB - arXiv
DO - 10.48550/arxiv.2610.25315
UR - https://arxiv.org/abs/2610.25315
AB - 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(nlog n), using only the n input qubits and m=⌈log_2(n+1)⌉ 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/4log n) using unitary gates alone.
ER -