Curator's Take
AI Commentary
This article delivers the first systematic analysis of how Hamming‑weight and general symmetric Boolean functions can be computed with provably optimal depth–ancilla tradeoffs across both all‑to‑all and realistic 2‑D grid architectures, showing that O(log n) depth is achievable with sublinear ancillas in the fully connected model and that Θ(√n) depth is unavoidable yet attainable with only polylogarithmic extra qubits on a planar chip. By extending these constructions to constant‑depth dynamic circuits at the cost of modestly super‑linear ancillary space, the work opens a practical pathway for speeding up many higher‑level algorithms—such as quantum counting, amplitude estimation, and error‑correcting syndrome extraction—that rely heavily on symmetric Boolean subroutines. The results also give hardware designers concrete targets for qubit layout and connectivity, highlighting that modest increases in ancilla budget can dramatically shrink circuit depth, a key factor for near‑term fault‑tolerant performance.
— Mark Eatherly
Summary
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(\sqrt n)$ with $O(\log^2 n)$ ancillas, and a matching lower bound showing that $Θ(\sqrt n)$ is optimal. In both dynamic models, we obtain constant-depth circuits with $O(n^{1+\varepsilon}\operatorname{polylog}\,n)$ ancillary qubits for every fixed $\varepsilon>0$. All constructions give a smooth depth-ancilla tradeoff, and they also extend to arbitrary symmetric Boolean functions.