Codeword stabilized (CWS) code

Codeword stabilized (CWS) code[1,2]

Description

A code defined using a cluster state and a set of \(Z\)-type Pauli strings defined by a binary classical code.

The CWS construction takes in \( \mathcal{Q} = (\mathcal{G},\mathcal{C}) \), where \(\mathcal{G}\) is a graph, and where \(\mathcal{C}\) is an \((n,K,d)\) binary code. From the graph, we form the unique cluster state \( |\mathcal{G} \rangle \). From the binary code, we form Pauli \(Z\)-type operators \( W_i = Z^{c_{i,1}} \otimes \cdots \otimes Z^{c_{i,n}} \), where \(c_{i,j} \) is the \(j\)-th coordinate of the \(i\)-th classical codeword. The CWS codewords are then \( | i \rangle = W_i | \mathcal{G} \rangle \).

The above definition corresponds to the standard form of CWS codes. Since any stabilizer state is equivalent to a cluster state under a single-qubit Clifford circuit [3][4; Appx. A], any code whose underlying state is a non-cluster stabilizer state is similarly equivalent to a CWS code.

The term CWS was coined in Ref. [2], and their approach is equivalent to another approach [1] based on Boolean functions (see Ref. [5]). In an alternative convention (not used here), CWS codes are defined from an underlying stabilizer state that is not a necessarily a cluster state.

Protection

Code distance \(\mathcal{Q} = ( \mathcal{G},\mathcal{C}) \) is upper bounded by the distance of the classical code \(\mathcal{C} \). The diagonal distance is upper bounded by \(\delta + 1\), where \(\delta\) is the minimum degree of \(\mathcal{G}\).

Computing the distance is generally \(NP\)-complete, and is \(NP\)-hard for non-degenerate codes [6]. Some bounds are provided in Ref. [7].

Encoding

If \( \mathcal{C} \) has an efficient classical encoder, then so does the CWS code \( \mathcal{Q} = (\mathcal{G},\mathcal{C}) \).Sequantial encoder related to MBQC [8].

Decoding

There is no known efficient algorithm to decode non-additive (non-stabilizer) CWS codes.Clustered bounded-distance decoder [9–11].Structured error recovery [12], which reduces to syndrome-based recovery for additive (i.e., stabilizer) CWS codes.

Notes

See Ref. [13] for an overview of CWS codes.

Parents

Union stabilizer (USt) code — Any CWS code can be written as a USt whose (\(K=1\)) stabilizer code is the cluster state and whose coset representatives are constructed from the binary classical code. Conversely, USt codes are equivalent to CWS codes via a single-qubit Clifford circuit as follows [9,11][13; Sec. 10.4]. The set of coset representatives of any USt can be extended to a larger set iterating over the underlying stabilizer code such that all codewords can be obtained from a single stabilizer state. Then, one can apply a single-qubit Clifford transformation to map said stabilizer state into a cluster state.
Modular-qudit CWS code — Modular-qudit CWS codes reduce to CWS codes for \(q=2\).
Galois-qudit CWS code — Galois-qudit CWS codes reduce to CWS codes for \(q=2\).

Children

Amplitude-damping CWS code
\(((10,24,3))\) qubit code — The \(((10,24,3))\) qubit code is a CWS code [14].
\(((9,12,3))\) qubit code — The \(((9,12,3))\) qubit code is a cyclic CWS code [2,14].
\(((5+2r,3\times 2^{2r+1},2))\) Rains code — The \(((5+2r,3\times 2^{2r+1},2))\) qubit code family is a CWS family whose graph state is the union of the ring and Bell-pair graphs [2,14].
Smolin-Smith-Wehner (SSW) code — SSW codes can be formulated as CWS codes [2,14].

Cousins

