Finding diagonal logical gates in CSS codes and circuits

Technical Summary: Finding Diagonal Logical Gates in CSS Codes and Circuits

Problem Statement
The realization of large-scale, fault-tolerant universal quantum computers requires the efficient implementation of non-Clifford logical gates. While Clifford operations are relatively straightforward in the stabilizer formalism, non-Clifford gates pose significant challenges. Current approaches often rely on magic state distillation, transversal non-Clifford gates (sometimes combined with code switching), or "spacetime" logical gates inserted into syndrome-extraction circuits. A central challenge is identifying which CSS (Calderbank-Shor-Steane) codes or circuits admit efficient, locality-preserving diagonal non-Clifford logical gates (such as $T$, $CS$, or $CCZ$) composed from a prescribed set of physical ansatz gates. Existing methods, such as the triorthogonality condition, are often limited to specific gate types or lack generality for arbitrary locality-preserving circuits.

Methodology
The paper proposes an efficient algorithm to find all logical gates of a given CSS code (or circuit) that are composed from a prescribed set of diagonal ansatz gates. The core theoretical insight is that a diagonal logical gate preserves the code space if and only if it assigns the same phase to every $Z$-basis configuration within a given cohomology class.

1. Mathematical Formulation:

   • The action of a diagonal gate $V_c$ on a computational basis state $|a\rangle$ is defined by a phase function $S_c(a)$. For gates in the third level of the Clifford hierarchy, $S_c(a)$ is a "third-order" function involving terms like $a_i a_j a_k$ (for $CCZ$),$a_i a_j$ (for $CS$), and $a_i$ (for $T$).
   • The condition for code-space preservation is that $S_c(a)$ must be constant for all $a$ in the same cohomology class. This reduces to the requirement that $S_c(a + A e_j) = S_c(a)$ for all $X$-stabilizer generators $A e_j$, where $A$ is the $X$-check matrix.
   • This condition is equivalent to requiring that the "pullback" of the phase function by the $X$-check matrix, denoted $S_c \circ A$, yields a trivial phase function.

2. The Pullback Homomorphism ($A^*$):

   • The authors define a group homomorphism $A^*$ that maps the coefficients of the physical ansatz gates ($c \in G_{phys}$) to the coefficients of the induced phase function on the $X$-checks.
   • $G_{phys}$ is a product of finite abelian 2-groups (e.g., $\mathbb{Z}_2, \mathbb{Z}_4, \mathbb{Z}_8$) corresponding to the different levels of the Clifford hierarchy.
   • The set of valid logical gates corresponds exactly to the kernel of this homomorphism: $A^* c = 0$.

3. Algorithmic Implementation (Filtration):

   • To compute the kernel of $A^*$ efficiently, the authors introduce a "filtration" method. Instead of using Smith normal form (which involves large integer arithmetic), the method decomposes the problem into a sequence of kernel computations over binary fields ($\mathbb{Z}_2$).
   • The algorithm iteratively computes kernels of $X \pmod 2$, $X \pmod 4$, and so on, lifting solutions from lower-order groups to higher-order groups. This leverages the fact that $\ker(X) \subset \ker(X \pmod 4) \subset \ker(X \pmod 2)$.
   • The subroutines rely on standard binary linear algebra (Gaussian elimination/RREF) which can be accelerated using bit-packing.

4. Generalizations:

   • Spacetime Gates: The method extends to "spacetime local logical gates," where diagonal gates are inserted into syndrome-extraction circuits. This is modeled by treating the circuit as a tensor network (or path integral) and applying the same pullback logic to the $Z$-decoding graph.
   • Higher Levels & Arbitrary Gates: The framework generalizes to higher levels of the Clifford hierarchy and arbitrary diagonal gates (non-hierarchy) by adjusting the definition of the phase functions and the coefficient groups.
   • Qudits: The method is generalized to prime and composite-dimensional qudits by defining appropriate higher-order functions over $\mathbb{Z}_{d_i}$.

Key Contributions

• Unified Framework: The paper provides a general formalism that unifies the search for transversal gates, locality-preserving logical circuits, and spacetime logical gates under a single algebraic condition: finding the kernel of a specific group homomorphism $A^*$.
• Efficient Algorithm: It presents a fast algorithm with a naive runtime of $O(n^3)$ for a system with $O(n)$ qubits (or gates), utilizing a filtration technique that reduces the problem to binary matrix operations.
• Flexibility: The approach allows users to prescribe arbitrary sets of ansatz gates (including non-local or folded gates) and find all resulting logical gates without imposing translation invariance.
• Implementation: A Python implementation is provided, including a specialized package (twogroup-linalg) for linear algebra over abelian 2-groups.

Results and Examples

• The algorithm successfully recovers known logical gates for 2D and 3D toric codes, color codes, fracton codes, and bivariate bicycle codes.
• It discovers a previously unknown third-order diagonal gate in the "dual 3D color code," which implements a logical $T$-gate equivalent.
• The method is demonstrated to find translation-invariant logical gates in $O(1)$ time relative to system size (scaling only with unit cell parameters).
• The runtime for a 2D color code with 800 qubits is approximately 30 seconds on a standard laptop for the non-translation-invariant case.

Significance and Claims
The paper claims that its method offers a systematic and efficient way to explore the space of fault-tolerant logical gates for CSS codes and circuits. By reframing the problem as a kernel computation, it generalizes the triorthogonality condition to arbitrary products of Clifford-hierarchy gates and locality-preserving circuits.

The authors note that while the method can find arbitrary diagonal gates, physical realizability in fault-tolerant settings likely restricts these gates to the Clifford hierarchy (consistent with Bravyi-Koenig-type arguments). The work suggests that this approach could be used to discover new qLDPC codes with desirable logical gate properties or to optimize the extension of logical gates to code boundaries and domain walls. The paper maintains a modest tone regarding future speedups, acknowledging that while sparsity in qLDPC codes offers potential for further optimization (e.g., via Wiedemann's algorithm or local kernel decomposition), the current $O(n^3)$ dense implementation is already competitive with finding the logical basis of the code itself.