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:2608.04627

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

Wei Zi, Pei Yuan, Junhong Nie, Shengyu Zhang

quant-phSubmitted Aug 5, 2026• Announced Aug 6, 2026• 0 citations• Revised Aug 30, 2026 (v2)
v1 · Aug 5, 2026v2 · Aug 30, 2026
arXivHTMLPDF

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.

Comments
38 pages

Related papers

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

Wei Zi, Pei Yuan, Junhong Nie

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.

quant-pharXiv:2610.25315•Oct 20, 2026•0 citations

Quantum space-depth tradeoffs for coherent block encodings

Yuxin Zhang, Changpeng Shao

Block encodings are a basic interface between quantum algorithms and linear algebra. Standard LCU constructions achieve optimal circuit depth but typically require logarithmically many ancilla qubits. We ask how much quantum workspace can be reduced without sacrificing circuit depth, and study this tradeoff from both algorithmic and lower-bound perspectives. For a Hermitian decomposition $A=\sum_{j=1}^L α_j H_j$, with $\|H_j\|=1$ and $α=\sum_j|α_j|$, we give two coherent $\varepsilon$-approximate block-encoding constructions. The first uses one ancilla qubit and has depth $\widetilde O(L(α/\varepsilon)^{o(1)})$, while the second uses $O(\log\log(α/\varepsilon))$ ancillas and achieves depth $\widetilde O(L)$. For a broad Suzuki-based coherent simulation architecture, we prove an ancilla-depth tradeoff. In the polynomial-resource regime and for a constant number of coherent rounds, $\log(1/\varepsilon)\le O((\log Q)^2+2^a\log Q)$, where $Q$ is depth normalized by the number of Hamiltonian terms and $a$ is the ancilla count. Thus polylogarithmic dependence on $1/\varepsilon$ requires more than constantly many ancillas within this architecture. In a separate repeated-query LCU model, for balanced coefficients $1/L$ and error $\varepsilon=η/L$ with fixed $0<η<1$, we prove $2^a=Ω_η(L^2/(T+L))$, where $T$ is the number of oracle queries. Hence $a=Ω(\log L)$ when $T=O(L^α)$ for some $α<2$. Moreover, in the exact case, $a\ge \log L$ regardless of $T$. We also extend this tradeoff to arbitrary nonnegative coefficients. Finally, we apply our low-ancilla constructions to normalized trace estimation in DQC1, obtaining an optimal algorithm linear in the approximate degree together with a matching query lower bound. Together, these results establish quantitative space-depth and space-query tradeoffs in two natural circuit models.

quant-pharXiv:2607.01843•Jul 3, 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

Nearly optimal quantum circuits for Boolean oracles

Junhong Nie, Wei Zi

Quantum oracle of Boolean functions is one of the central bridges between classical and quantum algorithms, but the study focusing at quantum circuit optimization of such oracle is yet closed. In this paper, we propose nearly optimal tradeoffs among circuit size, circuit depth and ancilla count, for quantum oracles of three kinds of Boolean functions: general total Boolean functions with output size $b$: with $1\le m\leΘ\left(\frac{2^n}{n}\right)$ ancilla, size $\mathcal{O}\left(\frac{b2^n}{\log(n+m)}\right)$, depth $\mathcal{O}\left(\frac{b2^n}{n+m}\right)$; partial Boolean functions of effective support size $d$ and output size $b$: with $Θ\left(\log d\right)\le m\le Θ\left(d\right)$ ancilla, size $\mathcal{O}\left(n\log d+bd\right)$, depth $\mathcal{O}\left(\frac{n\log n\log d}{n+m}+\log n+\frac{d(\log d+b\log m)}{m}\right)$; sparse Boolean functions of true input size $d$: with $Θ\left(\log n+\log d\right)\le m\leΘ\left(\frac{nd}{\log d}\right)$ ancilla, size $\mathcal{O}\left(n^2\log d+\frac{nd}{\log(\log d+m/n)}\right)$, depth $\mathcal{O}\left(\frac{n^2\log n\log d}{n+m}+\log n+\frac{nd}{m}\right)$. All the size and depth bounds are asymptotically optimal up to logarithmic factors in the corresponding ancilla count regions. We hope these results find applications in scenarios where classical procedures are needed to be embedded into quantum circuits, such as QROM implementation and quantum algorithm design.

quant-pharXiv:2607.28402•Jul 31, 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

On the Computational Power of Geometrically Local QAC circuits

Yangjing Dong, Fengning Ou, Penghui Yao

