PaperlayerView exact revision on arXiv

Source-linked AI summary

Exact synthesis of multiqubit Clifford+T circuits

Brett Giles, Peter Selinger

arXiv:1212.0506v3quant-phcs.ET

TL;DR

Exact synthesis asks when arbitrary unitary operators can be decomposed exactly over a fixed universal gate set. This paper proves the Clifford+T characterization, establishes ancilla sufficiency, and gives an exact synthesis algorithm while characterizing ancilla-free operators.

  • Problem

    Exact synthesis seeks to determine when arbitrary unitary operators can be decomposed exactly, rather than only approximately, over a fixed universal gate set.

  • Method

    The paper proves equivalence conditions for Clifford+T representations, uses decompositions into one- and two-level matrices and known Clifford+T implementations, and derives an exact synthesis algorithm.

  • Results

    The paper proves the conjectures that one ancilla qubit always suffices for Clifford+T representations with ancillas and characterizes the Clifford+T group without ancillas.

  • Takeaways & Limitations

    The results provide a criterion for exact Clifford+T representability and a constructive route to synthesizing circuits for n-qubit operators.

  • Takeaways & Limitations

    The synthesis algorithm produces circuits very far from optimal, with a worst-case gate count separated from information-theoretic lower bounds by an exponential gap.

Abstract

from arXiv · show

We prove that a unitary matrix has an exact representation over the Clifford+T gate set with local ancillas if and only if its entries are in the ring Z[1/sqrt(2),i]. Moreover, we show that one ancilla always suffices. These facts were conjectured by Kliuchnikov, Maslov, and Mosca. We obtain an algorithm for synthesizing a exact Clifford+T circuit from any such n-qubit operator. We also characterize the Clifford+T operators that can be represented without ancillas.

1 Introduction

The paper studies exact synthesis of n-qubit operators over Clifford+T, including representations with local ancillas. It proves conjectures establishing an algebraic characterization, one-ancilla sufficiency, a synthesis algorithm, and an ancilla-free characterization, while leaving efficient synthesis open.

  • Problem: Exact synthesis decomposes arbitrary unitary operators into gates from a fixed universal set, unlike approximate synthesis, which permits error ε.The paper focuses on exact synthesis for n-qubit operators using Clifford+T.
  • Setting: Clifford+T operators with ancillas allow an n-qubit operator to be realized on n+m qubits while initializing and returning the ancillas to |0⟩.This extends the ordinary Clifford+T group used for n-qubit operators.
  • Prior work: Prior work characterized single-qubit Clifford+T operators algebraically and showed that ancilla-assisted and ancilla-free groups diverge for n ≥2.Kliuchnikov, Maslov, and Mosca conjectured the corresponding characterization for all n and that one ancilla always suffices.
  • Contributions: The paper proves the conjectures, yielding an algorithm for exact Clifford+T synthesis and a characterization of n-qubit Clifford+T operators without ancillas.The result applies to multiqubit operators and distinguishes ancilla-assisted from ancilla-free representations.
  • Limitation: The synthesized circuits are neither canonical nor close to optimal, so the paper does not address efficient synthesis.This limitation concerns the circuits produced by the exact-synthesis algorithm.

2 Statement of the main result

The main theorem characterizes exactly which unitary matrices admit Clifford+T representations with initialized and finalized ancillas. It also establishes that one ancilla always suffices for such representations.

  • Algebraic setting: The paper considers the ring Z[1/sqrt(2),i] as the algebraic domain underlying its exact-synthesis characterization.The theorem is stated for unitary 2^n × 2^n matrices whose entries are tested against this ring.
  • Theorem 1: For a unitary 2^n × 2^n matrix U, exact Clifford+T representability with finitely many initialized and finalized |0⟩ ancillas is equivalent to its entries belonging to Z[1/sqrt(2),i].The theorem gives both directions of this equivalence.
  • Theorem 1: One ancilla is always sufficient in the theorem’s exact representation.Additional ancillas are not required for existence, although they may matter for circuit construction in practice.

