Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.25315

Exact quantum Hamming-weight computation at optimal depth and minimum width

Wei Zi, Pei Yuan, Junhong Nie

quant-phSubmitted Oct 18, 2026• Announced Oct 20, 2026• 0 citations
arXivHTMLPDF

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(n\log n)$, using only the $n$ input qubits and $m=\lceil\log_2(n+1)\rceil$ 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/4}\log n)$ using unitary gates alone.

AI Summary

The paper asks whether coherent Hamming-weight computation can simultaneously attain logarithmic depth and minimum width. It constructs an exact map $|x\rangle|0^m\rangle\mapsto|x\rangle||x|\rangle$, with $m=\lceil\log_2(n+1)\rceil$, depth $O(\log n)$, size $O(n\log n)$, and no qubits beyond the input and binary output registers. Width is minimal for this interface, and the parity output gives an $\Omega(\log n)$ depth lower bound. The model permits arbitrary one-qubit gates and CNOTs, all-to-all connectivity, and no measurements. The main primitive adds one $m$-bit source register to $r$ arbitrary target registers in depth $O(m+\log r)$ and size $O(rm^2)$ without extra workspace. Two tree traversals cancel unwanted initial target values; pipelined Fourier addition overlaps tree levels. Counting then borrows input blocks as dirty workspace, accumulates weight-dependent phases through addition–phase cancellation, restores the borrowed inputs, and applies an inverse Fourier transform. A separate dirty-workspace routing construction yields exact evaluation of every symmetric Boolean function with depth $O(\log n)$, size $O(n\log n)$, and $m$ clean ancillas returned to zero. Applications give exact balanced Dicke-state preparation with expected depth $O(\log^2 n)$ using measurements and feedforward, and exact unitary preparation at depth $O(r^{1/4}\log n)$, where $r=\min\{k,n-k\}$, using $m$ ancillas. These adapt existing preparation strategies. Adaptive depth excludes classical latency; unitary preparation assumes fixed classical weight. Restricted connectivity and fault-tolerant rotation synthesis are not costed, and linear-size counting remains open.

No sign of AI-generated text

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
17 pages

Related papers

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

Wei Zi, Pei Yuan, Junhong Nie +1 more

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.

quant-pharXiv:2608.04627•Aug 6, 2026•1 citation

Efficient circuits for leaf-separable state preparation

Sunil Vittal, Anthony Wilkie, Nika Rastegari +2 more

Efficient state preparation is a challenging and important problem in quantum computing. In this work, we present a recursive state preparation algorithm that combines logarithmic-depth Dicke state circuits with Hamming weight encoders for efficiently preparing ``leaf-separable" quantum states. The algorithm is built on binary partition trees, generalized weight distribution blocks (gWDBs), and leaf-level encoders. We evaluate the performance of the algorithm by numerically simulating it on randomly generated target states with between 4 and 15 qubits. Compared to general state preparation approaches which require $O(2^n)$ CX gates, our algorithm achieves a circuit depth of $O(k\log\frac{n}{k} + 2^k)$ and uses $O(n(k+2^k))$ two-qubit gates, where $k < n$ denotes the subtree size. We also compare implementations of the algorithm with and without the use of ancilla qubits, providing a detailed analysis of the trade-offs in circuit depth and two-qubit gate counts. These results contribute to scalable state preparation for quantum algorithms that require structured inputs such as Dicke or near-Dicke states.

quant-pharXiv:2511.11227•Nov 17, 2025•2 citations

Shallow Quantum Circuit Implementation of Symmetric Functions With Limited Ancillary Qubits

Wei Zi, Junhong Nie, Xiaoming Sun

