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~. \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 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

Circuits consisting of CNOT, Hadamard, and phase gates using algorithm based on the Gottesman-Knill theorem [5].Circuits obtained by first constructing the CWS form of the code [6][7]. 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.Dissipative preparation, for which codespace is steady-state space of a Lindbladian [8].Lindbladian-based dissipative encoding [9][8] that does not give a speedup, in terms of scaling with \(n\), over circuit-based encoders [10].

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 [11].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 [12].

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 decoding is \(NP\)-complete in general [13][14]. Degenerate maximum-likelihood decoding is \(\#P\)-complete in general [15], although can be polynomial-time for specific codes like the surface code [16].Trellis decoder, which builds a compact representation of the algebraic structure of the normalizer \(\mathsf{N(S)}\) [17].Quantum extension of GRAND decoder [18].Deep neural-network probabilistic decoder [19].

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 [12].Fault-tolerant error correction scheme by Shor [20], which is based on repeated measurements. A modification uses adaptive measurements [21].Generalization of Steane error correction stabilizer codes [22; Sec. 3.6].Fault-tolerant error correction scheme by Knill (a.k.a. telecorrection [23]), which is based on teleportation [24][25].

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 [26][27][28][29].

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 [30][31][32][33]. 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

Tables of bounds and examples of stabilizer codes for various \(n\) and \(k\), based on algorithms developed in Ref. [34], are maintained by M. Grassl at this website.Stabilizer error-recovery circuits can be simulated efficiently using dedicated software (e.g., STIM [35]).

Parents

  • Stabilizer code
  • 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\).
  • 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 ([40], 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 [41]. Various bounds exist on the distance of the resulting codes [42][43].
  • Galois-qudit stabilizer code — Galois-qudit stabilizer codes reduce to qubit stabilizer codes for \(q=2\).
  • Metrological code — A joint \(+1\) and \(-1\) eigenstate of a set of stabilizer can form a metrological stabilizer code [44].
  • Movassagh-Ouyang Hamiltonian code — Many, but not all, Movassagh-Ouyang codes are stabilizer codes.
  • Subsystem qubit stabilizer code — Gauge stabilizer codes reduce to stabilizer codes when there are no gauge qubits.
  • 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.

References

[1]
A. R. Calderbank et al., “Quantum Error Correction and Orthogonal Geometry”, Physical Review Letters 78, 405 (1997). DOI; quant-ph/9605005
[2]
Daniel Gottesman, “Stabilizer Codes and Quantum Error Correction”. 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). DOI; 0810.1983
[5]
S. Aaronson and D. Gottesman, “Improved simulation of stabilizer circuits”, Physical Review A 70, (2004). DOI; quant-ph/0406196
[6]
I. Chuang et al., “Codeword stabilized quantum codes: Algorithm and structure”, Journal of Mathematical Physics 50, 042109 (2009). DOI; 0803.3232
[7]
A. Cross et al., “Codeword Stabilized Quantum Codes”, IEEE Transactions on Information Theory 55, 433 (2009). DOI; 0708.1021
[8]
J. Dengis, R. König, and F. Pastawski, “An optimal dissipative encoder for the toric code”, New Journal of Physics 16, 013023 (2014). DOI; 1310.1036
[9]
Juan Pablo Paz and Wojciech Hubert Zurek, “Continuous Error Correction”. quant-ph/9707049
[10]
R. König and F. Pastawski, “Generating topological order: No speedup by dissipation”, Physical Review B 90, (2014). DOI; 1310.1037
[11]
S. Bravyi and R. König, “Classification of Topologically Protected Gates for Local Stabilizer Codes”, Physical Review Letters 110, (2013). DOI; 1206.1609
[12]
T. J. Yoder, R. Takagi, and I. L. Chuang, “Universal Fault-Tolerant Gates on Concatenated Stabilizer Codes”, Physical Review X 6, (2016). DOI; 1603.03948
[13]
M.-H. Hsieh and F. Le Gall, “NP-hardness of decoding quantum error-correction codes”, Physical Review A 83, (2011). DOI; 1009.1319
[14]
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.
[15]
Pavithran Iyer and David Poulin, “Hardness of decoding quantum stabilizer codes”. 1310.3235
[16]
S. Bravyi, M. Suchara, and A. Vargo, “Efficient algorithms for maximum likelihood decoding in the surface code”, Physical Review A 90, (2014). DOI; 1405.4883
[17]
H. Ollivier and J.-P. Tillich, “Trellises for stabilizer codes: Definition and uses”, Physical Review A 74, (2006). DOI; quant-ph/0512041
[18]
Diogo Cruz, Francisco A. Monteiro, and Bruno C. Coutinho, “Quantum Error Correction via Noise Guessing Decoding”. 2208.02744
[19]
S. Krastanov and L. Jiang, “Deep Neural Network Probabilistic Decoder for Stabilizer Codes”, Scientific Reports 7, (2017). DOI; 1705.09334
[20]
Peter W. Shor, “Fault-tolerant quantum computation”. quant-ph/9605011
[21]
Theerapat Tansuwannont and Kenneth R. Brown, “Adaptive syndrome measurements for Shor-style error correction”. 2208.05601
[22]
Yoder, Theodore., DSpace@MIT Practical Fault-Tolerant Quantum Computation (2018)
[23]
C. M. Dawson, H. L. Haselgrove, and M. A. Nielsen, “Noise thresholds for optical cluster-state quantum computation”, Physical Review A 73, (2006). DOI; quant-ph/0601066
[24]
E. Knill, “Quantum computing with realistically noisy devices”, Nature 434, 39 (2005). DOI; quant-ph/0410199
[25]
E. Knill, “Scalable Quantum Computation in the Presence of Large Detected-Error Rates”. quant-ph/0312190
[26]
E. Dennis et al., “Topological quantum memory”, Journal of Mathematical Physics 43, 4452 (2002). DOI; quant-ph/0110143
[27]
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). DOI; 1208.2317
[28]
Alexey A. Kovalev and Leonid P. Pryadko, “Spin glass reflection of the decoding transition for quantum error correcting codes”. 1311.7688
[29]
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). DOI; 1809.10704
[30]
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). DOI; quant-ph/9702058
[31]
Dorit Aharonov and Michael Ben-Or, “Fault-Tolerant Quantum Computation With Constant Error Rate”. quant-ph/9906129
[32]
J. Preskill, “Reliable quantum computers”, Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences 454, 385 (1998). DOI; quant-ph/9705031
[33]
Panos Aliferis, Daniel Gottesman, and John Preskill, “Quantum accuracy threshold for concatenated distance-3 codes”. quant-ph/0504218
[34]
M. Grassl, “Searching for linear codes with large minimum distance”, Discovering Mathematics with Magma 287. DOI
[35]
C. Gidney, “Stim: a fast stabilizer circuit simulator”, Quantum 5, 497 (2021). DOI; 2103.02202
[36]
S. Bravyi, B. M. Terhal, and B. Leemhuis, “Majorana fermion codes”, New Journal of Physics 12, 083039 (2010). DOI; 1004.3791
[37]
A. Kitaev, “Anyons in an exactly solved model and beyond”, Annals of Physics 321, 2 (2006). DOI; cond-mat/0506438
[38]
A. Y. Kitaev, “Unpaired Majorana fermions in quantum wires”, Physics-Uspekhi 44, 131 (2001). DOI; cond-mat/0010440
[39]
F. Pastawski et al., “Holographic quantum error-correcting codes: toy models for the bulk/boundary correspondence”, Journal of High Energy Physics 2015, (2015). DOI; 1503.06237
[40]
W. C. Huffman, J.-L. Kim, and P. Solé, Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021). DOI
[41]
L. G. Gunderman, “Local-dimension-invariant qudit stabilizer codes”, Physical Review A 101, (2020). DOI; 1910.08122
[42]
Arun J. Moorthy and Lane G. Gunderman, “Local-dimension-invariant Calderbank-Shor-Steane Codes with an Improved Distance Promise”. 2110.11510
[43]
L. G. Gunderman, “Degenerate local-dimension-invariant stabilizer codes and an alternative bound for the distance preservation condition”, Physical Review A 105, (2022). DOI; 2110.15274
[44]
Philippe Faist et al., “Time-energy uncertainty relation for noisy quantum metrology”. 2207.13707
Page edit log

Zoo code information

Internal code ID: qubit_stabilizer

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 |  | 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.