Cluster-state code — A single cluster-state codeword is used to construct a CWS code.
Movassagh-Ouyang Hamiltonian code — The Movassagh-Ouyang codes overlap the CWS codes but neither family is contained in the other [15].
Spacetime code (STC) — CWS codes have been considered in the context of spacetime replication of quantum data [16,17], while STCs are designed to replicate classical data.
XP stabilizer code — The orbit representatives of XP codes play a similar role to the word operators of CWS codes.
\([[4,2,2]]\) Four-qubit code — A \([[4,1,2]]\) subcode can be thought of as a CWS code [18].
Five-qubit perfect code — The five-qubit perfect code is equivalent via a single-qubit Clifford circuit to a CWS code defined from a five-cycle graph and a classical repetition code [2,14][7; Table I].
\([[7,1,3]]\) Steane code — The Steane code is equivalent via a single-qubit Clifford unitary to a CWS code for a particular graph and classical code [7; Exam. 4].
Qubit stabilizer code — CWS codes whose underlying classical code is a linear binary code are qubit stabilizer codes containing a cluster-state codeword [2,18]. Since any stabilizer state is equivalent to a cluster state under a single-qubit Clifford circuit [3][4; Appx. A], any stabilizer code is similarly equivalent to a CWS code.

References

[1]: V. Aggarwal and A. R. Calderbank, “Boolean Functions, Projection Operators, and Quantum Error Correcting Codes”, IEEE Transactions on Information Theory 54, 1700 (2008) arXiv:cs/0610159 DOI
[2]: A. Cross et al., “Codeword Stabilized Quantum Codes”, IEEE Transactions on Information Theory 55, 433 (2009) arXiv:0708.1021 DOI
[3]: M. Van den Nest, J. Dehaene, and B. De Moor, “Graphical description of the action of local Clifford transformations on graph states”, Physical Review A 69, (2004) arXiv:quant-ph/0308151 DOI
[4]: J. Bausch and F. Leditzky, “Error Thresholds for Arbitrary Pauli Noise”, SIAM Journal on Computing 50, 1410 (2021) arXiv:1910.00471 DOI
[5]: Zeng, Bei. Quantum operations and codes beyond the Stabilizer-Clifford framework. Diss. Massachusetts Institute of Technology, 2009.
[6]: U. Kapshikar and S. Kundu, “On the Hardness of the Minimum Distance Problem of Quantum Codes”, IEEE Transactions on Information Theory 69, 6293 (2023) arXiv:2203.04262 DOI
[7]: A. A. Kovalev, I. Dumer, and L. P. Pryadko, “Design of additive quantum codes via the code-word-stabilized framework”, Physical Review A 84, (2011) arXiv:1108.5490 DOI
[8]: S. Sudevan et al., “Sequentially Encodable Codeword Stabilized Codes”, (2024) arXiv:2405.06142
[9]: Y. Li, I. Dumer, and L. P. Pryadko, “Clustered Error Correction of Codeword-Stabilized Quantum Codes”, Physical Review Letters 104, (2010) arXiv:0907.2038 DOI
[10]: Y. Li et al., “Clustered bounded-distance decoding of codeword-stabilized quantum codes”, 2010 IEEE International Symposium on Information Theory (2010) DOI
[11]: Li, Yunfan. Codeword Stabilized Quantum Codes and Their Error Correction. Diss. UC Riverside, 2010.
[12]: Y. Li et al., “Structured error recovery for code-word-stabilized quantum codes”, Physical Review A 81, (2010) arXiv:0912.3245 DOI
[13]: M. Grassl and M. Rötteler, “Nonadditive quantum codes”, Quantum Error Correction 261 (2013) DOI
[14]: Cross, Andrew William. Fault-tolerant quantum computer architectures using hierarchies of quantum error-correcting codes. Diss. Massachusetts Institute of Technology, 2008.
[15]: R. Movassagh and Y. Ouyang, “Constructing quantum codes from any classical code and their embedding in ground space of local Hamiltonians”, (2020) arXiv:2012.01453
[16]: P. Hayden and A. May, “Summoning information in spacetime, or where and when can a qubit be?”, Journal of Physics A: Mathematical and Theoretical 49, 175304 (2016) arXiv:1210.0913 DOI
[17]: P. Hayden et al., “Spacetime replication of continuous variable quantum information”, New Journal of Physics 18, 083043 (2016) arXiv:1601.02544 DOI
[18]: C. Cafaro, D. Markham, and P. van Loock, “Scheme for constructing graphs associated with stabilizer quantum codes”, (2014) arXiv:1407.2777

Page edit log

Victor V. Albert (2024-03-28) — most recent
Victor V. Albert (2022-04-21)
Victor V. Albert (2021-12-16)
Eric Kubischta (2021-12-15)

Cite as:

“Codeword stabilized (CWS) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2024. https://errorcorrectionzoo.org/c/cws

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/quantum/qubits/nonstabilizer/union_stabilizer/cws/cws.yml.