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

Nearly optimal quantum circuits for Boolean oracles

Junhong Nie, Wei Zi

quant-phSubmitted Jul 30, 2026• Announced Jul 31, 2026• 1 citation
arXivHTMLPDF

Abstract

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.

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

Novel oracle constructions for quantum random access memory

Ákos Nagy, Cindy Zhang

We present new designs for quantum random access memory. More precisely, for each function, $f : \mathbb{F}_2^n \rightarrow \mathbb{F}_2^d$, we construct oracles, $\mathcal{O}_f$, with the property \begin{equation} \mathcal{O}_f \left| x \right\rangle_n \left| 0 \right\rangle_d = \left| x \right\rangle_n \left| f(x) \right\rangle_d. \end{equation} Our methods are based on the Walsh-Hadamard Transform of $f$, viewed as an integer valued function. In general, the complexity of our method scales with the sparsity of the Walsh-Hadamard Transform and not the sparsity of $f$, yielding more favorable constructions in cases such as binary optimization problems and function with low-degree Walsh-Hadamard Transforms. Furthermore, our design comes with a tuneable amount of ancillas that can trade depth for size. In the ancilla-free design, these oracles can be $ε$-approximated so that the Clifford + $T$ depth is $O \left( \left( n + \log_2 \left( \tfrac{d}ε \right) \right) \mathcal{W}_f \right)$, where $\mathcal{W}_f$ is the number of nonzero components in the Walsh-Hadamard Transform. The depth of the shallowest version is $O \left( n + \log_2 \left( \tfrac{d}ε \right) \right)$, using $n + d \mathcal{W}_f$ qubit. The connectivity of these circuits is also only logarithmic in $\mathcal{W}_f$. As an application, we show that for boolean functions with low approximate degrees (as in the case of read-once formulas) the complexities of the corresponding QRAM oracles scale only as $2^{\widetilde{O} \left( \sqrt{n} \log_2 \left( n \right) \right)}$.

arXiv:2405.20225•May 30, 2024•6 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•3 citations

Optimal T-depth Quantum Circuits for Implementing Arbitrary Boolean Functions

Suman Dutta, Anik Bhaumik, Anupam Chattopadhyay +1 more

Abstract In this paper, we present a generic construction for synthesizing an optimal T-depth quantum circuit for any arbitrary n -input, m -output Boolean function f : {0, 1 } n → {0, 1} m with algebraic degree k ≤ n , achieving an exact Toffoli (consequently T) depth of ⌈log 2 k ⌉. This broadly generalizes the recent result establishing the optimal Toffoli (and T) depth for multi-controlled Toffoli decompositions (Dutta et al., Phys. Rev. A, 2025). The optimality of T-depth in this initiative is considered in the context of implementing an n -MCT, assuming the decomposition via Clifford plus Toffoli gates. The key technique involves inspecting the Algebraic Normal Form (ANF) of the Boolean function. Obtaining a benchmark for the minimum T-depth of such circuits is crucial for the efficient implementation of quantum algorithms by enabling greater parallelism, reducing time complexity, and minimizing circuit latency, making them suitable for near-term quantum devices with limited coherence times. The broader implications of our results include a provable lower bounds on T-depth for S-box and block cipher implementations, such as AES. Finally, we also explain the impact of our result in identifying the T-depth for the generic cryptanalysis of block ciphers using Grover’s algorithm.

arXiv:2506.01542•Quantum Information and Computation•Dec 1, 2025•4 citations

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

Improved Lower Bounds for QAC0

Malvika Raj Joshi, Avishay Tal, Francisca Vasconcelos +1 more

In this work, we prove the strongest known lower bounds for QAC$^0$, allowing polynomially many gates and ancillae. Our main results show that: (1) Depth-3 QAC$^0$ circuits cannot compute PARITY, and require $Ω(\exp(\sqrt{n}))$ gates to compute MAJORITY. (2) Depth-2 circuits cannot approximate high-influence Boolean functions (e.g., PARITY) with non-negligible advantage, regardless of size. We develop new classical simulation techniques for QAC$^0$ to obtain our depth-3 bounds. In these results, we relax the output requirement of the quantum circuit to a single bit, making our depth $2$ approximation bound stronger than the previous best bound of Rosenthal (2021). This also enables us to draw natural comparisons with classical AC$^0$ circuits, which can compute PARITY exactly in depth $2$ (exp size). Our techniques further suggest that, for boolean total functions, constant-depth quantum circuits do not necessarily provide more power than their classical counterparts. Our third result shows that depth $2$ QAC$^0$ circuits, regardless of size, cannot exactly synthesize an $n$-target nekomata state (a state whose synthesis is directly related to the computation of PARITY). This complements the depth $2$ exponential size upper bound of Rosenthal (2021) for approximating nekomatas (which is used as a sub-circuit in the only known constant depth PARITY upper bound). Finally, we argue that approximating PARITY in QAC0, with significantly better than 1/poly(n) advantage on average, is just as hard as computing it exactly. Thus, extending our techniques to higher depths would also rule out approximate circuits for PARITY and related problems

