Qubit stabilizer code[1,2] 

Description

Also called a Pauli stabilizer code. An \(((n,2^k,d))\) qubit stabilizer code is denoted as \([[n,k]]\) or \([[n,k,d]]\), where \(d\) is the code's distance. Logical subspace is the joint eigenspace of commuting Pauli operators forming the code's stabilizer group \(\mathsf{S}\). Traditionally, the logical subspace is the joint \(+1\) eigenspace of a set of \(2^{n-k}\) commuting Pauli operators which do not contain \(-I\). The distance is the minimum weight of a Pauli string that implements a nontrivial logical operation in the code.

Binary symplectic representation: Each stabilizer code can be represented by a \((n-k) \times 2n\) check matrix (a.k.a. stabilizer generator matrix) \(H=(A|B)\), where each row \((a|b)\) is the binary symplectic representation of an element from a set of generating elements of the stabilizer group. In the symplectic representation, the single-qubit identity, \(X\), \(Y\), or \(Z\) Pauli matrices represented using two bits as \((0|0)\), \((1|0)\), \((1|1)\), and \((0|1)\), respectively. The check matrix can be brought into standard form via Gaussian elimination [3].

The stabilizer commutation condition can equivalently be stated in the symplectic representation. A pair of \(n\)-qubit stabilizers with symplectic representations \((a|b)\) and \((a^{\prime}|b^{\prime})\) commute iff their symplectic inner product is zero, \begin{align} a \cdot b^{\prime} + a^{\prime}\cdot b = \sum_{j=1}^{n} a_j b^{\prime}_j + a^{\prime}_i b_i = 0~. \tag*{(1)}\end{align} Binary symplectic representations of stabilizer group elements thus form a self-orthogonal subspace of \(GF(2)^{2n}\) with respect to the symplectic inner product.

Alternative representations include the decoupling representation, in which Pauli strings are represented as vectors over \(GF(2)\) using three bits [4], or the representation over \(GF(4)\) (see stabilizer codes over \(GF(4)\)).

Protection

Detects errors on up to \(d-1\) qubits, and corrects erasure errors on up to \(d-1\) qubits. More generally, define the normalizer \(\mathsf{N(S)}\) of \(\mathsf{S}\) to be the set of all Pauli operators that commute with all \(S\in\mathsf{S}\). A stabilizer code can correct a Pauli error set \({\mathcal{E}}\) if and only if \(E^\dagger F \notin \mathsf{N(S)}\setminus \mathsf{S}\) for all \(E,F \in {\mathcal{E}}\).

A stabilizer code is geometrically local if the support of the stabilizer generators is bounded by a ball of size independent of \(n\).

Encoding

Clifford circuits, i.e., those consisting of CNOT, Hadamard, and certain phase gates, using an algorithm based on the Gottesman-Knill theorem [5] or using ZX calculus [6–8].Circuits obtained by first constructing the CWS form of the code [9,10]. These consist of \(n\) Hadamard gates, a classical encoder which takes at most \(n\) CX gates for a single-qubit encoding code, and at most \(n(n-1)/2\) CZ gates to create the needed graph state.Lindbladian-based dissipative encoding [11,12], for which codespace is steady-state space of a Lindbladian. This does not give a speedup, in terms of scaling with \(n\), over circuit-based encoders [13].

Transversal Gates

All stabilizer codes realize Pauli transformations transversally; for a single logical qubit, these a realize dicyclic subgroup of \(SU(2)\). More generally, transversal logical gates are in a finite level of the Clifford hierarchy, which is shown using stabilizer disjointness [14] (see also [15,16]). Transversal gates for \(n\in\{1,2\}\) are semi-Clifford [17].

Gates

With pieceable fault-tolerance, any nondegenerate stabilizer code with a complete set of fault-tolerant single-qubit Clifford gates has a universal set of non-transversal fault-tolerant gates [18].

Decoding

