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:2404.18104 · ACM Transactions on Quantum Computing

The Power of Shallow-depth Toffoli and Qudit Quantum Circuits

Alex B. Grilo, Elham Kashefi, Damian Markham, Michael de Oliveira

Published May 18, 2026• 9 citations
arXivHTMLPDF

Abstract

The relevance of shallow-depth quantum circuits has recently increased, mainly due to their applicability to near-term devices. In this context, one of the main goals of quantum circuit complexity is to find problems that can be solved by quantum shallow circuits but require more computational resources classically. Our first contribution in this work is to prove new separations between classical and quantum constant-depth circuits. Firstly, we show a separation between constant-depth quantum circuits with quantum advice \(\mathsf {QNC}^0/\mathsf {qpoly} \) , and \(\mathsf {AC}^0[p] \) , which is the class of classical constant-depth circuits with unbounded-fan in and \(\mathsf {MOD}_{p} \) gates. Additionally, we show a separation between \(\mathsf {QAC}^0 \) , the circuit class containing Toffoli gates with unbounded control, and \(\mathsf {AC}^0[p] \) , when \(\mathsf {QAC}^0 \) is augmented with additional mid-circuit measurements and classical fanout. This establishes the first such separation for a shallow-depth quantum class that does not involve quantum fanout gates, while relying solely on finite quantum gate sets. Equivalently, this yields a separation between \(\mathsf {AC}^0[p] \) and \([\mathsf {QNC}^0, \mathsf {AC}^0]^2 \) , i.e., shallow quantum circuits interleaved with simple classical computation. Secondly, we consider \(\mathsf {QNC}^0 \) circuits with infinite-size gate sets. We show that these circuits, along with quantum prime modular gates or classical prime modular gates in combination with classical fanout, can implement threshold gates, showing that \(\mathsf {QNC}^0[p]=\mathsf {QTC}^0 \) . Finally, we also show that in the infinite-size gate set case, these quantum circuit classes for higher-dimensional Hilbert spaces do not offer any advantage to standard qubit implementations.

DOI
10.1145/3802819

Related papers

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

Counting, fanout and the complexity of quantum ACC

F. Green, Steven Thomas Homer, Cristopher Moore +1 more

We propose definitions of QAC^0, the quantum analog of the classical class AC^0 of constant-depth circuits with AND and OR gates of arbitrary fan-in, and QACC[q], the analog of the class ACC[q] where Mod_q gates are also allowed. We prove that parity or fanout allows us to construct quantum MOD_q gates in constant depth for any q, so QACC[2] = QACC. More generally, we show that for any q,p > 1, MOD_q is equivalent to MOD_p (up to constant depth and polynomial size). This implies that QAC^0 with unbounded fanout gates, denoted QACwf^0, is the same as QACC[q] and QACC for all q. Since \ACC[p] \ne ACC[q] whenever p and q are distinct primes, QACC[q] is strictly more powerful than its classical counterpart, as is QAC^0 when fanout is allowed. This adds to the growing list of quantum complexity classes which are provably more powerful than their classical counterparts. We also develop techniques for proving upper bounds for QACC in terms of related language classes. We define classes of languages closely related to QACC[2] and show that restricted versions of them can be simulated by polynomial-size circuits. With further restrictions, language classes related to QACC[2] operators can be simulated by classical threshold circuits of polynomial size and constant depth.

arXiv:quant-ph/0106017•Quantum Information and Computation•Jan 1, 2002•69 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•1 citation

Quantum lower bounds for fanout

Maosen Fang, Stephen Fenner, F. Green +2 more

