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

Allowable Generalized Quantum Gates Using Nonlinear Quantum Optics

Chun Li

理论物理通讯：英文版Jan 1, 20100 citations

Restricted allowable generalized quantum gates

Cao Huai

An allowable generalized quantum gate(introduced by Long,Liu and Wang)has the form of U 1 0 d kk k c U -= ∑,where Uk's are unitary operators on a Hilbert space H and 1 0 1 d kkc -= |∑|≤and 1 k |c|≤(0≤k≤d-1).In this work we consider a kind of AGQGs,called restricted allowable generalized quantum gates(RAGQGs),satisfying 1 0 0 1 d kk c -= ∑||≤.Some properties of the set RAGQG(H)of all RAGQGs on H are established.Especially,we prove that the extreme points of RAGQG(H)are exactly unitary operators on H and that B(H)=R+RAGQG(H).An allowable generalized quantum gate(introduced by Long,Liu and Wang)has the form of U 1 0 d kk k c U -= ∑,where Uk's are unitary operators on a Hilbert space H and 1 0 1 d kkc -= |∑|≤and 1 k |c|≤(0≤k≤d-1).In this work we consider a kind of AGQGs,called restricted allowable generalized quantum gates(RAGQGs),satisfying 1 0 0 1 d kk c -= ∑||≤.Some properties of the set RAGQG(H)of all RAGQGs on H are established.Especially,we prove that the extreme points of RAGQG(H)are exactly unitary operators on H and that B(H)=R+RAGQG(H).

Chinese Science BulletinJan 1, 20100 citations

Remarks on generalized quantum gates

Zhaoqi Wu, Shifang Zhang, Chuanxi Zhu

In this paper, we give a characterization of generalized quantum gates.We also show that many important operators are generalized quantumgates, moreover, some of these operators can be represented as theconvex combination of only two unitary operators. Our results answerwhat kinds of operations a duality quantum computing admits. Wepoint out that the set of all generalized quantum gates coincides withthe set of all restricted allowable generalized quantum gates. Thus,our results are also valid for restricted allowable generalized quantumgatesIn this paper, we give a characterization of generalized quantum gates.We also show that many important operators are generalized quantumgates, moreover, some of these operators can be represented as theconvex combination of only two unitary operators. Our results answerwhat kinds of operations a duality quantum computing admits. Wepoint out that the set of all generalized quantum gates coincides withthe set of all restricted allowable generalized quantum gates. Thus,our results are also valid for restricted allowable generalized quantumgates

Hacettepe Journal of Mathematics and StatisticsJun 1, 20145 citations

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