Qubit CSS code

Qubit CSS code[1–3]

Also known as Euclidean-construction qubit code.

Description

An \([[n,k,d]]\) stabilizer code admitting a set of stabilizer generators that are either \(Z\)-type or \(X\)-type Pauli strings. Codes can be defined from two classical codes and/or chain complexes over \(\mathbb{Z}_2\) per the qubit CSS-to-homology correspondence below. Strong CSS codes are codes for which there exists a set of \(X\) and \(Z\) stabilizer generators of equal weight.

The stabilizer generator matrix is of the form \begin{align} H=\begin{pmatrix}0 & H_{Z}\\ H_{X} & 0 \end{pmatrix} \label{eq:parity} \tag*{(1)}\end{align} such that the rows of the two blocks must be orthogonal \begin{align} H_X H_Z^T=0~. \label{eq:comm} \tag*{(2)}\end{align} The above condition guarantees that the \(X\)-stabilizer generators, defined in the symplectic representation as rows of \(H_X\), commute with the \(Z\)-stabilizer generators associated with \(H_Z\).

Encoding is based on two related binary linear codes, an \([n,k_X,d_X]\) code \(C_X\) and \([n,k_Z,d_Z]\) code \(C_Z\), satisfying \(C_X^\perp \subseteq C_Z\). The resulting CSS code has \(k=k_X+k_Z-n\) logical qubits and distance \(d\geq\min\{d_X,d_Z\}\). The \(H_X\) (\(H_Z\)) block of \(H\) (1) is the parity-check matrix of the code \(C_Z\) (\(C_X\)). The requirement \(C_X^\perp \subseteq C_Z\) guarantees (2) and also implies \(C_Z^\perp \subseteq C_X \). Basis states for the code are, for \(\gamma \in C_X\), \begin{align} |\gamma + C_Z^\perp \rangle = \frac{1}{\sqrt{|C_Z^\perp|}} \sum_{\eta \in C_Z^\perp} |\gamma + \eta\rangle. \tag*{(3)}\end{align}

A CSS code has stabilizer weight \(w\) if the highest weight of any stabilizer generator is \(w\), i.e., any row of \(H_X\) and \(H_Z\) has weight at most \(w\). In the context of comparing weight as well as of determining distances for noise models biased toward \(X\)- or \(Z\)-type errors, an extended notation for asymmetric CSS codes is \([[n,k,(d_X,d_Z),w]]\) or \([[n,k,d_X/d_Z,w]]\). The quantity \(\min\{d_X,d_Z\}\) is often called the worst-case minimum distance and is often less than the actual code distance due to degeneracy [4].

To find the minimum distance of degenerate CSS code, we have to first remove the codewords of the smaller codes as those codewords correspond to stabilizer generators instead of logical operators. Thus the general formulae for the minimum distances \(d, d_Z, d_X\) for an \([[n,k,d]]\) or \([[n,k,(d_X,d_Z)]]\) \(CSS(C_X, C_Z)\) code are: \begin{align} d_{X}&=\min\{ w_H(c) | c \in C_X \setminus C_Z^\perp \} \tag*{(4)}\\ d_{Z}&=\min\{ w_H(c) | c \in C_Z \setminus C_X^\perp \} \tag*{(5)}\\ d&=\min\{d_X,d_Z\}~, \tag*{(6)}\end{align} where \(w_H\) is the Hamming weight of a codeword.

CSS-to-homology correspondence

Qubit CSS-to-homology correspondence: CSS codes and their properties can be formulated in terms of homology theory, yielding a powerful correspondence between codes and chain complexes, the primary homological structures. There exists a many-to-one mapping from size three chain complexes to CSS codes [5–8] that allows one to extract code properties from topological features of the complexes. Codes constructed in this manner are sometimes called homological CSS codes, but they are equivalent to CSS codes. This mapping of codes to manifolds allows the application of structures from topology to error correction, yielding various QLDPC codes with favorable properties.

