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.

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. 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} Symplectic representations of stabilizer group elements thus form a self-orthogonal subspace of \(GF(2)^{2n}\) with respect to the symplectic inner product.

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\). There is an upper bound of \(d \leq O(L^{D-1})\) on the distance [4] of geometrically local stabilizer codes arranged in a \(D\)-dimensional lattice of length \(L\) with \(n=L^D\).

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].Circuits obtained by first constructing the CWS form of the code [7][8]. 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 [9][10], 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 [11].

Transversal Gates

Transversal logical gates are in a finite level of the Clifford hierarchy [12] (see also [13][14]). Transversal gates for \(n\in\{1,2\}\) are semi-Clifford [15].

Gates

Logical gates implemented via constant-depth quantum circuits of \(D\)-dimensional geometrically local stabilizer codes lie in the \(D\)th level of the Clifford hierarchy [16].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 [17].

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 [18][19]. 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 [20].Trellis decoder, which builds a compact representation of the algebraic structure of the normalizer \(\mathsf{N(S)}\) [21].Quantum extension of GRAND decoder [22].Deep neural-network probabilistic decoder [23].Generalized belief propagation (GBP) [24] based on a classical version [25].

Fault Tolerance

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 [17].Fault-tolerant error correction scheme by Shor [26], which is based on repeated measurements. A modification uses adaptive measurements [27].Generalization of Steane error correction stabilizer codes [28; Sec. 3.6].Fault-tolerant error correction scheme by Knill (a.k.a. telecorrection [29]), which is based on teleportation [30][31].GHz state distillation for Steane error correction [32].Syndrome extraction using flag qubits and classical codes [33].

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 [34][35][36][37].

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 [38][39][40][41]. 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][42][43].Tables of bounds and examples of stabilizer codes for various \(n\) and \(k\), based on algorithms developed in Ref. [44], are maintained by M. Grassl at this website.Stabilizer error-recovery circuits can be simulated efficiently using dedicated software (e.g., STIM [45]).

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\).
  • Stabilizer code
  • Quantum Lego code — Qubit stabilizer codes are quantum Lego codes built out of atomic blocks such as the 2-qubit repetition code, single-qubit trivial stabilizer codes, and tensor-products of the \(|0\rangle\) state.

Children

