Catalytic $z$-rotations in constant $T$-depth

Abstract

We show that the $T$-depth of any single-qubit $z$-rotation can be reduced to $3$ if a certain catalyst state is available. To achieve an $\epsilon$-approximation, it suffices to have a catalyst state of size polynomial in $\log (1/\epsilon )$. This implies that ${\mathsf{QNC}}_f^0/\mathsf{qpoly}$ admits a finite universal gate set consisting of Clifford+$T$. In particular, there are catalytic constant $T$-depth circuits that approximate multi-qubit Toffoli, adder, and quantum Fourier transform arbitrarily well. We also show that the catalyst state can be prepared in time polynomial in $\log (1/\epsilon )$.

13 pages, 4 figures, journal version

References in corpus (17)

• Surface codes: Towards practical large-scale quantum computation
• Quantum Teleportation is a Universal Computational Primitive
• A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery
• Halving the cost of quantum addition
• Quantum circuits of T-depth one
• Magic State Distillation: Not as Costly as You Think
• Efficient synthesis of universal Repeat-Until-Success circuits
• Efficient magic state factories with a catalyzed |CCZ> to 2|T> transformation
• Asymptotically optimal approximation of single qubit unitaries by Clifford and T circuits using a constant number of ancillary qubits
• Quantum Circuits with Unbounded Fan-out
• Catalysis and activation of magic states in fault tolerant architectures
• Very low overhead fault-tolerant magic state preparation using redundant ancilla encoding and flag qubits
• Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits
• Shorter quantum circuits via single-qubit gate approximation
• Efficient Magic State Distillation by Zero-Level Distillation
• Experimental Demonstration of High-Fidelity Logical Magic States from Code Switching
• Code switching revisited: Low-overhead magic state preparation using color codes