Shallow Quantum Circuits with Uninitialized Ancillary Qubits.

Yasuhiro Takahashi, Seiichiro Tani

Published Aug 25, 2016• 0 citations

Abstract

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.

Related papers

Quantum addition circuits and unbounded fan-out

Yasuhiro Takahashi, Seiichiro Tani, Noboru Kunihiro

arXiv:0910.2530Quantum Information and ComputationSep 1, 2010119 citations

The Power of Shallow-depth Toffoli and Qudit Quantum Circuits

Alex B. Grilo, Elham Kashefi, Damian Markham +1 more

arXiv:2404.18104ACM Transactions on Quantum ComputingMay 18, 20263 citations

The power of constant-depth quantum circuits of unbounded size

Sergii Strelchuk, Sathyawageeswar Subramanian, Máté Weisz

quant-pharXiv:2609.40294Oct 1, 20260 citations

Low-degree approximation of QAC$^0$ circuits

Ashley Montanaro, Changpeng Shao, Dominic Verdon

arXiv:2411.00976Nov 1, 20240 citations

Depth-Optimal Quantum Compilation

Francisca Vasconcelos

quant-pharXiv:2609.34659Sep 29, 20260 citations

Shallow Quantum Circuit Implementation of Symmetric Functions With Limited Ancillary Qubits

Wei Zi, Junhong Nie, Xiaoming Sun

arXiv:2404.06052IEEE Transactions on Computer-Aided Design of Integrated Circuits and SystemsFeb 5, 20254 citations

Shallow Quantum Circuits with Uninitialized Ancillary Qubits.

Yasuhiro Takahashi, Seiichiro Tani

Published Aug 25, 2016• 0 citations

OpenAlex

Abstract

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.

Related papers

Quantum addition circuits and unbounded fan-out

Yasuhiro Takahashi, Seiichiro Tani, Noboru Kunihiro

We first show how to construct an $O(n)$ -depth $O(n)$ -size quantum circuit for addition of two $n$ -bit binary numbers with no ancillary qubits. The exact size is $7n-6$ , which is smaller than that of any other quantum circuit ever constructed for addition with no ancillary qubits. Using the circuit, we then propose a method for constructing an $O(d(n))$ -depth $O(n)$ -size quantum circuit for addition with $O(n/d(n))$ ancillary qubits for any $d(n) = \Omega(\log n)$ . If we are allowed to use unbounded fan-out gates with length $O(n^{\varepsilon})$ for an arbitrary small positive constant $\varepsilon$ , we can modify the method and construct an $O(e(n))$ -depth $O(n)$ -size circuit with $o(n)$ ancillary qubits for any $e(n) = \Omega(\log^* n)$ . In particular, these methods yield efficient circuits with depth $O(\log n)$ and with depth $O(\log^* n)$ , respectively. We apply our circuits to constructing efficient quantum circuits for Shor's discrete logarithm algorithm.We first show how to construct an $O(n)$-depth $O(n)$-size quantum circuit for addition of two $n$-bit binary numbers with no ancillary qubits. The exact size is $7n-6$, which is smaller than that of any other quantum circuit ever constructed for addition with no ancillary qubits. Using the circuit, we then propose a method for constructing an $O(d(n))$-depth $O(n)$-size quantum circuit for addition with $O(n/d(n))$ ancillary qubits for any $d(n) = \Omega(\log n)$. If we are allowed to use unbounded fan-out gates with length $O(n^{\varepsilon})$ for an arbitrary small positive constant $\varepsilon$, we can modify the method and construct an $O(e(n))$-depth $O(n)$-size circuit with $o(n)$ ancillary qubits for any $e(n) = \Omega(\log^* n)$. In particular, these methods yield efficient circuits with depth $O(\log n)$ and with depth $O(\log^* n)$, respectively. We apply our circuits to constructing efficient quantum circuits for Shor's discrete logarithm algorithm.

arXiv:0910.2530Quantum Information and ComputationSep 1, 2010119 citations

The Power of Shallow-depth Toffoli and Qudit Quantum Circuits

Alex B. Grilo, Elham Kashefi, Damian Markham +1 more

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.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.

arXiv:2404.18104ACM Transactions on Quantum ComputingMay 18, 20263 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.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.40294Oct 1, 20260 citations

Low-degree approximation of QAC $^0$ circuitsLow-degree approximation of QAC$^0$ circuits

Ashley Montanaro, Changpeng Shao, Dominic Verdon