Cousins

  • Linear binary code — Qubit stabilizer codes are quantum analogues of binary linear codes.
  • Dual linear code — Symplectic representations of stabilizer group elements form a linear code over \(GF(2)\) that is self-orthogonal with respect to the symplectic inner product ([49], Thm. 27.3.6).
  • Hamiltonian-based code — Codespace is the ground-state space of the code Hamiltonian, which consists of an equal linear combination of stabilizer generators and which can be made into a commuting projector Hamiltonian.
  • Modular-qudit stabilizer code — 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 [50]. Various bounds exist on the distance of the resulting codes [51][52].
  • Translationally invariant stabilizer code — Qubit stabilizer codes can be thought of as translationally-invariant stabilizer codes for dimension \(D = 0\), with the lattice consisting of a single site.
  • Metrological code — A joint \(+1\) and \(-1\) eigenstate of a set of stabilizer can form a metrological stabilizer code [53].
  • Cluster-state code — Any fault-tolerant scheme based on qubit stabilizer codes can be mapped into an MBQC protocol [54].
  • Movassagh-Ouyang Hamiltonian code — Many, but not all, Movassagh-Ouyang codes are stabilizer codes.
  • Galois-qudit stabilizer code — Galois-qudit stabilizer codes reduce to qubit stabilizer codes for \(q=2\).

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]
S. Bravyi and B. Terhal, “A no-go theorem for a two-dimensional self-correcting quantum memory based on stabilizer codes”, New Journal of Physics 11, 043029 (2009) arXiv:0810.1983 DOI
[5]
S. Aaronson and D. Gottesman, “Improved simulation of stabilizer circuits”, Physical Review A 70, (2004) arXiv:quant-ph/0406196 DOI
[6]
A. B. Khesin, J. Z. Lu, and P. W. Shor, “Graphical quantum Clifford-encoder compilers from the ZX calculus”, (2023) arXiv:2301.02356
[7]
I. Chuang et al., “Codeword stabilized quantum codes: Algorithm and structure”, Journal of Mathematical Physics 50, 042109 (2009) arXiv:0803.3232 DOI
[8]
A. Cross et al., “Codeword Stabilized Quantum Codes”, IEEE Transactions on Information Theory 55, 433 (2009) arXiv:0708.1021 DOI
[9]
J. P. Paz and W. H. Zurek, “Continuous Error Correction”, (1997) arXiv:quant-ph/9707049
[10]
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
[11]
R. König and F. Pastawski, “Generating topological order: No speedup by dissipation”, Physical Review B 90, (2014) arXiv:1310.1037 DOI
[12]
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
[13]
B. Zeng, A. Cross, and I. L. Chuang, “Transversality versus Universality for Additive Quantum Codes”, (2007) arXiv:0706.1382
[14]
J. T. Anderson and T. Jochym-O’Connor, “Classification of transversal gates in qubit stabilizer codes”, (2014) arXiv:1409.8320
[15]
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
[16]
S. Bravyi and R. König, “Classification of Topologically Protected Gates for Local Stabilizer Codes”, Physical Review Letters 110, (2013) arXiv:1206.1609 DOI
[17]
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
[18]
M.-H. Hsieh and F. Le Gall, “NP-hardness of decoding quantum error-correction codes”, Physical Review A 83, (2011) arXiv:1009.1319 DOI
[19]
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.
[20]
P. Iyer and D. Poulin, “Hardness of decoding quantum stabilizer codes”, (2013) arXiv:1310.3235
[21]
H. Ollivier and J.-P. Tillich, “Trellises for stabilizer codes: Definition and uses”, Physical Review A 74, (2006) arXiv:quant-ph/0512041 DOI
[22]
D. Cruz, F. A. Monteiro, and B. C. Coutinho, “Quantum Error Correction via Noise Guessing Decoding”, (2022) arXiv:2208.02744
[23]
S. Krastanov and L. Jiang, “Deep Neural Network Probabilistic Decoder for Stabilizer Codes”, Scientific Reports 7, (2017) arXiv:1705.09334 DOI
[24]
J. Old and M. Rispler, “Generalized Belief Propagation Algorithms for Decoding of Surface Codes”, (2022) arXiv:2212.03214
[25]
J. S. Yedidia, W. T. Freeman, and Y. Weiss, Generalized belief propagation, in NIPS, Vol. 13 (2000) pp. 689–695.
[26]
P. W. Shor, “Fault-tolerant quantum computation”, (1997) arXiv:quant-ph/9605011
[27]
T. Tansuwannont and K. R. Brown, “Adaptive syndrome measurements for Shor-style error correction”, (2022) arXiv:2208.05601
[28]
Yoder, Theodore., DSpace@MIT Practical Fault-Tolerant Quantum Computation (2018)
[29]
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
[30]
E. Knill, “Quantum computing with realistically noisy devices”, Nature 434, 39 (2005) arXiv:quant-ph/0410199 DOI
[31]
E. Knill, “Scalable Quantum Computation in the Presence of Large Detected-Error Rates”, (2004) arXiv:quant-ph/0312190
[32]
N. Rengaswamy et al., “Distilling GHZ States using Stabilizer Codes”, (2022) arXiv:2109.06248
[33]
B. Anker and M. Marvian, “Flag Gadgets based on Classical Codes”, (2022) arXiv:2212.10738
[34]
E. Dennis et al., “Topological quantum memory”, Journal of Mathematical Physics 43, 4452 (2002) arXiv:quant-ph/0110143 DOI
[35]
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
[36]
A. A. Kovalev and L. P. Pryadko, “Spin glass reflection of the decoding transition for quantum error correcting codes”, (2014) arXiv:1311.7688
[37]
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
[38]
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
[39]
D. Aharonov and M. Ben-Or, “Fault-Tolerant Quantum Computation With Constant Error Rate”, (1999) arXiv:quant-ph/9906129
[40]
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
[41]
P. Aliferis, D. Gottesman, and J. Preskill, “Quantum accuracy threshold for concatenated distance-3 codes”, (2005) arXiv:quant-ph/0504218
[42]
J. Preskill. Lecture notes on Quantum Computation. (1997–2020) URL
[43]
M. Grassl, “Classical Information Theory and Classical Error Correction”, Lectures on Quantum Information 3 DOI
[44]
M. Grassl, “Searching for linear codes with large minimum distance”, Discovering Mathematics with Magma 287 DOI
[45]
C. Gidney, “Stim: a fast stabilizer circuit simulator”, Quantum 5, 497 (2021) arXiv:2103.02202 DOI
[46]
S. Bravyi, B. M. Terhal, and B. Leemhuis, “Majorana fermion codes”, New Journal of Physics 12, 083039 (2010) arXiv:1004.3791 DOI
[47]
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
[48]
A. Kitaev, “Anyons in an exactly solved model and beyond”, Annals of Physics 321, 2 (2006) arXiv:cond-mat/0506438 DOI
[49]
W. C. Huffman, J.-L. Kim, and P. Solé, Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
[50]
L. G. Gunderman, “Local-dimension-invariant qudit stabilizer codes”, Physical Review A 101, (2020) arXiv:1910.08122 DOI
[51]
A. J. Moorthy and L. G. Gunderman, “Local-dimension-invariant Calderbank-Shor-Steane Codes with an Improved Distance Promise”, (2021) arXiv:2110.11510
[52]
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
[53]
P. Faist et al., “Time-energy uncertainty relation for noisy quantum metrology”, (2022) arXiv:2207.13707
[54]
B. J. Brown and S. Roberts, “Universal fault-tolerant measurement-based quantum computation”, Physical Review Research 2, (2020) arXiv:1811.11780 DOI
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/qubit_stabilizer.yml.