Source-linked AI summary
An algorithm for the T-count
David Gosset, Vadym Kliuchnikov, Michele Mosca, Vincent Russo
TL;DR
Because T gates can be costly to implement fault-tolerantly, the paper asks how to minimize their number in Clifford+T circuits. It presents an exact algorithm for COUNT-T and establishes that Toffoli and Fredkin have T-count 7, while giving a single-qubit characterization.
Problem
T gates are costly to implement fault-tolerantly, motivating the problem of finding the minimum number needed to implement a given unitary and deciding whether its T-count is at most m.
Source: §1 · pp. 1–2Method
The paper uses a meet-in-the-middle algorithm and a special representation of Clifford+T unitaries to solve COUNT-T, with polynomial overhead for converting a T-count algorithm into an optimal circuit.
Source: §1 · p. 2Results
Toffoli and Fredkin each have T-count 7, and a single-qubit unitary's T-count equals the sde of its channel representation.
Source: §4 · p. 6, §5.3 · p. 10Takeaways & Limitations
The single-qubit channel-representation characterization does not appear to generalize to multiple qubits: Toffoli has channel-representation sde 2 but T-count 7.
Source: §6 · p. 11Whether COUNT-T has a polynomial-time algorithm in N and m remains open, even for two-qubit unitaries.
Source: §6 · p. 11
Abstract
from arXiv · showhide
We consider quantum circuits composed of Clifford and T gates. In this context the T gate has a special status since it confers universal computation when added to the (classically simulable) Clifford gates. However it can be very expensive to implement fault-tolerantly. We therefore view this gate as a resource which should be used only when necessary. Given an n-qubit unitary U we are interested in computing a circuit that implements it using the minimum possible number of T gates (called the T-count of U). A related task is to decide if the T-count of U is less than or equal to m; we consider this problem as a function of N=2^n and m. We provide a classical algorithm which solves it using time and space both upper bounded as O(N^m poly(m,N)). We implemented our algorithm and used it to show that any Clifford+T circuit for the Toffoli or the Fredkin gate requires at least 7 T gates. This implies that the known 7 T gate circuits for these gates are T-optimal. We also provide a simple expression for the T-count of single-qubit unitaries.
1. Introduction
Because T gates are costly to implement fault-tolerantly, the paper studies minimizing their use in Clifford+T circuits. It formulates COUNT-T, presents an exact algorithm, and reports optimal T-counts for Toffoli and Fredkin.
1. Introduction
- The paper focuses on unitaries implementable without ancillas in the group J_n generated by the n-qubit Clifford group and T.It also places this resource-counting perspective alongside earlier work that treats quantum states as resources for Clifford computation [10].Source: §1 · pp. 1–2
- COUNT-T asks, for a given unitary U and integer m, whether T(U) is at most m; computing T(U) can also yield an optimal circuit with polynomial overhead.T(U) is the minimum number of T gates in a Clifford+T circuit implementing U up to global phase.Source: §1 · pp. 1–2
- The implemented algorithm proves that Toffoli and Fredkin each have T-count 7, making known seven-T circuits for both gates T-optimal.The paper's T-count definition excludes ancillas, though ancillas or measurements with classical control may permit fewer T gates.Source: §1 · p. 2
- The introduction also reports a simple expression for single-qubit T-count and situates the work among prior circuit-synthesis and T-count optimization approaches.It outlines later sections on decomposition, single-qubit characterization, COUNT-T, and open problems.Source: §1 · p. 2
- The paper gives an exact COUNT-T algorithm with a superexponential speedup in n over prior work and computes T-count exactly, unlike the cited heuristic.The introduction describes the algorithm's time and space upper bounds in terms of m and N.Source: §1 · p. 2
2. Preliminaries
The preliminaries establish the notation and algebraic setting for Clifford+T unitaries. They introduce the channel representation, which identifies unitaries up to global phase and respects multiplication.
2. Preliminaries
- The notation sets N = 2^n and [K] = {1, ..., K}; parenthesized subscripts specify which qubits an operator acts on.Source: §2 · p. 2
2.1. Cliffords and Paulis
- Clifford gates are generated from Hadamard and phase gates, with CNOT added for multiple qubits, and map Pauli operators to Pauli operators up to sign.Any two nonidentity Paulis can be related by an efficiently computable Clifford.Source: §2.1 · p. 3
2.2. The group Jn generated by Clifford and T gates
- The group J_n is generated by Clifford and T gates, and membership is characterized by matrix entries in the specified ring together with a determinant condition.For n ≥ 4, the determinant condition is det U = 1.Source: §2.2 · p. 3
2.3. Channel representation, and modding out global phases
- The channel representation records a unitary's action on Paulis; that action determines the unitary up to global phase and defines an N^2 × N^2 matrix.Source: §2.3 · pp. 3–4
- Channel representations are real, respect matrix multiplication, and make T-count well-defined after global phases are identified.For unitaries in J_n, their entries lie in the specified ring and in its real subring.Source: §2.3 · p. 4
3. decomposition for unitaries in Jn
The paper decomposes unitaries in Jn into Clifford and Pauli-rotation components, then uses a COUNT-T decision algorithm to construct T-optimal circuits with polynomial overhead.
3. decomposition for unitaries in Jn
- A unitary in Jn can be expressed, up to global phase, using a Clifford and T-count-many Clifford-conjugated Pauli rotations.The decomposition is the basis for converting T-count decisions into circuit synthesis.Source: §3 · pp. 4–5
Computing T-optimal circuits using an algorithm for COUNT-T
- A COUNT-T solver can be used to compute T(U) and successively identify Pauli factors, then recover a Clifford circuit for the remaining component.The procedure yields an implementation over {H, T, CNOT} with overhead polynomial in T(U) and N.Source: Computing T-optimal circuits using an… · pp. 5–6
- The resulting implementation realizes U up to global phase using the minimum number of T gates.The paper states that the construction gives a T-optimal implementation.Source: Computing T-optimal circuits using an… · p. 6
4. T-count for single-qubit unitaries
For single-qubit unitaries, the paper gives a direct characterization of T-count through the smallest denominator exponent of the channel representation.
4. T-count for single-qubit unitaries
- The smallest denominator exponent is the least k in the paper's ring representation, and a matrix's exponent is the maximum across its entries.The proof tracks this quantity in the channel representation.Source: §4 · p. 6
- For a single-qubit unitary, T(U) equals the smallest denominator exponent of its channel representation.The paper states the relation as T(U) = sde(bU).Source: §4 · p. 6
- In the lower-right 3 × 3 submatrix, two rows have sde T(U) and one row has sde T(U) − 1, labeled by the final Pauli.The paper establishes this row pattern by induction on T(U).Source: §4 · p. 7
5. Algorithm for the T-count
This section presents and proves a coset-based algorithm for COUNT-T, then uses its implementation to establish that Toffoli and Fredkin each have T-count 7 in the paper’s ancilla-free model.
5. Algorithm for the T-count
- Coset labels match exactly when two channel-representation unitaries differ by right-multiplication by a Clifford, enabling the search to compare Clifford-equivalent unitaries.The algorithm stores sorted coset databases with unique representatives for each T-count.Source: §5 · p. 8
5.1. Algorithm
- The algorithm solves COUNT-T in O(N^m poly(m,N)) time and space using coset databases and a meet-in-the-middle search.It precomputes sorted databases of representatives by T-count and searches for matching coset labels.Source: §5.1 · pp. 8–9, §5 · p. 8
5.2. Correctness of the algorithm
- The correctness argument establishes the sorted-database properties and shows the search computes T(U) when it is at most m, and otherwise reports T(U) > m.The algorithm first tests smaller T-counts, then increases the meet-in-the-middle search parameter through m.Source: §5.2 · p. 9
5.3. The T-count of Toffoli and Fredkin is 7
- Both Toffoli and Fredkin have T-count 7, making the known seven-T circuits T-optimal in the ancilla-free model.The three-qubit search found each count is at least 7; circuits using 7 T gates were already known.Source: §5.3 · p. 10, Figure 5.1 · p. 11, Figure 5.2 · p. 11
6. Conclusions and open problems
The conclusion contrasts exhaustive COUNT-T search with the single-qubit channel-sde characterization, which does not appear to extend to larger systems. Whether COUNT-T has a polynomial-time algorithm remains open, even for two-qubit unitaries.
6. Conclusions and open problems
- For single-qubit unitaries, the T-count is characterized by the sde of the channel representation, unlike the paper’s exhaustive-search approach for COUNT-T.The authors say this characterization does not appear to generalize to n > 1.Source: §6 · p. 11
- The channel-representation sde of Toffoli is 2, while its T-count is 7, illustrating the gap for a multi-qubit unitary.Source: §6 · p. 11
- Whether COUNT-T has a polynomial-time algorithm or is computationally difficult remains unknown, even for two-qubit unitaries.Source: §6 · p. 11
Appendix A. Proof of Fact 1
The proof reduces the needed Clifford-conjugation result to mapping Z(1) to any nonidentity n-qubit Pauli, using swaps, CNOTs, and single-qubit Cliffords.
Appendix A. Proof of Fact 1
- It is sufficient to prove the conjugation result for Z(1), since Clifford conjugations can map it to any nonidentity Pauli.Source: Appendix A · pp. 11–12
- The construction uses O(n) SWAP and CNOT gates followed by at most n single-qubit Clifford conjugations.Source: Appendix A · pp. 11–12