Source-linked AI summary
Quantum circuits of T-depth one
Peter Selinger
TL;DR
The paper studies cost-aware Clifford+T decompositions, focusing on reducing T-depth when T-gates are expensive and ancillas are available. It gives T-depth-one constructions for a class of circuits, while proving that some circuits, including THT, cannot achieve T-depth one regardless of ancilla count.
Problem
Finding Clifford+T decompositions optimized for costs such as T-gate count, circuit depth, and ancilla use is an important problem.
Method
The paper constructs T-depth-one representations by copying Boolean conditions for T-gates into ancillas, executing the T-gates in parallel, and uncomputing the ancillas.
Results
The paper identifies circuits whose T-depth can be reduced to one with sufficiently many ancillas and proves that some circuits cannot reach T-depth one regardless of ancilla count.
Takeaways & Limitations
T-depth reduction is possible for a broad class of circuits, but determining the minimal T-depth or T-count of an arbitrary Clifford+T circuit remains open.
Takeaways & Limitations
Reducing T-depth trades against ancilla count: splitting a circuit can approximately halve ancillas by doubling T-depth, and analogous trade-offs continue.
Abstract
from arXiv · showhide
We give a Clifford+T representation of the Toffoli gate of T-depth 1, using four ancillas. More generally, we describe a class of circuits whose T-depth can be reduced to 1 by using sufficiently many ancillas. We show that the cost of adding an additional control to any controlled gate is at most 8 additional T-gates, and T-depth 2. We also show that the circuit THT does not possess a T-depth 1 representation with an arbitrary number of ancillas initialized to 0.
1 Introduction
The introduction frames Clifford+T decomposition as an optimization problem whose relevant costs include T-count, T-depth, circuit depth, and ancilla use. It motivates reducing Toffoli and other circuits to T-depth one when ancillas are cheap.
- Clifford+T decomposition is important for approximating arbitrary gates within a specified accuracy.
- T-depth counts parallel T-stages rather than individual T-gates.A T-stage contains T- or T†-gates on distinct qubits that can execute simultaneously.
- The standard Toffoli decomposition has T-count 7 and exact-form T-depth 6, reducible to T-depth 4 by trivial commutations.
- Amy et al. reduced ancilla-free Toffoli T-depth to 3 and conjectured that this is optimal without ancillas.
- Using ancillas, the paper aims to reduce Toffoli and many other circuits to T-depth 1, especially where T-gates are expensive and ancillas are cheap.
2 A T-depth one representation of the Toffoli gate
The Toffoli gate is transformed into a doubly-controlled Z-gate and decomposed into phase operations on Boolean parities. Four ancillas allow all required T and T† gates to run in one T-stage.
- The Toffoli gate is a doubly-controlled NOT and is equivalent to a doubly-controlled Z through basis change.
- The doubly-controlled Z applies phase (−1)^xyz to computational basis state |xyz⟩.
- The phase is decomposed using ω = (−1)^(1/4) = e^(iπ/4), enabling T and T† operations on individual bits and their pairwise or triple parities.
- Four ancillas permit the seven phase gates to be applied in parallel, yielding a Toffoli representation with T-depth 1 and overall depth 7.
- Earlier Toffoli decompositions follow the same phase-decomposition pattern, with one T-gate needlessly split into T† and S.
3 An application to multiply-controlled gates
The paper extends the phase-decomposition method to multiply-controlled gates and controlled gates more generally. Each added control costs at most 8 T-gates and increases T-depth by at most 2, with trade-offs in depth and ancillas.
- The combined doubly-controlled Z and controlled S† construction requires T-count 4 and can achieve T-depth 1 with one ancilla.Its overall depth is 5; an ancilla-free alternative has T-depth 2 and overall depth 7.
- 8 additional T-gates, T-depth increase of at most 2, and overall-depth increase of at most 14 suffice to add one control using two ancillas.
- Adding n controls costs T-count 8n and T-depth 2⌊log2 n + 1⌋.The logarithmic T-depth follows because each pair of T-stages can double the number of controls.
- A triply-controlled NOT uses T-count 15 and T-depth 3, while a quintuply-controlled NOT uses T-count 31 and T-depth 5.The optimality of these T-counts and depths is not known.
- One construction gives T-depth 3, depth 15, and gate count 29 with two ancillas; another uses one ancilla but raises T-depth to 5 and depth to 19.The two-ancilla gate count can be reduced to 27 by retaining an ancilla in state |x⟩.
- The procedure exposes a trade-off between overall gate count, T-depth, depth, and ancilla use.
4 T-depth one representation of almost classical circuits
The paper shows that circuits built from T gates and almost classical gates can be represented with T-depth 1 using ancillas. The construction separates diagonal and T-depth-zero components, while trading additional ancillas and circuit size against reduced T-depth.
- Scope and cost: The construction generalizes to circuits built from T gates and almost classical gates, with the resulting circuit typically increasing in size by only a constant factor.The paper notes that smaller circuits than the proof construction are often possible in practice.
- Definitions: Almost classical operators are products of a classical operator and a diagonal operator, and they form a group.Among single-qubit Clifford operators modulo global phase, exactly 8 are almost classical and are generated by S and X.
- Theorem 4.1: Any C + T-representable n-qubit circuit has T-depth 1 relative to C when C contains CNOT and consists of almost classical gates.The theorem permits C to include gates beyond Clifford gates, provided they satisfy the almost classical condition.
- Proof strategy: Each T gate’s phase condition is copied to an ancilla, all T gates are executed in parallel, and the ancillas are then uncomputed.This is the intuitive construction underlying the formal proof.
- Proof strategy: The inductive proof decomposes every circuit A into A2 ◦ A1, where A1 is diagonal with T-depth at most 1 and A2 has T-depth 0.The construction proceeds by induction on the circuit and preserves the required decomposition through each added gate.
- Scope and cost: Splitting a T-count n circuit into two parts of T-count ⌈n/2⌉ approximately halves ancilla usage while doubling T-depth.This establishes an explicit trade-off between parallelism and workspace.
5 Some circuits cannot be written with T-depth one
The paper proves that THT cannot have a T-depth 1 Clifford+T implementation, even with arbitrarily many zero-initialized ancillas. The proof derives a rationality constraint for certain Pauli expectations in all T-depth 1 circuits, then exhibits an irrational expectation for THT.
- Impossibility result: THT cannot be implemented with T-depth 1 using any number of ancillas initialized to |0⟩, even when ancillas need not be restored.This is the paper’s Theorem 5.1.
- General observation: T-depth 1 circuits can be decomposed into Clifford circuits surrounding one simultaneous T-stage.This structural form enables analysis of conjugated Pauli observables.
- Proof structure: The conjugated observable has Pauli-sum terms sharing a common factor λ, where λ=(1/√2)^k and k counts X and Y factors.Clifford conjugation maps the resulting operators back to Pauli operators, preserving the common scaling structure.
- Impossibility result: For U=THT, the ratio E|0⟩/E|+⟩ is irrational, contradicting the rationality property required by Proposition 5.1.The contradiction establishes the impossibility result.
6 Conclusion
The paper identifies both circuits reducible to T-depth one with enough ancillas and circuits that remain irreducible regardless of ancilla count. Determining minimum T-depth or T-count for arbitrary Clifford+T circuits remains open.
- Conclusion: The paper finds a class of circuits whose T-depth can be reduced to one using sufficiently many ancillas.
- Conclusion: Other circuits cannot have their T-depth reduced to one, regardless of the number of ancillas used.
- Conclusion: Determining the minimal T-depth or T-count of an arbitrary Clifford+T circuit remains an open problem.