We consider the resource bounded quantum circuit model with circuits restricted by the number of qubits they act upon and by their depth. Focusing on natural universal sets of gates which are familiar from classical circuit theory, several new lower bounds for constant depth quantum circuits are proved. The main result is that parity (and hence fanout) requires log depth quantum circuits, when the circuits are composed of single qubit and arbitrary size Toffoli gates, and when they use only constantly many ancill\ae. Under this constraint, this bound is close to optimal. In the case of a non-constant number $a$ of ancill\ae\ and $n$ input qubits, we give a tradeoff between $a$ and the required depth, that results in a non-constant lower bound for fanout when $a = n^{1-o(1)}$. We also show that, regardless of the number of ancill\ae\, arbitrary arity Toffoli gates cannot be simulated exactly by a constant depth circuit family with gates of bounded arity.

arXiv:quant-ph/0312208•Quantum Information and Computation•Jan 1, 2006•43 citations

Shallow Quantum Circuits with Uninitialized Ancillary Qubits.

Yasuhiro Takahashi, Seiichiro Tani

We study the computational power of shallow quantum circuits with $n$ input qubits, one output qubit, and two types of ancillary qubits: $O(\log n)$ initialized and $O({\rm poly}(n))$ uninitialized qubits. The initial state of the uninitialized ancillary qubits is arbitrary, and we have to return their state into the initial one at the end of the computation. First, to show the strengths of such circuits, we consider a class of symmetric functions on $n$ bits, including those (such as threshold functions) for which it is not known whether there exist shallow quantum circuits with only $O(\log n)$ initialized ancillary qubits. We show that there exists an $O(\log^2 n)$-depth quantum circuit for any function in the class with $O(\log n)$ initialized and $O(n\log^2 n)$ uninitialized ancillary qubits. Its existence shows the possibility that augmenting uninitialized ancillary qubits increases the computational power of shallow quantum circuits. The depth decreases to $O(\log n)$ when we use unbounded fan-out gates and unbounded Toffoli gates. Then, we consider the limitations of shallow quantum circuits with uninitialized ancillary qubits, which include unbounded fan-out gates and unbounded Toffoli gates. We show that, when the number of qubits on which unbounded fan-out gates act is $O({\rm poly}(\log n))$, for any constant $0 \leq \delta <1$, there does not exist an $O(\log^{\delta} n)$-depth quantum circuit for the parity function on $n$ bits with $O(\log n)$ initialized and $O({\rm poly}(n))$ uninitialized ancillary qubits.

•Aug 25, 2016•0 citations