The computational power of $\mathsf{QAC}$, which are constant-depth quantum circuit families consisting of arbitrary single-qubit unitaries and n-qubit generalized Toffoli gates, has gained tremendous focus recently. In this work, we initiate the study of the computational complexity of geometrically local $\mathsf{QAC}$ circuits, where the qubits are arranged in a high-dimensional grid, and all the generalized Toffoli gates act on contiguous qubits along one direction. We prove that $\mathsf{2D\text{-}QAC}$ circuits are universal: any $\mathsf{QAC}$ circuit can be exactly simulated by a two-dimensional geometrically local $\mathsf{QAC}$ circuit. Therefore, we focus on the computational power of $\mathsf{2D\text{-}QAC}$ circuits with grid width $w$. We prove that $\mathsf{PARITY}$ computation has a tight width--depth tradeoff of $w=n^{Θ(1/d)}$ in the constant-depth regime if the circuit allows arbitrary ancilla. Moreover, for polynomial-size circuits, a width lower bound of $n^{ω(1/d)}$ for $\mathsf{PARITY}$ would imply $\mathsf{PARITY}\notin\mathsf{QAC}^0$. We also establish Fourier tail and sensitivity bounds, together with tight width lower bounds and tight depth lower bounds in $\mathsf{1D\text{-}QAC}$ circuits for $\mathsf{MAJORITY}$ and $\mathsf{MOD}$ computation. Our main tool is \emph{local measurement variance}, the maximum variance of normalized sums of observables on separated regions. We use a hybrid argument to show that each layer of a $\mathsf{2D\text{-}QAC}^0$ circuit increases this variance by at most a factor depending only on its width, yielding a variance bound for every $\mathsf{2D\text{-}QAC}^0$ state. The high local measurement variance of cat and Dicke states then gives the width lower bounds.

