2026/08/05 by Wei Zi, Pei Yuan, Junhong Nie +1
Physics and Astronomy · #quant-ph
38 pages
arxiv created 2026/08/05 · arxiv updated 2026/08/06
Hamming weight computation maps an n-bit input to the number of ones it contains. It is a basic subroutine in quantum computing, and the core building block for symmetric Boolean functions, whose value depends only on the Hamming weight of the input. Moreover, symmetric Boolean functions are among the most common primitives in quantum computing. Efficient circuits for both problems are therefore important for the efficiency of many quantum algorithms. We study the depth-ancilla tradeoffs of Hamming weight computation under two qubit connectivity models, all-to-all and two-dimensional nearest-neighbor square grid (2D), in both the standard and dynamic circuit models. In the standard all-to-all model, we obtain depth O(log n) with a sublinear number of ancillas. In the standard 2D model, we give a circuit of depth O(√ n) with O(log2 n) ancillas, and a matching lower bound showing that Θ(√ n) is optimal. In both dynamic models, we obtain constant-depth circuits with O(n1+εpolylog n) ancillary qubits for every fixed ε>0. All constructions give a smooth depth-ancilla tradeoff, and they also extend to arbitrary symmetric Boolean functions.