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

Optimal T depth quantum circuits for implementing arbitrary Boolean functions

Dutta, Suman, Bhaumik, Anik Basu, Anupam Chattopadhyay, Subhamoy Maitra

Published Jun 2, 2025• 0 citations
arXivHTMLPDF

Abstract

In this paper we present a generic construction to obtain an optimal T depth quantum circuit for any arbitrary $n$-input $m$-output Boolean function $f: \{0,1\}^n \rightarrow \{0,1\}^m$ having algebraic degree $k\leq n$, and it achieves an exact Toffoli (and T) depth of $\lceil \log_2 k \rceil$. This is a broader generalization of the recent result establishing the optimal Toffoli (and consequently T) depth for multi-controlled Toffoli decompositions (Dutta et al., Phys. Rev. A, 2025). We achieve this by inspecting the Algebraic Normal Form (ANF) of a Boolean function. Obtaining a benchmark for the minimum T depth of such circuits are of prime importance for 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 implications of our results are highlighted explaining the provable lower bounds on S-box and block cipher implementations, for example AES.

DOI
10.48550/arxiv.2506.01542

Related papers

$\mathsf{QAC}^0$ Contains $\mathsf{TC}^0$ (with Many Copies of the Input)

Daniel Grier, Jackson Morris, Kewen Wu

$\mathsf{QAC}^0$ is the class of constant-depth polynomial-size quantum circuits constructed from arbitrary single-qubit gates and generalized Toffoli gates. It is arguably the smallest natural class of constant-depth quantum computation which has not been shown useful for computing any non-trivial Boolean function. Despite this, many attempts to port classical $\mathsf{AC}^0$ lower bounds to $\mathsf{QAC}^0$ have failed. We give one possible explanation of this: $\mathsf{QAC}^0$ circuits are significantly more powerful than their classical counterparts. We show the unconditional separation $\mathsf{QAC}^0\not\subset\mathsf{AC}^0[p]$ for decision problems, which also resolves for the first time whether $\mathsf{AC}^0$ could be more powerful than $\mathsf{QAC}^0$. Moreover, we prove that $\mathsf{QAC}^0$ circuits can compute a wide range of Boolean functions if given multiple copies of the input: $\mathsf{TC}^0 \subseteq \mathsf{QAC}^0 \circ \mathsf{NC}^0$. Along the way, we introduce an amplitude amplification technique that makes several approximate constant-depth constructions exact.

cs.CCCross-listedarXiv:2601.03243•Jan 7, 2026•0 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.

Quantum Information and Computation•Dec 1, 2025•2 citations

Depth-Optimal Quantum Compilation

Francisca Vasconcelos

We achieve the first constant-depth circuit for arbitrary single-qubit gate synthesis. Unlike prior approaches, the construction is fully unitary and requires no pre-supplied catalyst. For any constant $δ>0$, it $\varepsilon$-approximates an arbitrary single-qubit gate using $O(\log^{1+δ}(1/\varepsilon))$ clean ancillae, Hadamard and $T$ single-qubit gates, $O(\log(1/\varepsilon))$-width generalized Toffoli gates, and sublogarithmic-width Fan-Out gates. We further eliminate Fan-Out entirely, showing that Hadamard, $T$, and generalized Toffoli gates alone suffice for constant-depth synthesis. When restricted to the standard bounded-width gate model, our construction has depth $O(\log\log(1/\varepsilon))$, and we prove a matching $Ω(\log\log(1/\varepsilon))$-depth lower bound. Overall, we establish that $Θ(\log\log(1/\varepsilon))$-depth is unavoidable with only bounded-width gates, yet allowing even logarithmic-width multi-qubit gates suffices to achieve constant-depth synthesis. These results also reveal new structure in shallow quantum circuit complexity. We give a depth-preserving real simulation of bounded-error decision computation, showing that every depth-$d$ QAC circuit can be simulated in depth $O(d)$ using only Hadamard, $X$, and generalized Toffoli gates. Thus arbitrary single-qubit rotations and complex amplitudes do not increase the bounded-error decision power of QAC, even at constant depth. In particular, this reduces the long-standing conjecture Parity$\notin$QAC$^0$ to proving a Parity lower bound against circuits consisting only of Hadamard, $X$, and generalized Toffoli gates. More generally, this real normal form exposes a direct correspondence between the standard shallow-depth quantum circuit hierarchy and a hierarchy of Forrelation circuits with restricted oracle families.