quant-pharXiv:2604.07178•Apr 9, 2026•0 citations
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.
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.
Block encodings are a basic interface between quantum algorithms and linear algebra. Standard LCU constructions achieve optimal circuit depth but typically require logarithmically many ancilla qubits. We ask how much quantum workspace can be reduced without sacrificing circuit depth, and study this tradeoff from both algorithmic and lower-bound perspectives. For a Hermitian decomposition A=∑j=1LαjHjA=\sum_{j=1}^L α_j H_jA=∑j=1L​αj​Hj​, with ∥Hj∥=1\|H_j\|=1∥Hj​∥=1 and α=∑j∣αj∣α=\sum_j|α_j|α=∑j​∣αj​∣, we give two coherent ε\varepsilonε-approximate block-encoding constructions. The first uses one ancilla qubit and has depth O~(L(α/ε)o(1))\widetilde O(L(α/\varepsilon)^{o(1)})O(L(α/ε)o(1)), while the second uses O(log⁡log⁡(α/ε))O(\log\log(α/\varepsilon))O(loglog(α/ε)) ancillas and achieves depth O~(L)\widetilde O(L)O(L). For a broad Suzuki-based coherent simulation architecture, we prove an ancilla-depth tradeoff. In the polynomial-resource regime and for a constant number of coherent rounds, log⁡(1/ε)≤O((log⁡Q)2+2alog⁡Q)\log(1/\varepsilon)\le O((\log Q)^2+2^a\log Q)log(1/ε)≤O((logQ)2+2alogQ), where QQQ is depth normalized by the number of Hamiltonian terms and aaa is the ancilla count. Thus polylogarithmic dependence on 1/ε1/\varepsilon1/ε requires more than constantly many ancillas within this architecture. In a separate repeated-query LCU model, for balanced coefficients 1/L1/L1/L and error ε=η/L\varepsilon=η/Lε=η/L with fixed 0<η<10<η<10<η<1, we prove 2a=Ωη(L2/(T+L))2^a=Ω_η(L^2/(T+L))2a=Ωη​(L2/(T+L)), where TTT is the number of oracle queries. Hence a=Ω(log⁡L)a=Ω(\log L)a=Ω(logL) when T=O(Lα)T=O(L^α)T=O(Lα) for some α<2α<2α<2. Moreover, in the exact case, a≥log⁡La\ge \log La≥logL regardless of TTT. We also extend this tradeoff to arbitrary nonnegative coefficients. Finally, we apply our low-ancilla constructions to normalized trace estimation in DQC1, obtaining an optimal algorithm linear in the approximate degree together with a matching query lower bound. Together, these results establish quantitative space-depth and space-query tradeoffs in two natural circuit models.
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.
Quantum oracle of Boolean functions is one of the central bridges between classical and quantum algorithms, but the study focusing at quantum circuit optimization of such oracle is yet closed. In this paper, we propose nearly optimal tradeoffs among circuit size, circuit depth and ancilla count, for quantum oracles of three kinds of Boolean functions: general total Boolean functions with output size bbb: with 1≤m≤Θ(2nn)1\le m\leΘ\left(\frac{2^n}{n}\right)1≤m≤Θ(n2n​) ancilla, size O(b2nlog⁡(n+m))\mathcal{O}\left(\frac{b2^n}{\log(n+m)}\right)O(log(n+m)b2n​), depth O(b2nn+m)\mathcal{O}\left(\frac{b2^n}{n+m}\right)O(n+mb2n​); partial Boolean functions of effective support size ddd and output size bbb: with Θ(log⁡d)≤m≤Θ(d)Θ\left(\log d\right)\le m\le Θ\left(d\right)Θ(logd)≤m≤Θ(d) ancilla, size O(nlog⁡d+bd)\mathcal{O}\left(n\log d+bd\right)O(nlogd+bd), depth O(nlog⁡nlog⁡dn+m+log⁡n+d(log⁡d+blog⁡m)m)\mathcal{O}\left(\frac{n\log n\log d}{n+m}+\log n+\frac{d(\log d+b\log m)}{m}\right)O(n+mnlognlogd​+logn+md(logd+blogm)​); sparse Boolean functions of true input size ddd: with Θ(log⁡n+log⁡d)≤m≤Θ(ndlog⁡d)Θ\left(\log n+\log d\right)\le m\leΘ\left(\frac{nd}{\log d}\right)Θ(logn+logd)≤m≤Θ(logdnd​) ancilla, size O(n2log⁡d+ndlog⁡(log⁡d+m/n))\mathcal{O}\left(n^2\log d+\frac{nd}{\log(\log d+m/n)}\right)O(n2logd+log(logd+m/n)nd​), depth O(n2log⁡nlog⁡dn+m+log⁡n+ndm)\mathcal{O}\left(\frac{n^2\log n\log d}{n+m}+\log n+\frac{nd}{m}\right)O(n+mn2lognlogd​+logn+mnd​). All the size and depth bounds are asymptotically optimal up to logarithmic factors in the corresponding ancilla count regions. We hope these results find applications in scenarios where classical procedures are needed to be embedded into quantum circuits, such as QROM implementation and quantum algorithm design.
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.
The computational power of QAC\mathsf{QAC}QAC, which are constant-depth quantum circuit families consisting of arbitrary single-qubit unitaries and n-qubit generalized Toffoli gates, has gained tremendous focus recently. In this work, we initiate the study of the computational complexity of geometrically local QAC\mathsf{QAC}QAC circuits, where the qubits are arranged in a high-dimensional grid, and all the generalized Toffoli gates act on contiguous qubits along one direction. We prove that 2D-QAC\mathsf{2D\text{-}QAC}2D-QAC circuits are universal: any QAC\mathsf{QAC}QAC circuit can be exactly simulated by a two-dimensional geometrically local QAC\mathsf{QAC}QAC circuit. Therefore, we focus on the computational power of 2D-QAC\mathsf{2D\text{-}QAC}2D-QAC circuits with grid width www. We prove that PARITY\mathsf{PARITY}PARITY computation has a tight width--depth tradeoff of w=nΘ(1/d)w=n^{Θ(1/d)}w=nΘ(1/d) in the constant-depth regime if the circuit allows arbitrary ancilla. Moreover, for polynomial-size circuits, a width lower bound of nω(1/d)n^{ω(1/d)}nω(1/d) for PARITY\mathsf{PARITY}PARITY would imply PARITY∉QAC0\mathsf{PARITY}\notin\mathsf{QAC}^0PARITY∈/QAC0. We also establish Fourier tail and sensitivity bounds, together with tight width lower bounds and tight depth lower bounds in 1D-QAC\mathsf{1D\text{-}QAC}1D-QAC circuits for MAJORITY\mathsf{MAJORITY}MAJORITY and MOD\mathsf{MOD}MOD computation. Our main tool is \emph{local measurement variance}, the maximum variance of normalized sums of observables on separated regions. We use a hybrid argument to show that each layer of a 2D-QAC0\mathsf{2D\text{-}QAC}^02D-QAC0 circuit increases this variance by at most a factor depending only on its width, yielding a variance bound for every 2D-QAC0\mathsf{2D\text{-}QAC}^02D-QAC0 state. The high local measurement variance of cat and Dicke states then gives the width lower bounds.