Optimizing the depth and number of ancillary qubits in quantum circuits is crucial in quantum computation, given the limitations imposed by current quantum devices. In this article, we introduce an innovative approach for implementing arbitrary symmetric Boolean functions using poly-logarithmic depth quantum circuits with only a logarithmic number of ancillary qubits. Symmetric functions are those whose outputs are dictated solely by the Hamming weight of the inputs. These functions find applications across various domains, including quantum machine learning and arithmetic circuit synthesis. Moreover, by fully leveraging the potential of qutrits, the ancilla count can be further reduced to just one. The key technique involves a novel poly-logarithmic depth quantum circuit designed to compute Hamming weight without the need for ancillary qubits. This quantum circuit for Hamming weight is of independent interest due to its wide-ranging applications, such as in quantum memory, quantum machine learning, and Hamiltonian dynamics simulations.

arXiv:2404.06052•IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems•Feb 5, 2025•12 citations

Logarithmic-depth quantum circuits for Hamming weight projections

Soorya Rethinasamy, Margarite L. LaBorde, Mark M. Wilde

A pure state of fixed Hamming weight is a superposition of computational basis states such that each bitstring in the superposition has the same number of ones. Given a Hilbert space of the form $\mathcal{H}={({\mathbb{C}}_{2})}^{\ensuremath{\bigotimes}n}$, or an $n$-qubit system, the identity operator can be decomposed as a sum of projectors onto subspaces of fixed Hamming weight. In this work, we propose several quantum algorithms that realize a coherent Hamming weight projective measurement on an input pure state, meaning that the post-measurement state of the algorithm is the projection of the input state onto the corresponding subspace of fixed Hamming weight. We analyze a depth-width tradeoff for the corresponding quantum circuits, allowing for a depth reduction of the circuits at the cost of more control qubits. For an $n$-qubit input, the depth-optimal algorithm uses $\mathcal{O}(n)$ control qubits and the corresponding circuit has depth $\mathcal{O}(log(n))$, assuming that we have the ability to perform qubit resets. Furthermore, the proposed algorithm construction uses only one- and two-qubit gates.

arXiv:2404.07151•Physical Review A•Nov 1, 2024•11 citations

The power of constant-depth quantum circuits of unbounded size

Sergii Strelchuk, Sathyawageeswar Subramanian, Máté Weisz

Classical circuits with unbounded fan-in can compute any Boolean function in constant depth when their size is unrestricted. We ask whether removing the restrictions on circuit size and ancillary qubits also allows quantum circuits built from arbitrary single-qubit gates and generalised Toffoli gates to implement every unitary in constant depth. We give exact constant-depth constructions for arbitrary permutations of computational basis states, diagonal unitaries and the preparation of arbitrary pure states. These connect quantum state preparation to reversible classical computation and the preparation of probability distributions. With fanout in the gate set, they use exponentially many gates and ancillary qubits and return all ancillary qubits to zero. Replacing fanout by an exact circuit over the original gate set preserves constant depth, although the size bounds can become doubly exponential. The implementation of arbitrary unitaries in constant depth remains open. We give equivalent formulations in terms of copying the vectors of a specified orthonormal basis, extracting their labels and implementing restricted families of unitaries. We also reduce arbitrary unitary implementation to that of traceless unitary involutions using one additional clean qubit. With adaptive measurements, gate teleportation gives depth proportional to the level of a gate in the Clifford hierarchy. Towards arbitrary unitary implementation in constant depth, we use port-based teleportation: for input dimension $d$ and $M\geq d^2-1$ ports, we construct a unitary circuit of depth $O(\sqrt d)$, independent of $M$ and including resource preparation and port selection, with entanglement fidelity at least $(1-(d^2-1)/(2M))^2$. Thus, at fixed $d$, the approximation can be made arbitrarily accurate without increasing depth. Whether the dependence on $d$ can also be removed remains open.

quant-pharXiv:2609.40294•Oct 1, 2026•2 citations

Polylogarithmic-Weight Dicke States in QAC$^0$ and Arbitrary Symmetric States in QAC$^0_f$

Lucas Gretta, Meghal Gupta, Malvika Raj Joshi

