Abstract
Codeword-stabilized (CWS) codes are a general class of quantum codes that includes stabilizer codes and many families of nonadditive codes with good parameters. For such a nonadditive code correcting all $t$-qubit errors, we propose an algorithm that employs a single measurement to test all errors located on a given set of $t$ qubits. Compared with exhaustive error screening, this reduces the total number of measurements required for error recovery by a factor of approximately $3^t$.
Introduction
Quantum Error Correction (QEC) is vital for the development of reliable quantum computers. While stabilizer codes are widely studied due to their structured decoding, the broader class of Codeword-Stabilized (CWS) codes includes non-additive codes that can achieve superior parameters, such as higher information rates for a given number of physical qubits. However, the lack of a simple syndrome structure in non-additive CWS codes has historically necessitated exhaustive error screening—testing every possible Pauli error ($X, Y, Z$) on every possible combination of qubits. This "brute-force" approach is computationally expensive, requiring $O(\binom{n}{t} 3^t)$ measurements for a $t$-error-correcting code.
Clustered Measurement Algorithm
This paper introduces a "clustered" measurement technique that significantly improves decoding efficiency by focusing on error locations rather than specific error types. The method leverages the mapping of CWS quantum error patterns onto classical binary strings, treating the code as a union of translated stabilizer codes.
The key innovation is the construction of Auxiliary Union Stabilizer (USt) codes. These auxiliary codes are designed to detect any error occurring within a specific cluster of $t$ qubits using a single measurement. This approach effectively "nets" all $4^t$ possible error combinations on those qubits simultaneously.
The recovery process is divided into two stages:
- Error Localization: Clustered measurements are performed to identify the specific $t$-qubit subset where errors have occurred.
- Error Identification: Once the location is known, a minimal set of additional measurements identifies the exact Pauli error type within that cluster.
Complexity and Performance
The proposed algorithm achieves an exponential reduction in the number of required measurements. For a code of length $n$ correcting $t$ errors, the total measurements are reduced from $B(n, t) \approx \binom{n}{t} 3^t$ to $N(n, t) \approx \binom{n}{t} + 2t$. For codes correcting 2 or 3 errors, this reduction is substantial, drastically lowering the quantum overhead.
The authors also analyze the gate complexity, proving that the clustered measurement circuits are efficient. Specifically, Theorem 2 shows that the circuit requires at most $2K(n-1)(n+3)$ two-qubit gates, where $K$ is the number of codewords. This ensures that the depth of the recovery circuit remains manageable for practical implementation.
Conclusion
The clustered measurement framework provides a general and efficient decoding strategy for all CWS codes. By generalizing the syndrome-based recovery of stabilizer codes to the non-additive regime, this work removes a major barrier to the adoption of high-performance CWS codes in fault-tolerant quantum computing. Future work will explore the performance of this method in fully fault-tolerant settings where the recovery gates themselves are subject to noise.
Summary updated