Quantum group codes for non-Clifford logic: enhanced decoding, addressability and parallelizability

Technical Summary: Quantum Group Codes for Non-Clifford Logic

Problem Statement
Current fault-tolerant quantum computation schemes suffer from significant space and time overheads, hindering the realization of practical quantum computers. While Calderbank-Shor-Steane (CSS) codes supporting transversal gates offer a path to fault tolerance, existing constructions face two primary limitations:

1. Decoding Complexity: State-of-the-art quantum Algebraic Geometry (AG) codes supporting non-Clifford transversal gates (essential for Magic State Distillation, or MSD) rely on decoding algorithms with cubic time complexity ($O(n^3)$). This high complexity propagates to the MSD protocol, limiting its efficiency.
2. Addressability and Parallelizability: Existing codes with transversal non-Clifford gates typically implement global operations acting on all physical qudits simultaneously. This lack of "addressability"—the ability to target specific subsets of logical qudits—limits algorithmic flexibility. Furthermore, while recent work has shown the existence of codes with addressable gates, the constructions often rely on very specific families of transitive AG codes, and the parallelizability of these gates requires further optimization to reduce circuit depth.

Methodology
The authors propose a framework based on quantum group codes, derived from classical quasi group codes with specific multiplication properties. The methodology proceeds in three main stages:

1. Framework Definition (Quantum Group Codes):
   The authors define a class of quantum CSS codes where the underlying classical codes ($C_0$ and $C_1$) are quasi-$G$ codes (isomorphic to right ideals of a group algebra $F_q[G]$). By ensuring the existence of a $G$-module homomorphism section for the quotient map, they establish conditions under which these quantum codes admit parallelizable and addressable transversal multi-control-Z ($C_{m-1}Z$) gates.

   • Key Mechanism: The group action allows for the construction of modulation functions that enable the implementation of logical gates on specific orbits of logical qudits using depth-one physical circuits.

2. Code Construction via Lifting:
   To generate codes with good parameters and efficient decoding, the authors employ a lifting procedure based on class field theory (specifically from [CG26]).

   • They start with a good classical AG code $C$ over $F_q$ that satisfies the $m$-multiplication property.
   • They construct an unramified abelian extension of the underlying function field, creating a new code $\tilde{C}$ over $F_{q^2}$.
   • This lifting process endows the new code with a large abelian permutation automorphism group $G$, making it a free $F_{q^2}[G]$-module. Crucially, the lifting preserves the $m$-multiplication property required for transversal gates.

3. Decoding Optimization:
   The authors leverage the module structure of the lifted codes. Unlike standard AG codes which require cubic-time decoding, the free-module structure allows the adaptation of decoding algorithms to utilize fast matrix multiplication over the group algebra. This results in a quasi-quadratic time decoder ($O(n^2 \cdot \text{polylog}(n))$) with a linear decoding radius.

Key Contributions and Results

• Theorem 1.1 (Code Families): The paper constructs two families of $q$-dimensional qudit quantum group codes (where $q=t^4$):

  1. Fully Addressable Family: Codes with parameters $[[n, \Theta(n/\log n), \Theta(n)]]_q$. These admit fully addressable transversal $C_{\tilde{m}-1}Z$ gates. The depth of logical circuits involving $m$ code blocks is upper-bounded by $O(k^{\tilde{m}-1})$.
  2. High-Rate Family: Codes with parameters $[[n, \Theta(n), \Theta(n)]]_q$. These admit a global transversal $C_{\tilde{m}}Z$ gate and orbit-wise addressable $C_{\tilde{m}-1}Z$ gates across $\Theta(\log n)$ orbits.
  • In both cases, the codes support a $O(n^2 \cdot \text{polylog}(n))$-time decoder with a linear decoding radius, a significant improvement over the $O(n^3)$ complexity of previous AG-based constructions.

• Corollary 1.2 (Magic State Distillation): By applying the high-rate family to Magic State Distillation (MSD) protocols, the authors demonstrate the existence of a constant-overhead distillation protocol for qubit CCZ-magic states with $O(n^2 \cdot \text{polylog}(n))$ time complexity. This represents an almost linear reduction in time complexity compared to the state-of-the-art $O(n^3)$ protocols.

• Parallelizability: The work establishes that logical multi-control-Z circuits can be parallelized to a high degree. For dense circuits, the minimal depth is bounded by $O(k^{m-1})$, which is optimal for such circuits.

Significance
The paper claims that its work addresses critical bottlenecks in fault-tolerant quantum computing:

1. Efficiency: By reducing the decoding complexity from cubic to quasi-quadratic, the time overhead for MSD protocols is substantially decreased, bringing practical fault-tolerant computation closer to feasibility.
2. Flexibility: The introduction of addressable and parallelizable non-Clifford gates moves beyond global operations, allowing for more precise control over logical qudits. This is essential for circuit compilation and algorithms that do not require global entanglement.
3. Generalization: The construction moves beyond the specific transitive AG codes used in prior work, utilizing a broader class of lifted AG codes with large abelian automorphism groups. This provides a more versatile toolkit for designing quantum codes with transversal non-Clifford gates.

The authors emphasize that their results are derived from theoretical constructions and existing lifting techniques, verifying that these transformations preserve the necessary properties for transversal non-Clifford gates while improving decoding efficiency.