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

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

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 [5].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 [6].

Decoding

The structure of stabilizer codes allows for syndrome-based decoding, where errors are corrected based on the results of stabilizer measurements (syndromes). Finding an optimal decoder is \(\#P\)-hard [7].Trellis decoder, which builds a compact representation of the algebraic structure of the normalizer \(\mathsf{N(S)}\) [8].

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 [6].Fault-tolerant error correction can be done using Shor error correction [9], which is based on repeated measurements, or Knill error correction, which is based on teleportation [10][11].

Code Capacity Threshold

For correlated Pauli noise, bounds on code capacity thresholds for any stabilizer codes can be obtained by mapping the effect of noise on the code to a statistical mechanical model [12][13][14][15].

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 [16][17][18][19]. 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. [20], are maintained by M. Grassl at this website.

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.
  • 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 [25]. Various bounds exist on the distance of the resulting codes [26][27].
  • 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.

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} }
Permanent link:
https://errorcorrectionzoo.org/c/qubit_stabilizer

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, 2009). 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. Bravyi and R. König, “Classification of Topologically Protected Gates for Local Stabilizer Codes”, Physical Review Letters 110, (2013). DOI; 1206.1609
[6]
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
[7]
Pavithran Iyer and David Poulin, “Hardness of decoding quantum stabilizer codes”. 1310.3235
[8]
H. Ollivier and J.-P. Tillich, “Trellises for stabilizer codes: Definition and uses”, Physical Review A 74, (2006). DOI; quant-ph/0512041
[9]
Peter W. Shor, “Fault-tolerant quantum computation”. quant-ph/9605011
[10]
E. Knill, “Quantum computing with realistically noisy devices”, Nature 434, 39 (2005). DOI; quant-ph/0410199
[11]
E. Knill, “Scalable Quantum Computation in the Presence of Large Detected-Error Rates”. quant-ph/0312190
[12]
E. Dennis et al., “Topological quantum memory”, Journal of Mathematical Physics 43, 4452 (2002). DOI; quant-ph/0110143
[13]
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
[14]
Alexey A. Kovalev and Leonid P. Pryadko, “Spin glass reflection of the decoding transition for quantum error correcting codes”. 1311.7688
[15]
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
[16]
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
[17]
Dorit Aharonov and Michael Ben-Or, “Fault-Tolerant Quantum Computation With Constant Error Rate”. quant-ph/9906129
[18]
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
[19]
Panos Aliferis, Daniel Gottesman, and John Preskill, “Quantum accuracy threshold for concatenated distance-3 codes”. quant-ph/0504218
[20]
M. Grassl, “Searching for linear codes with large minimum distance”, Discovering Mathematics with Magma 287. DOI
[21]
S. Bravyi, B. M. Terhal, and B. Leemhuis, “Majorana fermion codes”, New Journal of Physics 12, 083039 (2010). DOI; 1004.3791
[22]
A. Kitaev, “Anyons in an exactly solved model and beyond”, Annals of Physics 321, 2 (2006). DOI; cond-mat/0506438
[23]
A. Y. Kitaev, “Unpaired Majorana fermions in quantum wires”, Physics-Uspekhi 44, 131 (2001). DOI; cond-mat/0010440
[24]
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
[25]
L. G. Gunderman, “Local-dimension-invariant qudit stabilizer codes”, Physical Review A 101, (2020). DOI; 1910.08122
[26]
Arun J. Moorthy and Lane G. Gunderman, “Local-dimension-invariant Calderbank-Shor-Steane Codes with an Improved Distance Promise”. 2110.11510
[27]
Lane G. Gunderman, “Degenerate Local-dimension-invariant Stabilizer Codes and an Alternative Bound for the Distance Preservation Condition”. 2110.15274

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.