A chain complex of size three is given by binary vector spaces \(A_2\), \(A_1\), \(A_0\) and binary matrices \(\partial_{i=1,2}\) (called boundary operators) \(A_i\) to \(A_{i-1}\) that satisfy \(\partial_1 \partial_2 = 0\). Such a complex is typically denoted as \begin{align} A_2 \xrightarrow{\partial_2} A_1 \xrightarrow{\partial_1} A_0~. \label{eq:chain} \tag*{(7)}\end{align} One constructs a CSS code by associating a physical qubit to every basis element of \(A_1\), and defining parity-check matrices \(H_X=\partial_1\) and \(H_Z=\partial_2^T\)). That way, the spaces \(A_0\) and \(A_2\) can be associated with \(X\)-type and \(Z\)-type Pauli operators, respectively, and boundary operators determine the Paulis making up the stabilizer generators. The requirement \(\partial_1 \partial_2 = 0\) guarantees that the \(X\)-stabilizer generators associated with \(H_X\) commute with the \(Z\)-stabilizer generators associated with \(H_Z\).

Usually, the chain complex (7) used in the construction comes from the chain complex associated with a cellulation of a manifold. When the manifold is a two-dimensional surface, its entire chain is used. Higher-dimensional manifolds allow for longer chain complexes, and one can use the three largest non-trivial vector spaces in its chain.

CSS codes saturate a type of error correction uncertainty relation [2; Thm. 3], which is a special case of an entropic uncertainty relation between a pair of bases [9–11]. The code state \(\sum_{c\in C_{Z}}|c\rangle\) can be expressed in terms of either basis states labeled by the code \(C_{Z}\) or its dual, satisfying, with equality, the relation \begin{align} |C_{Z}||C_{Z}^{\perp}| \geq 2^{n}\,. \tag*{(8)}\end{align}

Protection

Detects errors on \(d-1\) qubits, corrects errors on \(\left\lfloor (d-1)/2 \right\rfloor\) qubits.

Using the relation to chain complexes, the number of encoded logical qubits is equal to the dimension of the first \(\mathbb{Z}_2\)-homology of the chain complex, \(H_1(\partial, \mathbb{Z}_2) = \frac{\text{Ker}(\partial_1)}{\text{Im}(\partial_2)}\).

The distance of the CSS code is equal to the minimum of the combinatorial (\(d-1\))-systole of the cellulated \(d\)-dimensional manifold and its dual.

Rate

For a depolarizing channel with probability \(p\), CSS codes allowing for arbitrarily accurate recovery exist with asymptotic rate \(1-2h(p)\), where \(h\) is the binary entropy function [12].

Encoding

Stabilizer measurement [13].Clusterization, i.e., measurement of a particular cluster state [14].

Transversal Gates

All CSS codes admit transversal Pauli and CNOT gates [15]. Self-dual CSS codes admit a transversal Hadamard, completing the Clifford group. A CSS code is doubly-even (triply-even) if all \(X\)-type stabilizer generators have weight divisible by four (eight); such codes yield a transversal \(S\) (\(T\)) gate [16].

Gates

LDPC CSS code symmetries called \(XZ\)-dualities allow for fold-transversal gates, i.e., transversal gates followed by qubit permutations [17].Generalized lattice surgery [18].

Decoding

Coherent decoders allow for measurement-free error correction [19]. One method is table/multi-control decoding [20], which scales exponentially with the number of ancillas used in syndrome measurement. Another method, the Ising-based decoder, utilizes the mapping of the effect of the noise to a statistical mechanical model [12,21] such that the decoding problem maps to preparation of the ground state of an Ising model.Decoders based on neural networks [22].

Fault Tolerance

Steane error correction, where fault-tolerance is ensured by preparing ancillary encoded states and extracting syndromes via \(CNOT\) gates [23].Homomorphic gadgets fault-tolerant measurement unify Steane and Shor error correction [24].Parallel syndrome extraction for distance-three codes can be done fault-tolerantly using one flag qubit [25].Distance-preserving flag fault-tolerant error correction using lookup tables for small codes [26].A fault-tolerant error-correction protocol using \(O(d\log d)\) syndrome measurements can be applied to any CSS code with distance \(d \geq \Omega(n^{\alpha})\) for any \(\alpha > 0\) [27].

Code Capacity Threshold

