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.

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•0 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•4 citations

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•0 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•6 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•0 citations

Preparation of Hamming-Weight-Preserving Quantum States with Log-Depth Quantum Circuits

Yu Li, Guojing Tian, He, Xiaoyu +3 more

Hamming-Weight-Preserving (HWP) states, $\vertψ_{\mathrm{H}}\rangle=\sum_{\mathrm{HW}(x)=k}α_x\vert x\rangle$, represent a fundamental class of quantum states on $n$ qubits with fixed excitation number $k$, playing a pivotal role in quantum simulation, machine learning, and optimization, with prominent examples including the Bethe eigenstates of integrable models and Configuration Interaction states. However, existing preparation methodologies typically rely on sequential architectures whose depth scales linearly with the subspace dimension, whereas practical deployment on realistic quantum hardware demands shallow circuits to mitigate decoherence. In this work, we present quantum circuits that achieve the information theoretic limit of depth logarithmic in the number of populated computational basis states while maintaining asymptotically optimal size. Specifically, for general HWP states, we provide a construction that matches the lower bounds of $Θ(\log \binom{n}{k})$ depth and $Θ(\binom{n}{k})$ size. Furthermore, we propose a resource efficient scheme utilizing only $O(\log k)$ ancillary qubits. For the $k=2$ case, where HWP states naturally admit a graph representation, we show that states whose support graphs are trees or grids admit ancilla free preparation with $Θ(\log n)$ depth and $Θ(m)$ size. Overall, our work provides logarithmic depth state preparation algorithms across various regimes while establishing a connection between quantum state synthesis and Krawtchouk polynomials.

arXiv:2508.14470•Aug 20, 2025•0 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.
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.
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.
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.
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.
Hamming-Weight-Preserving (HWP) states, ∣ψH⟩=∑HW(x)=kαx∣x⟩\vertψ_{\mathrm{H}}\rangle=\sum_{\mathrm{HW}(x)=k}α_x\vert x\rangle∣ψH​⟩=∑HW(x)=k​αx​∣x⟩, represent a fundamental class of quantum states on nnn qubits with fixed excitation number kkk, playing a pivotal role in quantum simulation, machine learning, and optimization, with prominent examples including the Bethe eigenstates of integrable models and Configuration Interaction states. However, existing preparation methodologies typically rely on sequential architectures whose depth scales linearly with the subspace dimension, whereas practical deployment on realistic quantum hardware demands shallow circuits to mitigate decoherence. In this work, we present quantum circuits that achieve the information theoretic limit of depth logarithmic in the number of populated computational basis states while maintaining asymptotically optimal size. Specifically, for general HWP states, we provide a construction that matches the lower bounds of Θ(log⁡(nk))Θ(\log \binom{n}{k})Θ(log(kn​)) depth and Θ((nk))Θ(\binom{n}{k})Θ((kn​)) size. Furthermore, we propose a resource efficient scheme utilizing only O(log⁡k)O(\log k)O(logk) ancillary qubits. For the k=2k=2k=2 case, where HWP states naturally admit a graph representation, we show that states whose support graphs are trees or grids admit ancilla free preparation with Θ(log⁡n)Θ(\log n)Θ(logn) depth and Θ(m)Θ(m)Θ(m) size. Overall, our work provides logarithmic depth state preparation algorithms across various regimes while establishing a connection between quantum state synthesis and Krawtchouk polynomials.