The structure of stabilizer codes allows for syndrome-based decoding, where errors are corrected based on the results of stabilizer measurements (syndromes). The size of the circuit extracting the syndrome depends on the weight of its corresponding stabilizer generator. Maximum-likelihood (ML) decoding, i.e., the process of finding the most likely error, is \(NP\)-complete in general [19,20]. If the noise model is such that the most likely error is the lowest-weight error, then ML decoding is called minimum-weight decoding. Degenerate maximum-likelihood decoding, i.e., the process of finding the most likely error class (up to degeneracy of errors), is \(\#P\)-complete in general [21].Trellis decoder, which builds a compact representation of the algebraic structure of the normalizer \(\mathsf{N(S)}\) [22].Quantum extension of GRAND decoder [23].Deep neural-network probabilistic decoder [24].Generalized belief propagation (GBP) [25] based on a classical version [26].

Fault Tolerance

Logical Bell measurements can be done transversally, and thus fault tolerantly, by performing bitwise Bell measurements for each pair of qubits (with each member of the pair taken from one of the two code blocks) and processing the result.With pieceable fault-tolerance, any nondegenerate stabilizer code with a complete set of fault-tolerant single-qubit Clifford gates has a universal set of non-transversal fault-tolerant gates [18].Fault-tolerant error correction scheme by Shor [27], which is based on repeated measurements. A modification uses adaptive measurements [28].Generalization of Steane error correction stabilizer codes [29; Sec. 3.6].Fault-tolerant error correction scheme by Knill (a.k.a. telecorrection [30]), which is based on teleportation [31,32].GHz state distillation for Steane error correction [33].Syndrome extraction using flag qubits and classical codes [34].

Code Capacity Threshold

Bounds on code capacity thresholds using maximum-likelihood (ML) decoding can be obtained by mapping the effect of noise on the code to a statistical mechanical model [35–38].

Threshold

Computational thresholds against stochastic local noise can be achieved through repeated use of concatenatenation, and can rely on the same small code in every level [39–42]. The resulting code is highly degenerate, with all but an exponentially small fraction of generators having small weights. Circuit and measurement designs have to take case of the few stabilizer generators with large weights in order to be fault tolerant.

Notes

Introductions to stabilizer codes can be found in [2,43,44].Tables of bounds and examples of stabilizer codes for various \(n\) and \(k\), based on algorithms developed in Ref. [45], are maintained by M. Grassl at this website.Stabilizer error-recovery circuits can be simulated efficiently using dedicated software (e.g., STIM [46]).There is a correspondence between stabilizer codes and bilocal Clifford entanglement distillation circuits [47].

Parents

  • Codeword stabilized (CWS) code — If the CWS set \( \mathcal{W} \) is an abelian group not containing \(-I\), then the CWS code is a stabilizer code.
  • XP stabilizer code — The XP stabilizer formalism reduces to the Pauli formalism at \(N=2\).
  • Modular-qudit stabilizer code — Modular-qudit stabilizer codes for \(q=2\) correspond to qubit stabilizer codes. Modular-qudit stabilizer codes for prime-dimensional qudits \(q=p\) inherit most of the features of qubit stabilizer codes, including encoding an integer number of qudits and a Pauli group with a unique number of generators. Conversely, qubit codes can be extended to modular-qudit codes by decorating appropriate generators with powers. For example, \([[4,2,2]]\) qubit code generators can be adjusted to \(ZZZZ\) and \(XX^{-1} XX^{-1}\). A systematic procedure extending a qubit code to prime-qudit codes involves putting its generator matrix into local-dimension-invariant (LDI) form [48]. Various bounds exist on the distance of the resulting codes [49,50].
  • Galois-qudit stabilizer code — Galois-qudit stabilizer codes for \(q=2\) correspond to qubit stabilizer codes.
  • Qubit stabilizer operator-algebra quantum error-correcting code

Children

Cousins

  • Linear binary code — Qubit stabilizer codes are the closest quantum analogues of binary linear codes because addition modulo two corresponds to multiplication of stabilizers in the quantum case.
  • Dual linear code — Binary symplectic representations of stabilizer group elements form a linear code over \(GF(2)\) that is self-orthogonal with respect to the symplectic inner product [55; Thm. 27.3.6].
  • Metrological code — A joint \(+1\) and \(-1\) eigenstate of a set of stabilizer can form a metrological stabilizer code [56].
  • Spacetime circuit code — Spacetime circuit codes are useful for constructing fault-tolerant syndrome extraction circuits for qubit stabilizer codes.
  • Movassagh-Ouyang Hamiltonian code — Many, but not all, Movassagh-Ouyang codes are stabilizer codes.

References

[1]
A. R. Calderbank et al., “Quantum Error Correction and Orthogonal Geometry”, Physical Review Letters 78, 405 (1997) arXiv:quant-ph/9605005 DOI
[2]
D. Gottesman, “Stabilizer Codes and Quantum Error Correction”, (1997) arXiv:quant-ph/9705052
[3]
M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information (Cambridge University Press, 2012) DOI
[4]
Z. Yi et al., “Improved belief propagation decoding algorithm based on decoupling representation of Pauli operators for quantum LDPC codes”, (2023) arXiv:2305.17505
[5]
S. Aaronson and D. Gottesman, “Improved simulation of stabilizer circuits”, Physical Review A 70, (2004) arXiv:quant-ph/0406196 DOI
[6]
B. Coecke and R. Duncan, “Interacting Quantum Observables”, Automata, Languages and Programming 298 DOI
[7]
B. Coecke and R. Duncan, “Interacting quantum observables: categorical algebra and diagrammatics”, New Journal of Physics 13, 043016 (2011) arXiv:0906.4725 DOI
[8]
A. B. Khesin, J. Z. Lu, and P. W. Shor, “Graphical quantum Clifford-encoder compilers from the ZX calculus”, (2023) arXiv:2301.02356
[9]
I. Chuang et al., “Codeword stabilized quantum codes: Algorithm and structure”, Journal of Mathematical Physics 50, 042109 (2009) arXiv:0803.3232 DOI
[10]
A. Cross et al., “Codeword Stabilized Quantum Codes”, IEEE Transactions on Information Theory 55, 433 (2009) arXiv:0708.1021 DOI
[11]
J. P. Paz and W. H. Zurek, “Continuous Error Correction”, (1997) arXiv:quant-ph/9707049
[12]
J. Dengis, R. König, and F. Pastawski, “An optimal dissipative encoder for the toric code”, New Journal of Physics 16, 013023 (2014) arXiv:1310.1036 DOI
[13]
R. König and F. Pastawski, “Generating topological order: No speedup by dissipation”, Physical Review B 90, (2014) arXiv:1310.1037 DOI
[14]
T. Jochym-O’Connor, A. Kubica, and T. J. Yoder, “Disjointness of Stabilizer Codes and Limitations on Fault-Tolerant Logical Gates”, Physical Review X 8, (2018) arXiv:1710.07256 DOI
[15]
B. Zeng, A. Cross, and I. L. Chuang, “Transversality versus Universality for Additive Quantum Codes”, (2007) arXiv:0706.1382
[16]
J. T. Anderson and T. Jochym-O’Connor, “Classification of transversal gates in qubit stabilizer codes”, (2014) arXiv:1409.8320
[17]
B. Zeng, X. Chen, and I. L. Chuang, “Semi-Clifford operations, structure ofCkhierarchy, and gate complexity for fault-tolerant quantum computation”, Physical Review A 77, (2008) arXiv:0712.2084 DOI
[18]
T. J. Yoder, R. Takagi, and I. L. Chuang, “Universal Fault-Tolerant Gates on Concatenated Stabilizer Codes”, Physical Review X 6, (2016) arXiv:1603.03948 DOI
[19]
M.-H. Hsieh and F. Le Gall, “NP-hardness of decoding quantum error-correction codes”, Physical Review A 83, (2011) arXiv:1009.1319 DOI
[20]
Kuo, Kao-Yueh, and Chung-Chin Lu. "On the hardness of decoding quantum stabilizer codes under the depolarizing channel." 2012 International Symposium on Information Theory and its Applications. IEEE, 2012.
[21]
P. Iyer and D. Poulin, “Hardness of decoding quantum stabilizer codes”, (2013) arXiv:1310.3235
[22]
H. Ollivier and J.-P. Tillich, “Trellises for stabilizer codes: Definition and uses”, Physical Review A 74, (2006) arXiv:quant-ph/0512041 DOI
[23]
D. Cruz, F. A. Monteiro, and B. C. Coutinho, “Quantum Error Correction via Noise Guessing Decoding”, (2023) arXiv:2208.02744
[24]
S. Krastanov and L. Jiang, “Deep Neural Network Probabilistic Decoder for Stabilizer Codes”, Scientific Reports 7, (2017) arXiv:1705.09334 DOI
[25]
J. Old and M. Rispler, “Generalized Belief Propagation Algorithms for Decoding of Surface Codes”, Quantum 7, 1037 (2023) arXiv:2212.03214 DOI
[26]
J. S. Yedidia, W. T. Freeman, and Y. Weiss, Generalized belief propagation, in NIPS, Vol. 13 (2000) pp. 689–695.
[27]
P. W. Shor, “Fault-tolerant quantum computation”, (1997) arXiv:quant-ph/9605011
[28]
T. Tansuwannont, B. Pato, and K. R. Brown, “Adaptive syndrome measurements for Shor-style error correction”, Quantum 7, 1075 (2023) arXiv:2208.05601 DOI
[29]
Yoder, Theodore., DSpace@MIT Practical Fault-Tolerant Quantum Computation (2018)
[30]
C. M. Dawson, H. L. Haselgrove, and M. A. Nielsen, “Noise thresholds for optical cluster-state quantum computation”, Physical Review A 73, (2006) arXiv:quant-ph/0601066 DOI
[31]
E. Knill, “Quantum computing with realistically noisy devices”, Nature 434, 39 (2005) arXiv:quant-ph/0410199 DOI
[32]
E. Knill, “Scalable Quantum Computation in the Presence of Large Detected-Error Rates”, (2004) arXiv:quant-ph/0312190
[33]
N. Rengaswamy et al., “Distilling GHZ States using Stabilizer Codes”, (2022) arXiv:2109.06248
[34]
B. Anker and M. Marvian, “Flag Gadgets based on Classical Codes”, (2022) arXiv:2212.10738
[35]
E. Dennis et al., “Topological quantum memory”, Journal of Mathematical Physics 43, 4452 (2002) arXiv:quant-ph/0110143 DOI
[36]
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
[37]
A. A. Kovalev and L. P. Pryadko, “Spin glass reflection of the decoding transition for quantum error correcting codes”, (2014) arXiv:1311.7688
[38]
C. T. Chubb and S. T. Flammia, “Statistical mechanical models for quantum codes with correlated noise”, Annales de l’Institut Henri Poincaré D 8, 269 (2021) arXiv:1809.10704 DOI
[39]
E. Knill, R. Laflamme, and W. H. Zurek, “Resilient quantum computation: error models and thresholds”, Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences 454, 365 (1998) arXiv:quant-ph/9702058 DOI
[40]
D. Aharonov and M. Ben-Or, “Fault-Tolerant Quantum Computation With Constant Error Rate”, (1999) arXiv:quant-ph/9906129
[41]
J. Preskill, “Reliable quantum computers”, Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences 454, 385 (1998) arXiv:quant-ph/9705031 DOI
[42]
P. Aliferis, D. Gottesman, and J. Preskill, “Quantum accuracy threshold for concatenated distance-3 codes”, (2005) arXiv:quant-ph/0504218
[43]
J. Preskill. Lecture notes on Quantum Computation. (1997–2020) URL
[44]
M. Grassl, “Classical Information Theory and Classical Error Correction”, Lectures on Quantum Information 3 DOI
[45]
M. Grassl, “Searching for linear codes with large minimum distance”, Discovering Mathematics with Magma 287 DOI
[46]
C. Gidney, “Stim: a fast stabilizer circuit simulator”, Quantum 5, 497 (2021) arXiv:2103.02202 DOI
[47]
K. Goodenough et al., “Near-term \(n\) to \(k\) distillation protocols using graph codes”, (2023) arXiv:2303.11465
[48]
L. G. Gunderman, “Local-dimension-invariant qudit stabilizer codes”, Physical Review A 101, (2020) arXiv:1910.08122 DOI
[49]
A. J. Moorthy and L. G. Gunderman, “Local-dimension-invariant Calderbank-Shor-Steane Codes with an Improved Distance Promise”, (2021) arXiv:2110.11510
[50]
L. G. Gunderman, “Degenerate local-dimension-invariant stabilizer codes and an alternative bound for the distance preservation condition”, Physical Review A 105, (2022) arXiv:2110.15274 DOI
[51]
A. Kitaev, “Anyons in an exactly solved model and beyond”, Annals of Physics 321, 2 (2006) arXiv:cond-mat/0506438 DOI
[52]
S. Bravyi, B. M. Terhal, and B. Leemhuis, “Majorana fermion codes”, New Journal of Physics 12, 083039 (2010) arXiv:1004.3791 DOI
[53]
B. J. Brown and S. Roberts, “Universal fault-tolerant measurement-based quantum computation”, Physical Review Research 2, (2020) arXiv:1811.11780 DOI
[54]
F. Pastawski et al., “Holographic quantum error-correcting codes: toy models for the bulk/boundary correspondence”, Journal of High Energy Physics 2015, (2015) arXiv:1503.06237 DOI
[55]
M. F. Ezerman, "Quantum Error-Control Codes." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
[56]
P. Faist et al., “Time-energy uncertainty relation for noisy quantum metrology”, (2022) arXiv:2207.13707
Page edit log

Your contribution is welcome!

on github.com (edit & pull request)

edit on this site

Zoo Code ID: qubit_stabilizer

Cite as:
“Qubit stabilizer code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/qubit_stabilizer
BibTeX:
@incollection{eczoo_qubit_stabilizer,
  title={Qubit stabilizer code},
  booktitle={The Error Correction Zoo},
  year={2022},
  editor={Albert, Victor V. and Faist, Philippe},
  url={https://errorcorrectionzoo.org/c/qubit_stabilizer}
}
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/qubit_stabilizer

Cite as:

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

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