Bounds on code capacity thresholds for various noise models exist in terms of stabilizer generator weights [28,29].

Realizations

Fully homomorphic encryption [30].Entanglement purification protocols related to quantum key distribution (QKD) [31].Cryptographic applications stemming from the monogamy of entanglement of CSS code and error words [32].

Notes

See Refs. [4,33–35] for simple examples.Introduction to Qubit CSS-to-homology correspondence by M. Hastings.Using linear programming to solve a set of equations and inequalities on weight distribution of a classical self-orthogonal code \(C=(n, 2^n-k)\) and its dual, one can find a \(C\) such that the \([[n,k,d]]\) CSS code constructed using \(C\) and its dual would have rate and distance close to the Singleton bound [36].

Parents

CPC code — CSS codes are a subset of CPC codes [37], with the latter not requiring the two classical codes to be related.
Movassagh-Ouyang Hamiltonian code — Movassagh-Ouyang codes stem from a prescription that converts an arbitrary classical code into a quantum code.
Modular-qudit CSS code — Modular-qudit CSS codes for \(q=2\) are (qubit) CSS codes.
Galois-qudit CSS code — Galois-qudit CSS codes for \(q=2\) are (qubit) CSS codes.

Children

Cousins

Qubit stabilizer code — CSS codes are stabilizer codes whose stabilizer groups admit a generating set of pure-\(X\) and pure-\(Z\) Pauli strings. Additionally, any \([[n,k,d]]\) stabilizer code can be mapped onto a \([[2n,2k,\geq d]]\) CSS code, with the mapping preserving geometric locality of a code up to a constant factor [38] (see also [39]).
Linear binary code — The CSS construction uses two related binary linear codes \(C_X\) and \(C_Z\).
Dual linear code — CSS codes for which \(C_X=C_Z \equiv C\) are called self-orthogonal since \(C^{\perp} \subseteq C\). The stabilizer group of such codes is invariant under the Hadamard gate exchanging \(X\) and \(Z\).
Alternant code — Alternant codes used in the CSS construction yield quantum codes that asymptotically achieve the quantum Gilbert-Varshamov bound [40].
Random quantum code — Random CSS codes asymptotically achieve linear distance with high probability, achieving the quantum Gilbert-Varshamov bound [1].
Algebraic-geometry (AG) code — Algebraic geometry codes can be plugged into the CSS construction to yield asymptotically good quantum codes [41].
Quantum spherical code (QSC) — CSS codes concatenated with two-component cat codes form QSCs which have a weight-based notion of distance.
Quantum locally testable code (QLTC) — A qubit CSS code defined by \(H_{Z}\) and \(H_{X}\) is glocally testable with some soundness iff the constituent codes \(\ker H_{Z}\) and \(\ker H_{X}\) are locally testable with the same soundness [42; Fact 17].
Majorana stabilizer code — When constructing a Majorana stabilizer code from a self-orthogonal classical code with an odd number of bits and generator matrix \(G\), a more complex procedure must be applied to ensure that the fermion code has an even number of Majorana zero modes, and thus a physical Hilbert space [39,43]. Rather than taking \(G\) to be the stabilizer matrix as in the even case, we take \(G\oplus G\). This is a concatenation of classical codes as in the CSS construction and it yields a mapping \([2N-1,k,d]\rightarrow [[2N-1,2N-1-k,d^\perp]]_f\). This procedure may be further generalized by concatenating two different self-orthogonal classical codes with an odd number of bits, as is often done in the CSS construction.
Cluster-state code — A resource cluster state can be constructed out of any qubit CSS code via foliation. Conversely, CSS codes can be constructed out of cluster states [14].
XP stabilizer code — Each XP-regular code can be mapped to a CSS code with a similar logical operator structure [44].
EA qubit stabilizer code — As opposed to CSS codes, EA qubit stabilizer codes can be constructed from any linear binary code.
Qubit BCH code — Some qubit BCH codes are CSS.
Subsystem CSS code — Subsystem qubit CSS codes reduce to (subspace) CSS qubit codes when there is no gauge subsystem.

References

