Bounded decoding complexity in transversal circuits with magic state injection

Technical Summary: Bounded Decoding Complexity in Transversal Circuits with Magic State Injection

Problem Statement
Fault-tolerant quantum computing architectures that implement Clifford gates transversally and achieve universality via magic state injection face a critical scalability challenge: the complexity of space-time correlated decoding. While reducing the number of syndrome-extraction rounds (e.g., to one round per gate) lowers time overhead, it necessitates correlating syndrome information across multiple circuit layers. In such schemes, decoding a logical measurement requires backpropagating the measurement operator through the circuit to identify the space-time region where errors could affect the outcome. As circuit depth increases, these backpropagation regions typically grow, leading to decoding graphs that scale with circuit volume. This raises the concern that classical decoding could become a bottleneck for large-scale computations, particularly given that decoding is generally considered a problem that scales poorly with size.

Methodology
The authors analyze the decoding complexity in a setting motivated by recent experimental platforms (trapped ions, neutral atoms) that support reconfigurable, effectively nonlocal connectivity. The study focuses on random circuits composed of:

1. Transversal Clifford layers: Arranged in a 1D brickwork geometry (or all-to-all connectivity in supplementary analysis) using gates like CNOT, H, and S.
2. Magic state injection: Non-Clifford T-gates are implemented via gate teleportation using resource states $|T\rangle_L$, involving mid-circuit measurements and conditional feedforward.

The core methodology involves:

• Reliable Measurement Products: Instead of decoding every measurement individually, the authors utilize a strategy where measurements are classified as "reliable" or "unreliable" based on their commutation with initial state stabilizers. Unreliable measurements are either assigned random outcomes or combined with previous measurements to form "reliable products" (products of measurements whose backpropagated operators commute with all initial stabilizers).
• Sequential Decoding: Decoding is performed sequentially. Once a reliable product is decoded and corrections are committed, the associated syndrome data is excluded from future decoding problems. This prevents the reprocessing of already resolved syndrome information.
• Backpropagation Analysis: The decoding graph for a reliable product is constructed by backpropagating the product through the circuit. The size of this graph (measured by the number of stabilizer checks) serves as a proxy for decoding complexity.
• Numerical Simulation: The authors simulate random circuits with varying numbers of logical qubits ($N$) and magic state injection probabilities ($\kappa$). They track the "normalized check count" ($N_C$), which excludes checks already processed in prior steps, to determine the effective decoding volume.

Key Contributions and Results

1. Bounded Decoding Volume: The primary finding is that the decoding complexity for mid-circuit measurements approaches a stationary average that is independent of both the number of computational qubits ($N$) and the circuit depth ($t$).

   • In the transient regime (early circuit times), the check count grows as unreliable measurements accumulate.
   • In the stationary regime, the average normalized check count $N_{C,\infty}$ is determined by the ratio of newly generated checks to the number of reliable products created per layer.
   • The authors derive an analytical prediction for this stationary value:
     $$N_{C,\infty} = \frac{3(2 + \kappa)}{\kappa}$$
     where $\kappa$ is the probability of a T-gate injection per layer. This indicates that the decoding volume is inversely proportional to the density of magic state injections.

2. Exponential Suppression of Large Instances: The distribution of decoding volumes in the stationary regime exhibits an exponential tail, $p(N_C) \sim e^{-b N_C}$. The decay rate $b$ increases with $\kappa$ (approximately as $\kappa^\alpha$ with $\alpha \approx 0.98$), meaning that higher densities of magic states not only reduce the average decoding load but also exponentially suppress the probability of encountering large, computationally expensive decoding instances.

3. Insensitivity to Product Choice: The construction of reliable products is generally not unique; there are exponentially many solutions for combining measurements. The authors tested four different selection strategies (Gaussian elimination, random selection, belief propagation with ordered-statistics decoding, and exact minimum-Hamming-weight via MaxSAT). They found that despite significant differences in the Hamming weights (number of constituent measurements) of the chosen products, the resulting decoding complexity statistics are indistinguishable. This suggests that computationally expensive optimization of the product choice is unnecessary; simple Gaussian elimination suffices.

4. Robustness Across Architectures: The qualitative behavior (boundedness and stationary distribution) persists across different circuit connectivities (1D brickwork vs. all-to-all) and Clifford gate ensembles.

Significance and Claims
The paper argues that the very mechanism used to achieve universality in transversal architectures—magic state injection—also provides the mechanism to keep decoding scalable.

• Scalability: The results suggest that scalable space-time correlated decoding is achievable for large-scale fault-tolerant quantum algorithms. The magic states, by introducing frequent mid-circuit measurements, continually "reset" the decoding problem, restricting the amount of new syndrome information that must be processed at any given step.
• Classical Overhead: The classical processing cost does not grow with the size of the quantum computation (width or depth) but remains bounded, depending only on the local density of magic states and the underlying code distance.
• Comparison to Windowed Decoding: Unlike "windowed decoding," which requires defining arbitrary space-time boundaries to limit the decoding region, this approach dynamically determines boundaries through the sequential commitment of corrections. This method preserves fault tolerance by construction without requiring additional prescriptions to handle boundary conditions.

The authors conclude that for transversal fault-tolerant architectures, the classical decoding problem can scale alongside the quantum hardware, provided the magic state density remains finite. This addresses a major potential bottleneck in the realization of practical, large-scale quantum error correction.