quant-pharXiv:2512.14643•ACM Symposium on Theory of Computing (STOC)•Dec 17, 2025•6 citations
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 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.
We present new designs for quantum random access memory. More precisely, for each function, f:F2n→F2df : \mathbb{F}_2^n \rightarrow \mathbb{F}_2^df:F2n​→F2d​, we construct oracles, Of\mathcal{O}_fOf​, with the property \begin{equation} \mathcal{O}_f \left| x \right\rangle_n \left| 0 \right\rangle_d = \left| x \right\rangle_n \left| f(x) \right\rangle_d. \end{equation} Our methods are based on the Walsh-Hadamard Transform of fff, viewed as an integer valued function. In general, the complexity of our method scales with the sparsity of the Walsh-Hadamard Transform and not the sparsity of fff, yielding more favorable constructions in cases such as binary optimization problems and function with low-degree Walsh-Hadamard Transforms. Furthermore, our design comes with a tuneable amount of ancillas that can trade depth for size. In the ancilla-free design, these oracles can be εεε-approximated so that the Clifford + TTT depth is O((n+log⁡2(dε))Wf)O \left( \left( n + \log_2 \left( \tfrac{d}ε \right) \right) \mathcal{W}_f \right)O((n+log2​(εd​))Wf​), where Wf\mathcal{W}_fWf​ is the number of nonzero components in the Walsh-Hadamard Transform. The depth of the shallowest version is O(n+log⁡2(dε))O \left( n + \log_2 \left( \tfrac{d}ε \right) \right)O(n+log2​(εd​)), using n+dWfn + d \mathcal{W}_fn+dWf​ qubit. The connectivity of these circuits is also only logarithmic in Wf\mathcal{W}_fWf​. As an application, we show that for boolean functions with low approximate degrees (as in the case of read-once formulas) the complexities of the corresponding QRAM oracles scale only as 2O~(nlog⁡2(n))2^{\widetilde{O} \left( \sqrt{n} \log_2 \left( n \right) \right)}2O(n​log2​(n)).
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.
Abstract In this paper, we present a generic construction for synthesizing an optimal T-depth quantum circuit for any arbitrary n -input, m -output Boolean function f : {0, 1 } n → {0, 1} m with algebraic degree k ≤ n , achieving an exact Toffoli (consequently T) depth of ⌈log 2 k ⌉. This broadly generalizes the recent result establishing the optimal Toffoli (and T) depth for multi-controlled Toffoli decompositions (Dutta et al., Phys. Rev. A, 2025). The optimality of T-depth in this initiative is considered in the context of implementing an n -MCT, assuming the decomposition via Clifford plus Toffoli gates. The key technique involves inspecting the Algebraic Normal Form (ANF) of the Boolean function. Obtaining a benchmark for the minimum T-depth of such circuits is crucial for the efficient implementation of quantum algorithms by enabling greater parallelism, reducing time complexity, and minimizing circuit latency, making them suitable for near-term quantum devices with limited coherence times. The broader implications of our results include a provable lower bounds on T-depth for S-box and block cipher implementations, such as AES. Finally, we also explain the impact of our result in identifying the T-depth for the generic cryptanalysis of block ciphers using Grover’s algorithm.
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.
In this work, we prove the strongest known lower bounds for QAC0^00, allowing polynomially many gates and ancillae. Our main results show that: (1) Depth-3 QAC0^00 circuits cannot compute PARITY, and require Ω(exp⁡(n))Ω(\exp(\sqrt{n}))Ω(exp(n​)) gates to compute MAJORITY. (2) Depth-2 circuits cannot approximate high-influence Boolean functions (e.g., PARITY) with non-negligible advantage, regardless of size. We develop new classical simulation techniques for QAC0^00 to obtain our depth-3 bounds. In these results, we relax the output requirement of the quantum circuit to a single bit, making our depth 222 approximation bound stronger than the previous best bound of Rosenthal (2021). This also enables us to draw natural comparisons with classical AC0^00 circuits, which can compute PARITY exactly in depth 222 (exp size). Our techniques further suggest that, for boolean total functions, constant-depth quantum circuits do not necessarily provide more power than their classical counterparts. Our third result shows that depth 222 QAC0^00 circuits, regardless of size, cannot exactly synthesize an nnn-target nekomata state (a state whose synthesis is directly related to the computation of PARITY). This complements the depth 222 exponential size upper bound of Rosenthal (2021) for approximating nekomatas (which is used as a sub-circuit in the only known constant depth PARITY upper bound). Finally, we argue that approximating PARITY in QAC0, with significantly better than 1/poly(n) advantage on average, is just as hard as computing it exactly. Thus, extending our techniques to higher depths would also rule out approximate circuits for PARITY and related problems