Source-linked AI summary
Fast and efficient exact synthesis of single qubit unitaries generated by Clifford and T gates
Vadym Kliuchnikov, Dmitri Maslov, Michele Mosca
TL;DR
Exact synthesis with finite quantum gate sets requires deciding whether a target unitary is exactly implementable and, when it is, finding an efficient decomposition. This paper characterizes the single-qubit Clifford+T unitaries algebraically and gives an efficient, gate-optimal synthesis algorithm.
Problem
The paper addresses how to decide exact Clifford+T synthesizability and efficiently construct an exact single-qubit circuit when one exists.
Method
The paper relates single-qubit Clifford+T circuits to the ring Z[1/√2,i] and develops an algorithm for exact synthesis using H, Z, P, and T gates.
Results
Single-qubit unitaries over Z[1/√2,i] are exactly the unitaries implementable with H and T gates, and the algorithm achieves asymptotically optimal runtime and H- and T-counts.
Takeaways & Limitations
The resulting criterion distinguishes exactly implementable unitaries from those requiring approximation, including QFT rotations Rx(π/2^m) for m > 3.
Takeaways & Limitations
The corresponding equivalence for n-qubit unitaries with one ancillary qubit remains conjectured, although the paper proves ancilla necessity.
Abstract
from arXiv · showhide
In this paper, we show the equivalence of the set of unitaries computable by the circuits over the Clifford and T library and the set of unitaries over the ring $\mathbb{Z}[\frac{1}{\sqrt{2}},i]$, in the single-qubit case. We report an efficient synthesis algorithm, with an exact optimality guarantee on the number of Hadamard and T gates used. We conjecture that the equivalence of the sets of unitaries implementable by circuits over the Clifford and T library and unitaries over the ring $\mathbb{Z}[\frac{1}{\sqrt{2}},i]$ holds in the $n$-qubit case.
1 Introduction
The introduction frames exact synthesis as the problem of determining and efficiently finding exact Clifford+T decompositions, beyond approximate universality. It motivates this focus by noting that implementation errors include the inability to realize a desired transformation exactly.
- Exact synthesis: The paper studies exact synthesis: whether a single-qubit unitary has a Clifford+T implementation and, when it does, how to find one.Clifford gates include Hadamard and Phase gates in the single-qubit setting; CNOT is additionally included for multiple qubits.
- Approximation versus exactness: Solovay–Kitaev provides provably efficient approximation over an approximately universal gate library, but neither guarantees exact decomposition nor decides whether one exists.For multiple qubits, decomposition into CNOT and single-qubit gates can be used with results from [2].
- Motivation: Exact synthesis is motivated by implementation errors from algorithmic probability, decoherence, control imperfections, and inability to implement a desired transformation exactly [4].The introduction presents these as multiple error sources affecting quantum-algorithm implementations.
- Paper organization: The paper proceeds from a state-preparation reduction to technical lemmas and an efficient Hadamard-and-T decomposition algorithm, with minimality proved for its Hadamard and T gate count.The introduction states that subsequent sections provide the required proofs and minor technical results.
2 Formulation and discussion of the results
The section establishes an exact characterization of single-qubit unitaries over Z[1/√2, i] and presents an efficient synthesis algorithm with H- and T-optimality guarantees. It also conjectures an n-qubit extension requiring one ancilla and explains why that ancilla is essential.
- Exact characterization: Theorem 1 equates 2 × 2 unitaries over Z[1/√2, i] with those exactly implementable by single-qubit H- and T-gate circuits.The circuit-to-ring inclusion follows from ring closure under matrix multiplication, while the inverse inclusion is proved in Sections 3–5 and Appendix A.
- Multi-qubit conjecture: Conjecture 1 extends the characterization to n > 1 by allowing Clifford-and-T circuits on n+1 qubits with one ancilla initialized and returned to |0⟩.The ancilla may be unused when unnecessary, but its inclusion is essential to the conjectured statement.
- Multi-qubit conjecture: The controlled-T gate demonstrates the ancilla requirement: its determinant is ω, unlike the i-power determinants of two-qubit Clifford-and-T circuits, but it can be implemented with an ancilla on three qubits [5].With the ancilla, the determinant obstruction based on the full system no longer applies.
- Implications: The theorem provides a criterion showing that Rx(π/2^m), for m > 3, cannot be implemented exactly, and the conjecture implies QFTs on more than three qubits require approximation.Thus approximation error may be unavoidable for some quantum computations.
- Synthesis algorithm: Algorithm 1 synthesizes single-qubit circuits using H, Z:=T^4, P:=T^2, and T in O(n_opt) time, where n_opt is the minimum required gate count.With constant-time ring operations, the algorithm is asymptotically optimal in speed and quality; bit-operation complexity is quadratic in n_opt.
- Optimality guarantees: The circuits synthesized by Algorithm 1 are formally both H-optimal and T-optimal, improving on [6], which guarantees only T-optimality.The implementation also permits a trade-off between the numbers of Phase and Pauli-Z gates, while Pauli-X and Pauli-Y gates total at most three.
3 Reducing unitary implementation to state preparation
This section reduces exact single-qubit unitary implementation to preparing the unitary’s first column. State-preparation and unitary-implementation circuit lengths are equivalent up to an additive O(1) overhead for H and T circuits.
- Any single-qubit state with entries in Z[1/√2, i] can be prepared from |0⟩ using only H and T gates.
- For ring-valued single-qubit unitaries, the determinant has unit modulus and the only ring elements of absolute value 1 are powers of ω.These facts constrain the general form of ring-valued unitaries and support the reduction to first-column preparation.
- Preparing a unitary’s first column enables construction of a circuit implementing the full unitary, with only constant additional gates.The construction synthesizes all compatible unitaries by multiplying by a power of T from the right.
- A state-preparation circuit of length n yields a unitary-implementation circuit of length n + O(1), and the converse also holds.
4 Sequence for state preparation
This section develops denominator-exponent tools and lemmas for reducing unitaries over Z[1/√2, i] to H and T circuits. Algorithm 1 repeatedly lowers the smallest denominator exponent, finishes by breadth-first search, and achieves asymptotically optimal circuit length and the stated runtime bounds.
- Denominator exponents: The smallest denominator exponent is defined through divisibility in Z[ω], while the greatest dividing exponent provides the relation needed to analyze its changes.The smallest denominator exponent is the least k such that z x^k belongs to Z[ω], and the greatest dividing exponent is the largest k for which x^k divides z.
- State preparation: The lemmas show that suitable powers of T followed by H can realize denominator-exponent changes of −1, 0, or 1, enabling preparation of ring-valued states from |0⟩.For almost all unit vectors, choosing an appropriate power of ω realizes all possible values of the relevant difference; low-exponent states are exhaustively checked by breadth-first search.
- Algorithm 1: Algorithm 1 reduces an entry’s smallest denominator exponent by 1 per H(T)^k step when the exponent is at least 4, then uses breadth-first search for the finite remainder.The reduction uses k ∈ {0, 1, 2, 3}; after n − 4 steps, all entries have smallest denominator exponent below 4.
- Complexity: Algorithm 1 produces circuits of length O(nopt(U)) using O(nopt(U)) arithmetic operations and O(n^2_opt(U)) bit operations.The complexity follows from the number of denominator-reduction steps and the cost of storing and updating the unitary entries.
- Optimality: Except for a finite set, circuit length and the unitary’s denominator exponent are asymptotically equivalent, so the algorithm runs in O(ng(U)) time and produces H- and T-optimal circuits.The section establishes an upper bound proportional to the denominator exponent and concludes that the algorithm’s circuits are optimal in Hadamard and T gates.
5 Quadratic forms and greatest dividing exponent
The section reduces the proof of Lemma 3 from infinitely many ring elements to finitely many residue classes modulo 23, using quadratic forms and greatest-dividing-exponent relations. An exhaustive computer search verifies all resulting cases and returns true.
- Quadratic forms and greatest dividing exponent: Real elements of Z[ω] have the form a + b√2, and Proposition 1 characterizes their base-2 greatest-dividing exponent through the exponents of the integer coefficients a and b.The two cases depend on whether gde(b, 2) is at least gde(a, 2) or strictly smaller, determining which coefficient controls the resulting exponent relation.
- Quadratic forms and greatest dividing exponent: The quadratic forms P and Q encode real elements of Z[ω] from their integer-coordinate representation and support the modular characterization used in the finite check.For x = x0 + x1ω + x2ω2 + x3ω3, Q is defined from the integer coordinates, and the values of P and Q modulo 23 follow from those coefficients modulo 23.
- Finite reduction: Because the relevant quadratic forms depend only on integer coefficients modulo 23, the infinite verification reduces to finitely many residue classes, with additional norm and exponent constraints.The residue-class search replaces the sets G_j by larger sets Q_j so the lemma’s conditions can be checked finitely, despite the large number of equivalence classes.
- Proof of Lemma 3: An implemented exhaustive computer search verifies Algorithm 2 and returns true, completing the proof of Lemma 3.The verification checks the reformulated statement over residue-vector equivalence classes rather than the original infinite sets.
7 Experimental results
Experiments combine Solovay–Kitaev approximation with the paper’s exact synthesis algorithm, showing faster decomposition and reduced gate counts after resynthesis. Controlled-rotation quality is evaluated with completely bounded trace norm, yielding an error roughly three times the corresponding single-qubit trace-distance error.
- Experimental results: Exact decomposition was significantly faster than the Solovay–Kitaev approximation stage, while Table 2 reports approximating circuits generated through this combined pipeline.The experiments used the authors’ implementation of Algorithm 1 after Solovay–Kitaev approximation over Z[1/√2, i].
- Experimental results: The approximation experiments used a single 3.40GHz Intel Core i7-2600 core and required 2.1GB of RAM during unitary approximation.Dawson’s comparison used around 6GB of memory, with maximal sequence length 22 and tile width 0.14.
- Experimental results: The controlled-Rz(φ) construction uses one ancillary qubit initialized to |0⟩, introduces no phase, and supports approximate QFT implementations because controlled rotations occur in the standard QFT.The circuit is shown in Figure 2 and uses the technique from.
- Experimental results: Resynthesizing Dawson’s circuits with the exact decomposition algorithm reduced gate counts by about 10–20% in most cases.This result applies to circuits generated with Dawson’s {H,T} implementation and subsequently decomposed over the {H,T} library.
8 Conclusion
The paper establishes exact equivalence between single-qubit Clifford+T unitaries and unitaries over Z[1/√2,i], and presents an asymptotically efficient synthesis algorithm with provably minimal Hadamard and T counts. It conjectures an ancilla-assisted n-qubit generalization, while showing ancillas are necessary.
- Single-qubit unitaries computable by Clifford+T circuits are exactly the unitaries over Z[1/√2,i].
- The paper conjectures the same equivalence for n-qubit circuits when one ancillary qubit initialized to |0⟩ is supplied, but proves only that an ancilla is necessary.
- The single-qubit synthesis algorithm is asymptotically optimal in both its performance guarantee and complexity, generating circuits with provably minimal Hadamard and T-gate counts.
- Experiments suggest that the algorithm’s P-counts may also be minimal, while its generated circuits use Pauli-X and Pauli-Y gates at most three times in total.
Appendix A
Appendix A proves foundational properties of the greatest dividing exponent (gde) and develops quadratic and bilinear forms used to analyze it. It establishes parity characterizations for elements with gde(x)=0 and connects these forms to later divisibility arguments.
- Properties of gde: The appendix proves the base-extraction property of gde and derives lower bounds, sum inequalities, and the absorption property from it.If x^k divides y, then gde(y,x) ≥ k; the sum inequality follows because x^min(gde(y,x),gde(y′,x)) divides y+y′.
- Quadratic and bilinear forms: The appendix defines F(x,y)=x0y0+x1y1+x2y2+x3y3 and shows that it generalizes the earlier quadratic forms P(x) and Q(x).Modulo-2 identities for these forms provide the algebraic framework for proving relations involving Re(2xy*).
- Parity properties: For x with gde(x)=0, Proposition 3 shows that exactly one parity pattern holds: P(x) is even and Q(x) odd, or P(x) is odd and Q(x) even.This follows by expressing the relevant coefficients modulo 2 and showing that P(x) and Q(x) have different parity.
Appendix B
Appendix B proves that Algorithm 1 synthesizes circuits implementing eligible single-qubit unitaries with minimal Hadamard and T-gate counts over the specified gate library. The proof establishes these optima through smallest-denominator exponents, brute-force base cases, and an HT-normal circuit form.
- H-optimality: Algorithm 1 achieves H-optimality, with h(U) = sde(|z|^2) − 1 for eligible 2×2 unitaries U over Z[1/√2, i].The theorem applies when U has a matrix entry z satisfying sde(|z|^2) ≥ 4.
- T-optimality: The algorithm also achieves T-optimality, with t(U) = h(U)−1+(l mod 2)+(j mod 2), where l and j satisfy h(HT^lUT^jH) = h(U) + 2.The gate library includes H, T, T†, P, P†, and the Pauli-X, Y, and Z gates.
- H-optimality: H-optimality is anchored by brute-force verification at sde(|z|^2) = 4 and extended to larger exponents by reducing them to this base case with Algorithm 1.The reduction uses n − 4 Hadamard gates when sde(|z|^2) = n ≥ 4, yielding a circuit with n − 1 Hadamard gates.
- T-optimality: For T-optimality, Algorithm 1 can preserve H-optimality while producing HT-normal circuits, and the proof reduces general circuits to the case beginning and ending with H gates.In the special case HS1H…HSkH, HT-normality gives k T gates and h(U) = k + 1, so T-optimality requires t(U) = h(U) − 1.