Track the frontier, from condensed matter to cosmology.
Search papers, labs, and topics across Lattice.
The authors construct the first fully unitary, catalyst-free constant-depth compilation protocol for arbitrary single-qubit gate synthesis using $O(\log^{1+\delta}(1/\varepsilon))$ clean ancillae and logarithmic-width generalized Toffoli gates. When restricted to bounded-width gates, they establish a tight $\Theta(\log\log(1/\varepsilon))$ depth bound, proving that multi-qubit gates are strictly required to collapse synthesis to $O(1)$ depth. Extending this framework to circuit complexity, they derive a depth-preserving real simulation showing that arbitrary rotations and complex amplitudes do not increase the decision power of shallow $\text{QAC}$ circuits.
Single-qubit quantum gate synthesis can achieve true constant depth without catalysts, revealing that logarithmic-width multi-qubit gates bypass the fundamental $\Theta(\log\log(1/\varepsilon))$ bounded-depth barrier while rendering complex amplitudes redundant in $\text{QAC}^0$.
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.