quant-pharXiv:2609.34659•Sep 29, 2026•0 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

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

On Exact Space-Depth Trade-Offs in Multi-Controlled Toffoli Decomposition

Dutta, Suman, Siyi Wang, Anubhab Baksi +2 more

In this paper, we consider the optimized implementation of Multi Controlled Toffoli (MCT) using the Clifford $+$ T gate sets. While there are several recent works in this direction, here we explicitly quantify the trade-off (with concrete formulae) between the Toffoli depth (this means the depth using the classical 2-controlled Toffoli) of the $n$-controlled Toffoli (hereform we will tell $n$-MCT) and the number of clean ancilla qubits. Additionally, we achieve a reduced Toffoli depth (and consequently, T-depth), which is an extension of the technique introduced by Khattar et al. (2024). In terms of a negative result, we first show that using such conditionally clean ancilla techniques, Toffoli depth can never achieve exactly $\ceil{\log_2 n}$, though it remains of the same order. This highlights the limitation of the techniques exploiting conditionally clean ancilla [Nie et al., 2024, Khattar et al., 2024]. Then we prove that, in a more general setup, the T-Depth in the Clifford + T decomposition, via Toffoli gates, is lower bounded by $\ceil{\log_2 n}$, and this bound is achieved following the complete binary tree structure. Since the ($2$-controlled) Toffoli gate can further be decomposed using Clifford $+$ T, various methodologies are explored too in this regard for trade-off related implications.