QAC $^0$ is the class of constant-depth quantum circuits with polynomially many ancillary qubits, where Toffoli gates on arbitrarily many qubits are allowed. In this work, we show that the parity function cannot be computed in QAC $^0$ , resolving a long-standing open problem in quantum circuit complexity more than twenty years old. As a result, this proves ${\rm QAC}^0 \subsetneqq {\rm QAC}_{\rm wf}^0$ . We also show that any QAC circuit of depth $d$ that approximately computes parity on $n$ bits requires $2^{\widetildeΩ(n^{1/d})}$ ancillary qubits, which is close to tight. This implies a similar lower bound on approximately preparing cat states using QAC circuits. Finally, we prove a quantum analog of the Linial-Mansour-Nisan theorem for QAC $^0$ . This implies that, for any QAC $^0$ circuit $U$ with $a={\rm poly}(n)$ ancillary qubits, and for any $x\in\{0,1\}^n$ , the correlation between $Q(x)$ and the parity function is bounded by ${1}/{2} + 2^{-\widetildeΩ(n^{1/d})}$ , where $Q(x)$ denotes the output of measuring the output qubit of $U|x,0^a\rangle$ . All the above consequences rely on the following technical result. If $U$ is a QAC $^0$ circuit with $a={\rm poly}(n)$ ancillary qubits, then there is a distribution $\mathcal{D}$ of bounded polynomials of degree polylog $(n)$ such that with high probability, a random polynomial from $\mathcal{D}$ approximates the function $\langle x,0^a| U^†Z_{n+1} U |x,0^a\rangle$ for a large fraction of $x\in \{0,1\}^n$ . This result is analogous to the Razborov-Smolensky result on the approximation of AC $^0$ circuits by random low-degree polynomials.QAC$^0$ is the class of constant-depth quantum circuits with polynomially many ancillary qubits, where Toffoli gates on arbitrarily many qubits are allowed. In this work, we show that the parity function cannot be computed in QAC$^0$, resolving a long-standing open problem in quantum circuit complexity more than twenty years old. As a result, this proves ${\rm QAC}^0 \subsetneqq {\rm QAC}_{\rm wf}^0$. We also show that any QAC circuit of depth $d$ that approximately computes parity on $n$ bits requires $2^{\widetildeΩ(n^{1/d})}$ ancillary qubits, which is close to tight. This implies a similar lower bound on approximately preparing cat states using QAC circuits. Finally, we prove a quantum analog of the Linial-Mansour-Nisan theorem for QAC$^0$. This implies that, for any QAC$^0$ circuit $U$ with $a={\rm poly}(n)$ ancillary qubits, and for any $x\in\{0,1\}^n$, the correlation between $Q(x)$ and the parity function is bounded by ${1}/{2} + 2^{-\widetildeΩ(n^{1/d})}$, where $Q(x)$ denotes the output of measuring the output qubit of $U|x,0^a\rangle$. All the above consequences rely on the following technical result. If $U$ is a QAC$^0$ circuit with $a={\rm poly}(n)$ ancillary qubits, then there is a distribution $\mathcal{D}$ of bounded polynomials of degree polylog$(n)$ such that with high probability, a random polynomial from $\mathcal{D}$ approximates the function $\langle x,0^a| U^†Z_{n+1} U |x,0^a\rangle$ for a large fraction of $x\in \{0,1\}^n$. This result is analogous to the Razborov-Smolensky result on the approximation of AC$^0$ circuits by random low-degree polynomials.

arXiv:2411.00976Nov 1, 20240 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.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.34659Sep 29, 20260 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.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.06052IEEE Transactions on Computer-Aided Design of Integrated Circuits and SystemsFeb 5, 20254 citations

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))

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)

O(\log n)

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.

We first show how to construct an

O(n)

-depth

O(n)

-size quantum circuit for addition of two

n

-bit binary numbers with no ancillary qubits. The exact size is

7n-6

, which is smaller than that of any other quantum circuit ever constructed for addition with no ancillary qubits. Using the circuit, we then propose a method for constructing an

O(d(n))

-depth

O(n)

-size quantum circuit for addition with

O(n/d(n))

ancillary qubits for any

d(n) = \Omega(\log n)

. If we are allowed to use unbounded fan-out gates with length

O(n^{\varepsilon})

for an arbitrary small positive constant

\varepsilon

, we can modify the method and construct an

O(e(n))

-depth

O(n)

-size circuit with

o(n)

ancillary qubits for any

e(n) = \Omega(\log^* n)

. In particular, these methods yield efficient circuits with depth

O(\log n)

and with depth

O(\log^* n)

, respectively. We apply our circuits to constructing efficient quantum circuits for Shor's discrete logarithm algorithm.

\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.

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.

Low-degree approximation of QAC

^0

circuits

QAC

^0

is the class of constant-depth quantum circuits with polynomially many ancillary qubits, where Toffoli gates on arbitrarily many qubits are allowed. In this work, we show that the parity function cannot be computed in QAC

^0

, resolving a long-standing open problem in quantum circuit complexity more than twenty years old. As a result, this proves

{\rm QAC}^0 \subsetneqq {\rm QAC}_{\rm wf}^0

. We also show that any QAC circuit of depth

d

that approximately computes parity on

n

bits requires

2^{\widetildeΩ(n^{1/d})}

ancillary qubits, which is close to tight. This implies a similar lower bound on approximately preparing cat states using QAC circuits. Finally, we prove a quantum analog of the Linial-Mansour-Nisan theorem for QAC

^0

. This implies that, for any QAC

^0

circuit

U

with

a={\rm poly}(n)

ancillary qubits, and for any

x\in\{0,1\}^n

, the correlation between

Q(x)

and the parity function is bounded by

{1}/{2} + 2^{-\widetildeΩ(n^{1/d})}

, where

Q(x)

denotes the output of measuring the output qubit of

U|x,0^a\rangle

. All the above consequences rely on the following technical result. If

U

is a QAC

^0

circuit with

a={\rm poly}(n)

ancillary qubits, then there is a distribution

\mathcal{D}

of bounded polynomials of degree polylog

(n)

such that with high probability, a random polynomial from

\mathcal{D}

approximates the function

\langle x,0^a| U^†Z_{n+1} U |x,0^a\rangle

for a large fraction of

x\in \{0,1\}^n

. This result is analogous to the Razborov-Smolensky result on the approximation of AC

^0

circuits by random low-degree polynomials.

δ>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.