Efficient Depth--Ancilla Tradeoffs for Hamming Weight Computation and Symmetric Boolean Functions

• URL: http://arxiv.org/abs/2608.04627v1
• Date: Wed, 05 Aug 2026 09:42:03 GMT
• Title: Efficient Depth--Ancilla Tradeoffs for Hamming Weight Computation and Symmetric Boolean Functions
• Abstract summary: Hamming weight maps an $n$-bit input to the number of ones it contains.<n> symmetric Boolean functions are among the most common primitives in quantum computing.<n> Efficient circuits for both problems are important for the efficiency of many quantum algorithms.
• Score: 8.46046792536661
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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(\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.

Related papers

• Two-Tower Quantum Matrix Chain Multiplication: Trading Qubits for Depth [73.08853228981701]
  Matrix chain multiplication is a problem in scientific computing, machine learning, and graph analysis.<n>We present emphTwo-Tower Matrix, a quantum subroutine that encodes the product $mathcalW$ of the $K$ matrices into a quantum state in circuit depth.
  arXiv  Detail & Related papers  (2026-07-14T18:42:40Z)
• A Polylogarithmic-Depth Quantum Multiplier [0.0]
  We present a quantum algorithm for multiplying two $n$-bit integers with overall circuit depth and $T$-depth.<n>Our construction generates partial products via indicator-controlled copying and adds them using a binary adder tree.
  arXiv  Detail & Related papers  (2026-04-10T19:21:07Z)
• Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation [47.600794349481966]
  In this work, we present a quantum algorithm which approximates values up to additive error $epsilonDelta_k$ using a logarithmic number of qubits.<n>A key technical step in the analysis is the preparation of a suitable random initial state, which ultimately allows us to efficiently count the number of eigenvalues that are smaller than a threshold.
  arXiv  Detail & Related papers  (2025-08-28T17:04:18Z)
• Depth-Efficient Quantum Circuit Synthesis for Deterministic Dicke State Preparation [5.755460769073285]
  Dicke states represent an important class of entangled quantum states with broad applications in quantum computing.<n>We propose deterministic quantum circuits for Dicke state preparation under two commonly seen qubit connectivity constraints.
  arXiv  Detail & Related papers  (2025-05-21T11:55:17Z)
• Quantum oracles for the finite element method [45.200826131319815]
  This study examines the quantum routines required for the implementation of oracles used in the block-encoding of the $N times N stiffness and mass matrices.<n>We show how to construct the necessary oracles, which require the calculation of element geometry, square root and the implementation of conditional operations.
  arXiv  Detail & Related papers  (2025-04-28T14:28:31Z)
• Logarithmic-Depth Quantum Circuits for Hamming Weight Projections [3.481985817302898]
  We propose several quantum algorithms that realize a coherent Hamming weight projective measurement on an input pure state. We analyze a depth-width trade-off for the corresponding quantum circuits, allowing for a depth reduction of the circuits at the cost of more control qubits.
  arXiv  Detail & Related papers  (2024-04-10T16:35:36Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$. We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM) Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
  arXiv  Detail & Related papers  (2022-06-07T18:00:01Z)
• Exponential Lower Bounds for Threshold Circuits of Sub-Linear Depth and Energy [0.0]
  We prove that any threshold circuit $C$ of size $s$, depth $d$, energy $e$ and weight $w$ satisfies $log (rk(M_C)) le ed. For other models of neural networks such as a discretized ReLE circuits and decretized sigmoid circuits, we prove that a similar inequality also holds for a discretized circuit $C$.
  arXiv  Detail & Related papers  (2021-07-01T05:37:53Z)
• Quantum-classical algorithms for skewed linear systems with optimized Hadamard test [10.386115383285288]
  We discuss hybrid quantum-classical algorithms for skewed linear systems for over-determined and under-determined cases. Our input model is such that the columns or rows of the matrix defining the linear system are given via quantum circuits of poly-logarithmic depth. We present an algorithm for the special case of a factorized linear system with run time poly-logarithmic in the respective dimensions.
  arXiv  Detail & Related papers  (2020-09-28T12:59:27Z)
• Quantum Algorithms for Simulating the Lattice Schwinger Model [63.18141027763459]
  We give scalable, explicit digital quantum algorithms to simulate the lattice Schwinger model in both NISQ and fault-tolerant settings. In lattice units, we find a Schwinger model on $N/2$ physical sites with coupling constant $x-1/2$ and electric field cutoff $x-1/2Lambda$. We estimate observables which we cost in both the NISQ and fault-tolerant settings by assuming a simple target observable---the mean pair density.
  arXiv  Detail & Related papers  (2020-02-25T19:18:36Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.