An $n$-qubit Dicke state of weight $k$, is the uniform superposition over all $n$-bit strings of Hamming weight $k$. Dicke states are central to quantum algorithms exhibiting speedups, such as Decoded Quantum Interferometry (Jordan et al., \emph{Nature}, 2025). In the NISQ era, quantum hardware is constrained by both depth and locality, motivating the question of which global operations suffice to prepare such states. QAC$^0$, the quantum analogue of AC$^0$, minimally extends local $O(1)$-depth quantum circuits by allowing arbitrary-width Toffoli (reversible AND) gates. We show that Dicke states of $\mathrm{polylog}(n)$ weight can be prepared in QAC$^0$. This gives the first QAC$^0$ construction of any super-constant-weight $n$-qubit Dicke state, since previous constructions relied on the much more powerful FANOUT$_n$ gate. In general, we show that any weight-$k$ Dicke state can be constructed using FANOUT$_{\min(k,n-k)}$ gates. Combined with recent hardness results, this yields a tight characterization: for $k \leq n/2$, a $n$-qubit weight-$k$ Dicke state can be prepared in QAC$^0$ if and only if FANOUT$_k$ $\in$ QAC$^0$. We develop a limited-fanout state-synthesis toolkit for QAC$^0$ that yields further constant-depth, poly$(n)$-ancilla constructions: 1. Every $n$-qubit symmetric state supported on Hamming weight $\leq k$ can be prepared using FANOUT$_k$ gates. 2. Every $O(\log n)$-qubit state can be prepared using quantum random-access memory (QRAM$_n$), which refers to a coherent indexing gate. QRAM$_n$ is a potentially weaker resource than FANOUT$_n$ and can be implemented in QAC$^0_f$.

