Climbing the Clifford Hierarchy

1. Problem Statement and Motivation

The Clifford Hierarchy is a fundamental structure in quantum computing, defined as a nested sequence of gate sets $C^{(1)} \subset C^{(2)} \subset \dots$, where $C^{(1)}$ is the Pauli group and $C^{(2)}$ is the Clifford group. The $k$-th level $C^{(k)}$ consists of gates that conjugate Pauli gates into the $(k-1)$-th level. This hierarchy is crucial for fault-tolerant quantum computation, particularly for magic state distillation and gate teleportation.

While the diagonal gates within the hierarchy are well-understood (they form groups and can be "climbed" by adding controls or taking square roots), the general structure of the hierarchy remains largely unknown. Specifically, it is not fully understood which non-diagonal gates allow their square roots to "climb" to the next level of the hierarchy.

Core Problem: Given a Hermitian gate $U \in C^{(k)}$, under what conditions does its square root $\hat{U} = \exp(i\pi U/4)$ belong to the next level, $C^{(k+1)}$?

2. Methodology

The authors employ a combination of algebraic analysis, symplectic geometry, and group theory to characterize these conditions.

• Definition of the Square Root: For a Hermitian gate $U$, the square root is defined as $\hat{U} = \frac{I + iU}{\sqrt{2}}$. The condition $\hat{U} \in C^{(k+1)}$ requires that for any Pauli gate $P$, the conjugation $\hat{U}P\hat{U}^\dagger$ must result in a gate within $C^{(k)}$.
• Symplectic Representation: For Clifford gates ($k=2$), the authors utilize the symplectic representation. Every Clifford gate $C$ corresponds to a symplectic matrix $F_C \in Sp(2n, \mathbb{F}_2)$. The action of $C$ on Pauli gates is linear in the symplectic vector space.
• Hyperbolicity and Involutions: The analysis focuses on Hermitian Clifford gates, which correspond to symplectic involutions ($F_C^2 = I$). The authors introduce the concept of hyperbolic symplectic matrices, where the symplectic inner product of any vector with its image under the matrix is zero.
• Residue Space Analysis: The authors analyze the residue space $Res(F) = \text{row space}(I + F)$. The dimension of this space ($r$) becomes a critical parameter in determining whether the square root climbs the hierarchy.
• Pauli Expansion: For general Clifford gates, the authors use a Pauli expansion (linear combination of Pauli gates) to analyze the trace properties of the conjugated operators, leveraging the fact that Clifford gates have specific trace magnitudes for their Pauli coefficients.

3. Key Contributions and Results

A. Necessary Conditions for Climbing (Theorem 3.3)

The paper establishes a necessary condition for a Hermitian gate $U \in C^{(k)}$ to have $\hat{U} \in C^{(k+1)}$.

• Result: If there exist two anti-commuting Hermitian Pauli gates $E, E'$ such that $UEU^\dagger = E'$, then $\hat{U} \notin C^{(k+1)}$.
• Implication: This explains why the Hadamard gate ($H = (X+Z)/\sqrt{2}$) fails to climb; it maps $X$ to $Z$ (which anti-commute), preventing its square root from entering $C^{(3)}$.

B. Characterization of Clifford Gates Climbing to Level 3 (Sections 4)

The authors provide a complete characterization of Hermitian Clifford gates ($C \in C^{(2)}$) whose square roots climb to $C^{(3)}$.

• Symplectic Condition: A Hermitian Clifford gate $C$ has $\hat{C} \in C^{(3)}$ if and only if its associated symplectic matrix $F_C$ is a hyperbolic involution and the dimension of its residue space is exactly 2 ($\dim(Res(F_C)) = 2$).
• Diagonal Gates: For diagonal Clifford gates, this condition is equivalent to the associated binary symmetric matrix $A$ having a zero diagonal and rank 2.
• Permutation Gates: For permutation Clifford gates, the condition requires the permutation matrix $B$ to be an involution ($B=B^{-1}$) such that $\text{rank}(I+B)=1$.
• Counter-examples: The paper demonstrates that if $\dim(Res(F_C)) > 2$, the square root generally fails to climb to $C^{(3)}$ (e.g., certain products of CNOTs or Toffoli gates).
• Counting: The authors derive formulas for the number of such diagonal and permutation Clifford gates for $n$ qubits.

C. Lifting to Level 4 (Section 5)

The paper investigates when controlled versions of these gates climb further.

• Theorem 5.3: If $C \in C^{(2)}$ is a Hermitian Clifford gate such that $\hat{C} \in C^{(3)}$, then the controlled version $U = C(C)$ satisfies $\hat{U} \in C^{(4)}$.
• Significance: This mimics the behavior of diagonal gates, showing that the "climbing" property is preserved under control operations for this specific class of Clifford gates.
• Examples: The authors apply this to products of Toffoli gates and controlled-SWAP gates, showing that specific configurations (sharing controls) allow climbing to the fourth level, while others do not.

D. Generalization to Higher Roots (Section 6)

The authors propose a generalization to $2^m$-th roots ($sq_m(U)$) and pose open problems regarding the conditions under which $sq_m(U)$ climbs $m$ levels. Preliminary data suggests similar structural constraints apply.

4. Significance and Impact

• Structural Understanding: This work moves beyond the well-studied diagonal gates to provide the first complete characterization of non-diagonal (specifically Clifford) gates that can be "climbed" via square roots.
• Fault Tolerance: By identifying which gates allow their square roots to remain within the hierarchy, the paper aids in the design of fault-tolerant quantum circuits. Gates that climb the hierarchy are essential for implementing non-Clifford operations (like the T gate) via gate teleportation and magic state distillation.
• Algorithmic Implications: The use of symplectic geometry and residue spaces provides a computational framework to test whether a given Clifford gate is "climbable," which is vital for optimizing quantum compilation and error correction schemes.
• Future Directions: The paper sets the stage for a complete understanding of the fourth level of the hierarchy and suggests that the "climbing" phenomenon is governed by the dimension of the residue space of the underlying symplectic matrix.

In summary, the paper successfully bridges the gap between the known properties of diagonal gates and the broader Clifford hierarchy, offering precise algebraic criteria for determining the "climbability" of quantum gates, a property critical for scalable, fault-tolerant quantum computing.