[1]: A. R. Calderbank and P. W. Shor, “Good quantum error-correcting codes exist”, Physical Review A 54, 1098 (1996) arXiv:quant-ph/9512032 DOI
[2]: A. M. Steane, “Error Correcting Codes in Quantum Theory”, Physical Review Letters 77, 793 (1996) DOI
[3]: “Multiple-particle interference and quantum error correction”, Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences 452, 2551 (1996) arXiv:quant-ph/9601029 DOI
[4]: D. Gottesman. Surviving as a quantum computer in a classical world
[5]: A. Y. Kitaev, “Quantum computations: algorithms and error correction”, Russian Mathematical Surveys 52, 1191 (1997) DOI
[6]: H. Bombin and M. A. Martin-Delgado, “Homological error correction: Classical and quantum codes”, Journal of Mathematical Physics 48, (2007) arXiv:quant-ph/0605094 DOI
[7]: S. Bravyi and M. B. Hastings, “Homological Product Codes”, (2013) arXiv:1311.0885
[8]: N. P. Breuckmann, “PhD thesis: Homological Quantum Codes Beyond the Toric Code”, (2018) arXiv:1802.01520
[9]: I. Białynicki-Birula and J. Mycielski, “Uncertainty relations for information entropy in wave mechanics”, Communications in Mathematical Physics 44, 129 (1975) DOI
[10]: D. Deutsch, “Uncertainty in Quantum Measurements”, Physical Review Letters 50, 631 (1983) DOI
[11]: H. Maassen and J. B. M. Uffink, “Generalized entropic uncertainty relations”, Physical Review Letters 60, 1103 (1988) DOI
[12]: E. Dennis et al., “Topological quantum memory”, Journal of Mathematical Physics 43, 4452 (2002) arXiv:quant-ph/0110143 DOI
[13]: J. Łodyga et al., “Simple scheme for encoding and decoding a qubit in unknown state for various topological codes”, Scientific Reports 5, (2015) arXiv:1404.2495 DOI
[14]: A. Bolt et al., “Foliated Quantum Error-Correcting Codes”, Physical Review Letters 117, (2016) arXiv:1607.02579 DOI
[15]: P. W. Shor, “Fault-tolerant quantum computation”, (1997) arXiv:quant-ph/9605011
[16]: S. Bravyi and A. Cross, “Doubled Color Codes”, (2015) arXiv:1509.03239
[17]: N. P. Breuckmann and S. Burton, “Fold-Transversal Clifford Gates for Quantum Codes”, (2022) arXiv:2202.06647
[18]: A. Cowtan and S. Burton, “CSS code surgery as a universal construction”, (2023) arXiv:2301.13738
[19]: T. Inada et al., “Measurement-Free Ultrafast Quantum Error Correction by Using Multi-Controlled Gates in Higher-Dimensional State Space”, (2021) arXiv:2109.00086
[20]: G. A. Paz-Silva, G. K. Brennen, and J. Twamley, “Fault Tolerance with Noisy and Slow Measurements and Preparation”, Physical Review Letters 105, (2010) arXiv:1002.1536 DOI
[21]: A. T. Schmitz, “Thermal Stability of Dynamical Phase Transitions in Higher Dimensional Stabilizer Codes”, (2020) arXiv:2002.11733
[22]: Y. Choukroun and L. Wolf, “Deep Quantum Error Correction”, (2023) arXiv:2301.11930
[23]: A. M. Steane, “Active Stabilization, Quantum Computation, and Quantum State Synthesis”, Physical Review Letters 78, 2252 (1997) arXiv:quant-ph/9611027 DOI
[24]: S. Huang, T. Jochym-O’Connor, and T. J. Yoder, “Homomorphic Logical Measurements”, (2022) arXiv:2211.03625
[25]: P.-H. Liou and C.-Y. Lai, “Parallel syndrome extraction with shared flag qubits for Calderbank-Shor-Steane codes of distance three”, Physical Review A 107, (2023) arXiv:2208.00581 DOI
[26]: B. Pato et al., “Optimization tools for distance-preserving flag fault-tolerant error correction”, (2023) arXiv:2306.12862
[27]: N. Delfosse, B. W. Reichardt, and K. M. Svore, “Beyond Single-Shot Fault-Tolerant Quantum Error Correction”, IEEE Transactions on Information Theory 68, 287 (2022) arXiv:2002.05180 DOI
[28]: A. A. Kovalev and L. P. Pryadko, “Fault tolerance of quantum low-density parity check codes with sublinear distance scaling”, Physical Review A 87, (2013) arXiv:1208.2317 DOI
[29]: I. Dumer, A. A. Kovalev, and L. P. Pryadko, “Thresholds for Correcting Errors, Erasures, and Faulty Syndrome Measurements in Degenerate Quantum Codes”, Physical Review Letters 115, (2015) arXiv:1412.6172 DOI
[30]: G. Alagic et al., “Quantum Fully Homomorphic Encryption with Verification”, Advances in Cryptology – ASIACRYPT 2017 438 (2017) arXiv:1708.09156 DOI
[31]: P. W. Shor and J. Preskill, “Simple Proof of Security of the BB84 Quantum Key Distribution Protocol”, Physical Review Letters 85, 441 (2000) arXiv:quant-ph/0003004 DOI
[32]: A. Coladangelo et al., “Hidden Cosets and Applications to Unclonable Cryptography”, (2022) arXiv:2107.05692
[33]: A. M. Steane, “Simple quantum error-correcting codes”, Physical Review A 54, 4741 (1996) arXiv:quant-ph/9605021 DOI
[34]: M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information (Cambridge University Press, 2012) DOI
[35]: J. Preskill. Lecture notes on Quantum Computation. (1997–2020) URL
[36]: A. R. Calderbank et al., “Quantum Error Correction via Codes over GF(4)”, (1997) arXiv:quant-ph/9608006
[37]: N. Chancellor et al., “Graphical structures for design and verification of quantum error correction”, Quantum Science and Technology 8, 045028 (2023) arXiv:1611.08012 DOI
[38]: M. L. Liu, N. Tantivasadakarn, and V. V. Albert, “Subsystem CSS codes, a tighter stabilizer-to-CSS mapping, and Goursat’s Lemma”, (2023) arXiv:2311.18003
[39]: S. Bravyi, B. M. Terhal, and B. Leemhuis, “Majorana fermion codes”, New Journal of Physics 12, 083039 (2010) arXiv:1004.3791 DOI
[40]: J. Fan et al., “Partially Concatenated Calderbank-Shor-Steane Codes Achieving the Quantum Gilbert-Varshamov Bound Asymptotically”, IEEE Transactions on Information Theory 69, 262 (2023) DOI
[41]: A. Ashikhmin, S. Litsyn, and M. Tsfasman, “Asymptotically good quantum codes”, Physical Review A 63, (2001) arXiv:quant-ph/0006061 DOI
[42]: L. Eldar and A. W. Harrow, “Local Hamiltonians Whose Ground States Are Hard to Approximate”, 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) (2017) arXiv:1510.02082 DOI
[43]: S. Vijay and L. Fu, “Quantum Error Correction for Complex and Majorana Fermion Qubits”, (2017) arXiv:1703.00459
[44]: M. A. Webster, B. J. Brown, and S. D. Bartlett, “The XP Stabiliser Formalism: a Generalisation of the Pauli Stabiliser Formalism with Arbitrary Phases”, Quantum 6, 815 (2022) arXiv:2203.00103 DOI

Page edit log

Christopher A. Pattison (2023-08-12) — most recent
Balint Pato (2023-02-28)
Balint Pato (2023-02-25)
Victor V. Albert (2022-09-10)
Victor V. Albert (2022-05-18)
Armin Gerami (2022-05-16)
Leonid Pryadko (2022-02-16)
Victor V. Albert (2022-02-16)
Seyed Sajjad Nezhadi (2021-12-14)
Victor V. Albert (2021-11-04)

Cite as:

“Qubit CSS code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023. https://errorcorrectionzoo.org/c/qubit_css

Github: https://github.com/errorcorrectionzoo/eczoo_data/tree/main/codes/quantum/qubits/stabilizer/qubit_css.yml.