3 Some algebra

This section develops the algebra of dyadic cyclotomic rings, residues, norms, weights, and denominator exponents used in the synthesis proof. Reducibility of residues provides the criterion for lowering denominator exponents.

  • Rings and residues: The paper works with D[ω], Z[ω], and Z2[ω], where D contains fractions with powers of 2 in the denominator.D[ω] and Z[ω] are complex-number subrings, while Z2[ω] is a 16-element residue ring.
  • Norm and weight: The norm and weight extend componentwise from ring elements to vectors and matrices, with weight capturing the dyadic part of squared norm.The squared norm lies in D[√2], while the squared weight lies in D.
  • Denominator exponents: A denominator exponent k is the least nonnegative integer such that 2^k t belongs to Z[ω], extended entrywise to vectors and matrices.The paper allows denominator exponents for any common bound, then selects the least one.
  • Residues: The residue map ρ sends Z[ω] onto Z2[ω], where residues encode coefficients as binary digits and preserve several operations used by the proof.Complex conjugation, multiplication by ω, multiplication by √2, and squared norm are treated through residues.
  • Reducibility: The lemmas characterize reducibility through divisibility by 2 and residue conditions, including the equivalence between halving elements and reducible residues.These facts support denominator reduction in later vector and matrix decompositions.
  • Reducibility: For t in D[ω], a positive denominator exponent k is least exactly when its k-residue is irreducible.This connects an arithmetic minimality condition with a finite residue property.

4 Decomposition into two-level matrices

This section proves that unit vectors over D[ω] can be reduced to a standard basis vector using elementary one- and two-level operations. Applying the result column by column yields a decomposition of any unitary matrix over D[ω].

  • Two-level operations: A two-level matrix acts nontrivially on at most two vector components, allowing local row operations to modify selected pairs.The construction represents these operations as one- or two-level matrices of specified gate types.
  • Denominator reduction: When two residue components have equal squared norm, sequences of H and T operations can lower the vector’s denominator exponent by one.The proof handles residue cases using cyclic permutations and reducibility of transformed residues.
  • Column lemma: The column lemma states that every unit vector in D[ω]^n can be mapped to the first standard basis vector using X, H, T, and ω operations.Its proof uses induction on the least denominator exponent, with an inner induction on irreducible residue components.
  • Column lemma: Residue norm constraints guarantee suitable pairings during the induction, while H and T operations reduce the number of irreducible components.The argument uses parity properties of residue squared norms to find a second component for each irreducible one.
  • Matrix decomposition: The matrix decomposition lemma follows by applying the column lemma recursively to transform a unitary matrix into the identity.The resulting factorization uses one- and two-level matrices of types X, H, T, and ω.

5 Proof of Theorem 1

The proof establishes exact Clifford+T representability by decomposing matrices over D[ω] into elementary controlled operations. It then shows that these operations can be implemented with at most one ancilla.

  • Equivalence: Because Clifford+T gates have entries in D[ω], exact circuit representability implies that the operator’s entries lie in the required ring.The converse begins with a unitary matrix over D[ω].
  • Equivalence: The matrix decomposition lemma reduces any unitary matrix over D[ω] to one- and two-level matrices of types X, H, T, and ω.Gray-code constructions convert these elementary matrices into controlled gates.
  • Equivalence: Controlled-not and multiply-controlled X, H, T, and ω gates have exact Clifford+T implementations with ancillas, completing the representability direction.A controlled-ω gate is identified with a T-gate in this construction.
  • One-ancilla construction: To prove the ancilla bound, it suffices to implement multiply-controlled X, H, and T gates using one ancilla.The paper recalls ancilla-free singly controlled H and controlled constructions for multiply-controlled iX gates.
  • One-ancilla construction: The one-ancilla constructions combine known controlled-gate decompositions to realize the required multiply-controlled operations.The paper notes that one ancilla is theoretically sufficient, while additional ancillas can reduce circuit size and depth in practice.

