Abstract
Code-word-stabilized (CWS) codes are, in general, nonadditive quantum codes that can correct errors by an exhaustive search of different error patterns, similar to the way that we decode classical nonlinear codes. For an $n$-qubit quantum code correcting errors on up to $t$ qubits, this brute-force approach consecutively tests different errors of weight $t$ or less and employs a separate $n$-qubit measurement in each test. In this article, we suggest an error grouping technique that allows one to simultaneously test large groups of errors in a single measurement. This structured error recovery technique exponentially reduces the number of measurements by about $3^t$ times. While it still leaves exponentially many measurements for a generic CWS code, the technique is equivalent to syndrome-based recovery for the special case of additive CWS codes.
Introduction
Quantum error correction is essential for building reliable quantum computers. While stabilizer codes—the quantum analogue of classical linear codes—benefit from efficient syndrome-based decoding, the broader class of Codeword-Stabilized (CWS) codes presents a significant challenge. CWS codes can outperform stabilizer codes in terms of parameters (e.g., higher code rates for a given distance), but they are often non-additive. This lack of additive structure typically forces a "brute-force" decoding approach: an exhaustive search through all possible error patterns, requiring a massive number of measurements that can disturb the quantum state.
The Challenge of CWS Decoding
In a standard stabilizer code, a single set of syndrome measurements identifies the error. For a CWS code correcting $t$ errors on $n$ qubits, the number of possible Pauli error patterns is $B(n, t) = \sum_{i=0}^t \binom{n}{i} 3^i$. Without a syndrome structure, traditional recovery involves testing each pattern one by one. Li et al. address this bottleneck by introducing a Structured Error Recovery framework that groups these patterns, allowing for simultaneous testing.
Structured Error Recovery and Group Testing
The core innovation lies in treating CWS codes as Union Stabilizer (USt) codes—unions of shifted stabilizer spaces. By leveraging this perspective, the authors construct auxiliary measurement operators, $M_Q$, designed to detect if any error within a specific group $Q$ has occurred.
Instead of checking individual Pauli operators ($X, Y, Z$), the method groups errors based on their qubit index sets. This "group testing" approach reduces the total number of measurements $N(n, t)$ from approximately $\binom{n}{t} 3^t$ to roughly $\binom{n}{t} + 2t$. For $t > 1$, this represents an exponential reduction in overhead by a factor of at least $3^t$.
Circuit Implementation and Scaling
The recovery process is implemented via quantum circuits using ancilla qubits. These circuits perform logical "AND" and "XOR" operations on measurement outcomes to pinpoint errors. The complexity of these non-Pauli measurements is shown to be $O(n^2)$, making them theoretically viable, though challenging for current hardware.
To handle multiple error groups, the protocol applies a sequence of measurement operators $C^{M_k}$. This sequential testing allows the decoder to narrow down the error location and type efficiently.
Conclusion and Future Outlook
This structured recovery technique bridges the gap between the high performance of non-additive CWS codes and the decoding efficiency of stabilizer codes. While the number of measurements still scales exponentially with $t$ for generic codes, the $3^t$ reduction is a significant leap forward. Future research may identify specific CWS code families that allow for even larger error groups, potentially leading to polynomial-time decoding for a wider range of non-additive quantum codes.
Summary updated