Efficient Depth--Ancilla Tradeoffs for Hamming Weight Computation and Symmetric Boolean Functions
Abstract
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.
Related
- Reducing the cost of ancilla purification for Majorana quantum computation
- Efficient thermalization of one-dimensional noncommuting Hamiltonians via system-bath interactions with Θ(n) ancilla qubits
- Exploiting all ancilla outcomes in linear combinations of unitaries: low-rank recovery and quantum trapdoor functions
- Ancilla-Efficient QSAMPLE Preparation for Reversible Markov Chains
- Efficient quantum Gibbs sampling of stabilizer codes using hybrid computation
BibTeX
@misc{zi2026efficient,
title = {{Efficient Depth--Ancilla Tradeoffs for Hamming Weight Computation and Symmetric Boolean Functions}},
author = {Wei Zi and Pei Yuan and Junhong Nie and Shengyu Zhang},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2608.04627},
eprint = {2608.04627},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.04627},
}
RIS
TY - UNPB
TI - Efficient Depth--Ancilla Tradeoffs for Hamming Weight Computation and Symmetric Boolean Functions
AU - Wei Zi
AU - Pei Yuan
AU - Junhong Nie
AU - Shengyu Zhang
PY - 2026
DA - 2026/08/30
PB - arXiv
DO - 10.48550/arxiv.2608.04627
UR - https://arxiv.org/abs/2608.04627
AB - 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(log^2 n) ancillas, and a matching lower bound showing that Θ(√n) is optimal. In both dynamic models, we obtain constant-depth circuits with O(n^1+ε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.
ER -