6 The no-ancilla case

The no-ancilla case is characterized by matrix-entry and determinant conditions, and the paper proves the resulting characterization through determinant adjustment and ancilla-free decompositions.

  • 6 The no-ancilla case: Lemma 7 shows that a unitary satisfying the theorem's hypotheses and det U = 1 has an exact ancilla-free Clifford+T representation.The proof uses decompositions into one- and two-level matrices and ancilla-free representations of the resulting controlled operators.
  • 6 The no-ancilla case: The paper obtains an ancilla-free characterization of the n-qubit Clifford+T group through an equivalence between exact representability and algebraic conditions on U.The characterization is stated as a corollary for unitary 2^n × 2^n matrices.
  • 6 The no-ancilla case: For n ≤ 1, the determinant must lie in {ω, i, ω^3, −1, ω^5, −i, ω^7, 1}.These are the allowed powers of ω in the low-qubit cases.
  • 6 The no-ancilla case: The proof adjusts determinants using Clifford+T elements D_n, reducing the target to determinant one before applying Lemma 7.The determinant-correction construction uses D_n with determinant d_n, including d_n = 1 for n ≥ 4.
  • 6 The no-ancilla case: For n ≤ 1, the stated determinant-power condition is redundant because det U belongs to the ring and has unit magnitude.It is retained for consistency with the n ≥ 2 formulation.
  • 6 The no-ancilla case: For n ≥ 4, the determinant condition is det U = 1, paralleling the even-permutation restriction for classical reversible circuits.A single ancilla similarly suffices to recover all classical reversible functions in the stated analogy.

7 Complexity

The synthesis algorithm is obtained from the paper's matrix decomposition, whose denominator-exponent growth yields an exponential operation bound and a corresponding Clifford+T gate-count bound.

  • 7 Complexity: The proof of Theorem 1 yields an algorithm for synthesizing a Clifford+T circuit with ancillas, although the paper describes it as not very efficient.The section estimates the size of the generated circuits.
  • 7 Complexity: O(nk) operations reduce a single n-dimensional column from denominator exponent k to k−1, and completely reducing that column also requires O(nk) operations.This estimate follows from constant-cost row operations and the induction step.
  • 7 Complexity: O(3^nk) one- and two-level operations are required by the full matrix decomposition of Lemma 6.The bound results from denominator-exponent growth by factors of up to 3 across successive column reductions.
  • 7 Complexity: O(3^(2^n)k) two-level operations decompose an n-qubit operator, because it is a 2^n × 2^n matrix.This applies the matrix-operation bound with matrix dimension 2^n.
  • 7 Complexity: O(3^(2^n)nk) elementary Clifford+T gates result when one ancilla decomposes each two-level operation into O(n) gates.The gate-count bound includes the one-ancilla implementation overhead.

8 Future work

The paper identifies substantial opportunities to improve its synthesis algorithm, whose circuits are far from optimal and whose worst-case gate count has an exponential gap from information-theoretic lower bounds. The main target is the superexponential 32^n factor caused by coupled changes in columns during row reduction.

  • The synthesis algorithm produces circuits that are very far from optimal, and efficient synthesis is not addressed.The authors illustrate this heuristically by resynthesizing operators generated from simple Clifford+T circuits.
  • The algorithm’s worst-case gate count O(32^n n k) is separated from information-theoretic lower bounds by an exponential gap.Operators with denominator exponent k carry between Ω(2^n k) and O(4^n k) bits of information, implying an exponential rather than superexponential lower bound in n.
  • The information-theoretic analysis does not establish a better asymptotic synthesis algorithm, but suggests that developing one is worthwhile.
  • The most obvious improvement target is the 32^n-driven superexponential blowup in the gate-count estimate.The blowup arises because row reductions that lower one column’s denominator exponent can simultaneously raise the exponents of the remaining columns.
Loading 1212.0506v3…