quant-pharXiv:2604.15298•Apr 17, 2026•5 citations
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 nnn-qubit register with depth O(log⁡n)O(\log n)O(logn) and size O(nlog⁡n)O(n\log n)O(nlogn), using only the nnn input qubits and m=⌈log⁡2(n+1)⌉m=\lceil\log_2(n+1)\rceilm=⌈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 mmm ancillary qubits returned to zero. Finally, we apply the counter to exact preparation of balanced Dicke states for even nnn. With only O(log⁡n)O(\log n)O(logn) ancillary qubits, we obtain expected depth O(log⁡2n)O(\log^2 n)O(log2n) using measurements and classical feedforward, and depth O(n1/4log⁡n)O(n^{1/4}\log n)O(n1/4logn) using unitary gates alone.
The paper asks whether coherent Hamming-weight computation can simultaneously attain logarithmic depth and minimum width. It constructs an exact map ∣x⟩∣0m⟩↦∣x⟩∣∣x∣⟩|x\rangle|0^m\rangle\mapsto|x\rangle||x|\rangle∣x⟩∣0m⟩↦∣x⟩∣∣x∣⟩, with m=⌈log⁡2(n+1)⌉m=\lceil\log_2(n+1)\rceilm=⌈log2​(n+1)⌉, depth O(log⁡n)O(\log n)O(logn), size O(nlog⁡n)O(n\log n)O(nlogn), and no qubits beyond the input and binary output registers. Width is minimal for this interface, and the parity output gives an Ω(log⁡n)\Omega(\log n)Ω(logn) depth lower bound. The model permits arbitrary one-qubit gates and CNOTs, all-to-all connectivity, and no measurements.
The main primitive adds one mmm-bit source register to rrr arbitrary target registers in depth O(m+log⁡r)O(m+\log r)O(m+logr) and size O(rm2)O(rm^2)O(rm2) without extra workspace. Two tree traversals cancel unwanted initial target values; pipelined Fourier addition overlaps tree levels. Counting then borrows input blocks as dirty workspace, accumulates weight-dependent phases through addition–phase cancellation, restores the borrowed inputs, and applies an inverse Fourier transform. A separate dirty-workspace routing construction yields exact evaluation of every symmetric Boolean function with depth O(log⁡n)O(\log n)O(logn), size O(nlog⁡n)O(n\log n)O(nlogn), and mmm clean ancillas returned to zero.
Applications give exact balanced Dicke-state preparation with expected depth O(log⁡2n)O(\log^2 n)O(log2n) using measurements and feedforward, and exact unitary preparation at depth O(r1/4log⁡n)O(r^{1/4}\log n)O(r1/4logn), where r=min⁡{k,n−k}r=\min\{k,n-k\}r=min{k,n−k}, using mmm ancillas. These adapt existing preparation strategies. Adaptive depth excludes classical latency; unitary preparation assumes fixed classical weight. Restricted connectivity and fault-tolerant rotation synthesis are not costed, and linear-size counting remains open.
Hamming weight computation maps an nnn-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)O(\log n)O(logn) with a sublinear number of ancillas. In the standard 2D model, we give a circuit of depth O(n)O(\sqrt n)O(n​) with O(log⁡2n)O(\log^2 n)O(log2n) ancillas, and a matching lower bound showing that Θ(n)Θ(\sqrt n)Θ(n​) is optimal. In both dynamic models, we obtain constant-depth circuits with O(n1+εpolylog⁡ n)O(n^{1+\varepsilon}\operatorname{polylog}\,n)O(n1+εpolylogn) ancillary qubits for every fixed ε>0\varepsilon>0ε>0. All constructions give a smooth depth-ancilla tradeoff, and they also extend to arbitrary symmetric Boolean functions.
Efficient state preparation is a challenging and important problem in quantum computing. In this work, we present a recursive state preparation algorithm that combines logarithmic-depth Dicke state circuits with Hamming weight encoders for efficiently preparing ``leaf-separable" quantum states. The algorithm is built on binary partition trees, generalized weight distribution blocks (gWDBs), and leaf-level encoders. We evaluate the performance of the algorithm by numerically simulating it on randomly generated target states with between 4 and 15 qubits. Compared to general state preparation approaches which require O(2n)O(2^n)O(2n) CX gates, our algorithm achieves a circuit depth of O(klog⁡nk+2k)O(k\log\frac{n}{k} + 2^k)O(klogkn​+2k) and uses O(n(k+2k))O(n(k+2^k))O(n(k+2k)) two-qubit gates, where k<nk < nk<n denotes the subtree size. We also compare implementations of the algorithm with and without the use of ancilla qubits, providing a detailed analysis of the trade-offs in circuit depth and two-qubit gate counts. These results contribute to scalable state preparation for quantum algorithms that require structured inputs such as Dicke or near-Dicke states.
Optimizing the depth and number of ancillary qubits in quantum circuits is crucial in quantum computation, given the limitations imposed by current quantum devices. In this article, we introduce an innovative approach for implementing arbitrary symmetric Boolean functions using poly-logarithmic depth quantum circuits with only a logarithmic number of ancillary qubits. Symmetric functions are those whose outputs are dictated solely by the Hamming weight of the inputs. These functions find applications across various domains, including quantum machine learning and arithmetic circuit synthesis. Moreover, by fully leveraging the potential of qutrits, the ancilla count can be further reduced to just one. The key technique involves a novel poly-logarithmic depth quantum circuit designed to compute Hamming weight without the need for ancillary qubits. This quantum circuit for Hamming weight is of independent interest due to its wide-ranging applications, such as in quantum memory, quantum machine learning, and Hamiltonian dynamics simulations.
A pure state of fixed Hamming weight is a superposition of computational basis states such that each bitstring in the superposition has the same number of ones. Given a Hilbert space of the form $\mathcal{H}={({\mathbb{C}}_{2})}^{\ensuremath{\bigotimes}n}$, or an nnn-qubit system, the identity operator can be decomposed as a sum of projectors onto subspaces of fixed Hamming weight. In this work, we propose several quantum algorithms that realize a coherent Hamming weight projective measurement on an input pure state, meaning that the post-measurement state of the algorithm is the projection of the input state onto the corresponding subspace of fixed Hamming weight. We analyze a depth-width tradeoff for the corresponding quantum circuits, allowing for a depth reduction of the circuits at the cost of more control qubits. For an nnn-qubit input, the depth-optimal algorithm uses O(n)\mathcal{O}(n)O(n) control qubits and the corresponding circuit has depth O(log(n))\mathcal{O}(log(n))O(log(n)), assuming that we have the ability to perform qubit resets. Furthermore, the proposed algorithm construction uses only one- and two-qubit gates.
Classical circuits with unbounded fan-in can compute any Boolean function in constant depth when their size is unrestricted. We ask whether removing the restrictions on circuit size and ancillary qubits also allows quantum circuits built from arbitrary single-qubit gates and generalised Toffoli gates to implement every unitary in constant depth. We give exact constant-depth constructions for arbitrary permutations of computational basis states, diagonal unitaries and the preparation of arbitrary pure states. These connect quantum state preparation to reversible classical computation and the preparation of probability distributions. With fanout in the gate set, they use exponentially many gates and ancillary qubits and return all ancillary qubits to zero. Replacing fanout by an exact circuit over the original gate set preserves constant depth, although the size bounds can become doubly exponential. The implementation of arbitrary unitaries in constant depth remains open. We give equivalent formulations in terms of copying the vectors of a specified orthonormal basis, extracting their labels and implementing restricted families of unitaries. We also reduce arbitrary unitary implementation to that of traceless unitary involutions using one additional clean qubit. With adaptive measurements, gate teleportation gives depth proportional to the level of a gate in the Clifford hierarchy. Towards arbitrary unitary implementation in constant depth, we use port-based teleportation: for input dimension ddd and M≥d2−1M\geq d^2-1M≥d2−1 ports, we construct a unitary circuit of depth O(d)O(\sqrt d)O(d​), independent of MMM and including resource preparation and port selection, with entanglement fidelity at least (1−(d2−1)/(2M))2(1-(d^2-1)/(2M))^2(1−(d2−1)/(2M))2. Thus, at fixed ddd, the approximation can be made arbitrarily accurate without increasing depth. Whether the dependence on ddd can also be removed remains open.
Polylogarithmic-Weight Dicke States in QAC0^00 and Arbitrary Symmetric States in QACf0^0_ff0​
An nnn-qubit Dicke state of weight kkk, is the uniform superposition over all nnn-bit strings of Hamming weight kkk. Dicke states are central to quantum algorithms exhibiting speedups, such as Decoded Quantum Interferometry (Jordan et al., \emph{Nature}, 2025). In the NISQ era, quantum hardware is constrained by both depth and locality, motivating the question of which global operations suffice to prepare such states. QAC0^00, the quantum analogue of AC0^00, minimally extends local O(1)O(1)O(1)-depth quantum circuits by allowing arbitrary-width Toffoli (reversible AND) gates. We show that Dicke states of polylog(n)\mathrm{polylog}(n)polylog(n) weight can be prepared in QAC0^00. This gives the first QAC0^00 construction of any super-constant-weight nnn-qubit Dicke state, since previous constructions relied on the much more powerful FANOUTn_nn​ gate. In general, we show that any weight-kkk Dicke state can be constructed using FANOUTmin⁡(k,n−k)_{\min(k,n-k)}min(k,n−k)​ gates. Combined with recent hardness results, this yields a tight characterization: for k≤n/2k \leq n/2k≤n/2, a nnn-qubit weight-kkk Dicke state can be prepared in QAC0^00 if and only if FANOUTk_kk​ ∈\in∈ QAC0^00. We develop a limited-fanout state-synthesis toolkit for QAC0^00 that yields further constant-depth, poly(n)(n)(n)-ancilla constructions: 1. Every nnn-qubit symmetric state supported on Hamming weight ≤k\leq k≤k can be prepared using FANOUTk_kk​ gates. 2. Every O(log⁡n)O(\log n)O(logn)-qubit state can be prepared using quantum random-access memory (QRAMn_nn​), which refers to a coherent indexing gate. QRAMn_nn​ is a potentially weaker resource than FANOUTn_nn​ and can be implemented in QACf0^0_ff0​.