arXiv:2502.01433•Feb 3, 2025•0 citations
In this paper we present a generic construction to obtain an optimal T depth quantum circuit for any arbitrary nnn-input mmm-output Boolean function f:{0,1}n→{0,1}mf: \{0,1\}^n \rightarrow \{0,1\}^mf:{0,1}n→{0,1}m having algebraic degree k≤nk\leq nk≤n, and it achieves an exact Toffoli (and T) depth of ⌈log⁡2k⌉\lceil \log_2 k \rceil⌈log2​k⌉. This is a broader generalization of the recent result establishing the optimal Toffoli (and consequently T) depth for multi-controlled Toffoli decompositions (Dutta et al., Phys. Rev. A, 2025). We achieve this by inspecting the Algebraic Normal Form (ANF) of a Boolean function. Obtaining a benchmark for the minimum T depth of such circuits are of prime importance for 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 implications of our results are highlighted explaining the provable lower bounds on S-box and block cipher implementations, for example AES.
QAC0\mathsf{QAC}^0QAC0 Contains TC0\mathsf{TC}^0TC0 (with Many Copies of the Input)
QAC0\mathsf{QAC}^0QAC0 is the class of constant-depth polynomial-size quantum circuits constructed from arbitrary single-qubit gates and generalized Toffoli gates. It is arguably the smallest natural class of constant-depth quantum computation which has not been shown useful for computing any non-trivial Boolean function. Despite this, many attempts to port classical AC0\mathsf{AC}^0AC0 lower bounds to QAC0\mathsf{QAC}^0QAC0 have failed. We give one possible explanation of this: QAC0\mathsf{QAC}^0QAC0 circuits are significantly more powerful than their classical counterparts. We show the unconditional separation QAC0⊄AC0[p]\mathsf{QAC}^0\not\subset\mathsf{AC}^0[p]QAC0⊂AC0[p] for decision problems, which also resolves for the first time whether AC0\mathsf{AC}^0AC0 could be more powerful than QAC0\mathsf{QAC}^0QAC0. Moreover, we prove that QAC0\mathsf{QAC}^0QAC0 circuits can compute a wide range of Boolean functions if given multiple copies of the input: TC0⊆QAC0∘NC0\mathsf{TC}^0 \subseteq \mathsf{QAC}^0 \circ \mathsf{NC}^0TC0⊆QAC0∘NC0. Along the way, we introduce an amplitude amplification technique that makes several approximate constant-depth constructions exact.
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.
We achieve the first constant-depth circuit for arbitrary single-qubit gate synthesis. Unlike prior approaches, the construction is fully unitary and requires no pre-supplied catalyst. For any constant δ>0δ>0δ>0, it ε\varepsilonε-approximates an arbitrary single-qubit gate using O(log⁡1+δ(1/ε))O(\log^{1+δ}(1/\varepsilon))O(log1+δ(1/ε)) clean ancillae, Hadamard and TTT single-qubit gates, O(log⁡(1/ε))O(\log(1/\varepsilon))O(log(1/ε))-width generalized Toffoli gates, and sublogarithmic-width Fan-Out gates. We further eliminate Fan-Out entirely, showing that Hadamard, TTT, and generalized Toffoli gates alone suffice for constant-depth synthesis. When restricted to the standard bounded-width gate model, our construction has depth O(log⁡log⁡(1/ε))O(\log\log(1/\varepsilon))O(loglog(1/ε)), and we prove a matching Ω(log⁡log⁡(1/ε))Ω(\log\log(1/\varepsilon))Ω(loglog(1/ε))-depth lower bound. Overall, we establish that Θ(log⁡log⁡(1/ε))Θ(\log\log(1/\varepsilon))Θ(loglog(1/ε))-depth is unavoidable with only bounded-width gates, yet allowing even logarithmic-width multi-qubit gates suffices to achieve constant-depth synthesis. These results also reveal new structure in shallow quantum circuit complexity. We give a depth-preserving real simulation of bounded-error decision computation, showing that every depth-ddd QAC circuit can be simulated in depth O(d)O(d)O(d) using only Hadamard, XXX, and generalized Toffoli gates. Thus arbitrary single-qubit rotations and complex amplitudes do not increase the bounded-error decision power of QAC, even at constant depth. In particular, this reduces the long-standing conjecture Parity∉\notin∈/QAC0^00 to proving a Parity lower bound against circuits consisting only of Hadamard, XXX, and generalized Toffoli gates. More generally, this real normal form exposes a direct correspondence between the standard shallow-depth quantum circuit hierarchy and a hierarchy of Forrelation circuits with restricted oracle families.
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 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 paper, we consider the optimized implementation of Multi Controlled Toffoli (MCT) using the Clifford +++ T gate sets. While there are several recent works in this direction, here we explicitly quantify the trade-off (with concrete formulae) between the Toffoli depth (this means the depth using the classical 2-controlled Toffoli) of the nnn-controlled Toffoli (hereform we will tell nnn-MCT) and the number of clean ancilla qubits. Additionally, we achieve a reduced Toffoli depth (and consequently, T-depth), which is an extension of the technique introduced by Khattar et al. (2024). In terms of a negative result, we first show that using such conditionally clean ancilla techniques, Toffoli depth can never achieve exactly $\ceil{\log_2 n}$, though it remains of the same order. This highlights the limitation of the techniques exploiting conditionally clean ancilla [Nie et al., 2024, Khattar et al., 2024]. Then we prove that, in a more general setup, the T-Depth in the Clifford + T decomposition, via Toffoli gates, is lower bounded by $\ceil{\log_2 n}$, and this bound is achieved following the complete binary tree structure. Since the (222-controlled) Toffoli gate can further be decomposed using Clifford +++ T, various methodologies are explored too in this regard for trade-off related implications.