$\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•10 citations
The relevance of shallow-depth quantum circuits has recently increased, mainly due to their applicability to near-term devices. In this context, one of the main goals of quantum circuit complexity is to find problems that can be solved by quantum shallow circuits but require more computational resources classically. Our first contribution in this work is to prove new separations between classical and quantum constant-depth circuits. Firstly, we show a separation between constant-depth quantum circuits with quantum advice (\mathsf {QNC}^0/\mathsf {qpoly} ) , and (\mathsf {AC}^0[p] ) , which is the class of classical constant-depth circuits with unbounded-fan in and (\mathsf {MOD}_{p} ) gates. Additionally, we show a separation between (\mathsf {QAC}^0 ) , the circuit class containing Toffoli gates with unbounded control, and (\mathsf {AC}^0[p] ) , when (\mathsf {QAC}^0 ) is augmented with additional mid-circuit measurements and classical fanout. This establishes the first such separation for a shallow-depth quantum class that does not involve quantum fanout gates, while relying solely on finite quantum gate sets. Equivalently, this yields a separation between (\mathsf {AC}^0[p] ) and ([\mathsf {QNC}^0, \mathsf {AC}^0]^2 ) , i.e., shallow quantum circuits interleaved with simple classical computation. Secondly, we consider (\mathsf {QNC}^0 ) circuits with infinite-size gate sets. We show that these circuits, along with quantum prime modular gates or classical prime modular gates in combination with classical fanout, can implement threshold gates, showing that (\mathsf {QNC}^0[p]=\mathsf {QTC}^0 ) . Finally, we also show that in the infinite-size gate set case, these quantum circuit classes for higher-dimensional Hilbert spaces do not offer any advantage to standard qubit implementations.
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.
We propose definitions of QAC^0, the quantum analog of the classical class AC^0 of constant-depth circuits with AND and OR gates of arbitrary fan-in, and QACC[q], the analog of the class ACC[q] where Mod_q gates are also allowed. We prove that parity or fanout allows us to construct quantum MOD_q gates in constant depth for any q, so QACC[2] = QACC. More generally, we show that for any q,p > 1, MOD_q is equivalent to MOD_p (up to constant depth and polynomial size). This implies that QAC^0 with unbounded fanout gates, denoted QACwf^0, is the same as QACC[q] and QACC for all q. Since \ACC[p] \ne ACC[q] whenever p and q are distinct primes, QACC[q] is strictly more powerful than its classical counterpart, as is QAC^0 when fanout is allowed. This adds to the growing list of quantum complexity classes which are provably more powerful than their classical counterparts. We also develop techniques for proving upper bounds for QACC in terms of related language classes. We define classes of languages closely related to QACC[2] and show that restricted versions of them can be simulated by polynomial-size circuits. With further restrictions, language classes related to QACC[2] operators can be simulated by classical threshold circuits of polynomial size and constant depth.
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.
We consider the resource bounded quantum circuit model with circuits restricted by the number of qubits they act upon and by their depth. Focusing on natural universal sets of gates which are familiar from classical circuit theory, several new lower bounds for constant depth quantum circuits are proved. The main result is that parity (and hence fanout) requires log depth quantum circuits, when the circuits are composed of single qubit and arbitrary size Toffoli gates, and when they use only constantly many ancill\ae. Under this constraint, this bound is close to optimal. In the case of a non-constant number aaa of ancill\ae\ and nnn input qubits, we give a tradeoff between aaa and the required depth, that results in a non-constant lower bound for fanout when a=n1−o(1)a = n^{1-o(1)}a=n1−o(1). We also show that, regardless of the number of ancill\ae\, arbitrary arity Toffoli gates cannot be simulated exactly by a constant depth circuit family with gates of bounded arity.
We study the computational power of shallow quantum circuits with nnn input qubits, one output qubit, and two types of ancillary qubits: O(log⁡n)O(\log n)O(logn) initialized and O(poly(n))O({\rm poly}(n))O(poly(n)) uninitialized qubits. The initial state of the uninitialized ancillary qubits is arbitrary, and we have to return their state into the initial one at the end of the computation. First, to show the strengths of such circuits, we consider a class of symmetric functions on nnn bits, including those (such as threshold functions) for which it is not known whether there exist shallow quantum circuits with only O(log⁡n)O(\log n)O(logn) initialized ancillary qubits. We show that there exists an O(log⁡2n)O(\log^2 n)O(log2n)-depth quantum circuit for any function in the class with O(log⁡n)O(\log n)O(logn) initialized and O(nlog⁡2n)O(n\log^2 n)O(nlog2n) uninitialized ancillary qubits. Its existence shows the possibility that augmenting uninitialized ancillary qubits increases the computational power of shallow quantum circuits. The depth decreases to O(log⁡n)O(\log n)O(logn) when we use unbounded fan-out gates and unbounded Toffoli gates. Then, we consider the limitations of shallow quantum circuits with uninitialized ancillary qubits, which include unbounded fan-out gates and unbounded Toffoli gates. We show that, when the number of qubits on which unbounded fan-out gates act is O(poly(log⁡n))O({\rm poly}(\log n))O(poly(logn)), for any constant 0≤δ<10 \leq \delta <10≤δ<1, there does not exist an O(log⁡δn)O(\log^{\delta} n)O(logδn)-depth quantum circuit for the parity function on nnn bits with O(log⁡n)O(\log n)O(logn) initialized and O(poly(n))O({\rm poly}(n))O(poly(n)) uninitialized ancillary qubits.
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.