## Description

## Protection

An \(((n,K,d))\) code corrects erasure errors on up to \(d-1\) qubits. The number of correctable errors is often called the decoding radius, and it is upper bounded by half of the code distance. As a result, qubit codes cannot tolerate adversarial errors on more than \((1-R)/4\) registers, where \(R = \log_2 K/n\) is the code rate.

### Pauli-string error basis

A convenient and often considered error set is the Pauli error or Pauli string basis.

Pauli strings: For a single qubit, this set consists of products of powers of the Pauli matrices \begin{align} X=\begin{pmatrix}0 & 1\\ 1 & 0 \end{pmatrix}\,\,\text{ and }\,\,Z=\begin{pmatrix}1 & 0\\ 0 & -1 \end{pmatrix}~. \tag*{(1)}\end{align} For multiple qubits, error set elements are tensor products of elements of the single-qubit error set.

The Pauli error set is a unitary and Hermitian basis for linear operators on the multi-qubit Hilbert space that is orthonormal under the Hilbert-Schmidt inner product; it is a prototypical nice error basis. The distance associated with this set is often the minimum weight of a Pauli string that implements a nontrivial logical operation in the code.

The minimum weight of a Pauli error that has a non-zero expectation value for some code basis state is called the diagonal distance [1]. Codes whose distance is greater than the diagonal distance are degenerate. Degenerate codes admit undetectable Pauli errors (i.e., errors whose projection into the codespace is nonzero) of weight less than the code distance (i.e., the projection satisfies the Knill-Laflamme conditions).

A quantum channel whose Kraus operators are Pauli strings is called a Pauli channel, and such channels are typically more tractable than general, non-Pauli channels. Relevant Pauli channels include dephasing noise and depolarizing noise (a.k.a. Werner-Holevo channel [2]), while relevant non-Pauli channels are amplitude damping, erasure (which maps all qubit states into a third state \(|e\rangle\) outside of the qubit Hilbert space), and biased erasure (in which case only the \(|1\rangle\) qubit state is mapped to \(|e\rangle\)). Noise can be correlated in space or in time, with the latter being an example of a non-Markovian phenomenon [3].

### Bounds on code parameters

Bounds on code performance include the quantum Singleton bound [4–6], quantum Hamming bound [7], and quantum Gilbert-Varshamov bound [7]. Linear programming bounds also exist [8,9].

Quantum weight enumerator: Determining protection and bounds on code parameters can also be done using the code's Shor-Laflamme quantum weight enumerator [10] (cf. weight enumerators) \begin{align} \begin{split} A(x)&=\sum_{j=0}^{n}A_{j}x^{j}\\ A_{j}&=\frac{1}{K^{2}}\sum_{\text{wt-}j\text{ Paulis }P}\left|\text{tr}(P\Pi)\right|^{2}~, \end{split} \tag*{(2)}\end{align} where \(\Pi\) is the code projection, and where the sum is over the Pauli group modulo the subgroup of phases (hence, the dagger below is necessary in case the coset representative is not Hermitian). The dual quantum weight enumerator is \begin{align} \begin{split} B(x)&=\sum_{j=0}^{n}B_{j}x^{j}\\ B_{j}&=\frac{1}{K}\sum_{\text{wt-}j\text{ Paulis }P}\text{tr}(P\Pi P^{\dagger}\Pi)~. \end{split} \tag*{(3)}\end{align} The weight enumerator and its dual satisfy the quantum MacWilliams identity [10]; see [11; Ch. 7]. The distance \(d\) of a code is the smallest \(j=d\) at which \(A_j \neq B_j\) [12]. Such a code is called pure if \(A_j = B_j = 0\) for all \(j < d\); otherwise, the code is called impure. Degeneracy is sufficient but not necessary for impurity [11]. Other types of quantum weight enumerators are the Rains shadow enumerators [8] (see also [13]). There are techniques to compute them for general codes [14]. These notions can be generalized to qudit codes and other error bases [14–16].

## Rate

## Gates

Clifford hierarchy: The Clifford hierarchy [40–42] is a tower of gate sets which includes Pauli and Clifford gates at its first two levels, and non-Clifford gates at higher levels. The \(k\)th level is defined recursively by \begin{align} C_k = \{ U | U P U^{\dagger} \in C_{k-1} \}~, \tag*{(4)}\end{align} where \(P\) is any Pauli matrix, and \(C_1\) is the Pauli group.

## Decoding

## Fault Tolerance

## Threshold

Computational threshold: A fault-tolerant computational threshold is the maximum noise rate in a noise model below which any logical computation of size \(M\) can be executed on a physical-qubit architecture to arbitrary accuracy and with an overhead of order \(O(M\text{polylog}M)\). The first methods to achieve a computational threshold use concatenated stabilizer codes [47–53]. Such methods require constant-space and polylogarithmic-time overhead, but concatentions using quantum Hamming codes improve this to quasi-polylogarithmic time [54]. Fault-tolerant computations with no notion of locality can be made local on a 2D or 3D geometry with minimial overhead [43].

Measurement threshold: One can derive conditions quantifying how many random single-qubit measurements can be made without destroying the logical information [55]. The measurement threshold is the maximum total probability that a single qubit is measured in a random \(X\), \(Y\), or \(Z\) basis at which the logical information is still recoverable. The measurement threshold is at least as large as the erasure threshold [55; Thm. 4].

## Notes

## Parents

- Modular-qudit code — Modular-qudit quantum codes for \(q=2\) correspond to qubit codes.
- Galois-qudit code — Galois-qudit quantum codes for \(q=2\) correspond to qubit codes.
- Spin code — Spin codes with spin \(\ell=1/2\) correspond to qubit codes.

## Children

- Dynamical automorphism (DA) code
- Haar-random qubit code
- Local Haar-random circuit qubit code
- Fermion code — The Majorana operator algebra is isomorphic to the qubit Pauli-operator algebra via various fermion-into-qubit encodings.
- Circuit-to-Hamiltonian approximate code
- Eigenstate thermalization hypothesis (ETH) code — ETH codewords are eigenstates of a local Hamiltonian whose eigenstates satisfy ETH.
- Jump code
- Movassagh-Ouyang Hamiltonian code
- Union stabilizer (USt) code
- XP stabilizer code
- PI qubit code
- Neural network code
- Cubic theory code
- Chen-Hsin invertible-order code

## Cousins

- Reed-Muller (RM) code — Optimizing T gates in a qubit circuit that uses CNOT and T gates is equivalent decoding a paricular RM code [29].
- Qubit c-q code — Qubit c-q codes are qubit codes designed to transmit classical information.
- EA qubit code — EA qubit codes utilize additional ancillary qubits in a pre-shared entangled state, but reduce to ordinary qubit codes when said qubits are interpreted as noiseless physical qubits.
- Five-qubit perfect code — Every \(((5,2,3))\) code is single-qubit-Clifford-equivalent to the five-qubit code [58; Corr. 10].
- Subsystem qubit code — Subsystem qubit codes reduce to (subspace) qubit codes when there is no gauge subsystem.

## References

- [1]
- U. S. Kapshikar, “The Diagonal Distance of CWS Codes”, (2021) arXiv:2107.11286
- [2]
- R. F. Werner and A. S. Holevo, “Counterexample to an additivity conjecture for output purity of quantum channels”, Journal of Mathematical Physics 43, 4353 (2002) arXiv:quant-ph/0203003 DOI
- [3]
- S. Milz and K. Modi, “Quantum Stochastic Processes and Quantum non-Markovian Phenomena”, PRX Quantum 2, (2021) arXiv:2012.01894 DOI
- [4]
- E. Knill, R. Laflamme, and L. Viola, “Theory of Quantum Error Correction for General Noise”, Physical Review Letters 84, 2525 (2000) arXiv:quant-ph/9604034 DOI
- [5]
- N. J. Cerf and R. Cleve, “Information-theoretic interpretation of quantum error-correcting codes”, Physical Review A 56, 1721 (1997) arXiv:quant-ph/9702031 DOI
- [6]
- E. M. Rains, “Nonbinary quantum codes”, (1997) arXiv:quant-ph/9703048
- [7]
- A. Ekert and C. Macchiavello, “Error Correction in Quantum Communication”, (1996) arXiv:quant-ph/9602022
- [8]
- E. M. Rains, “Quantum shadow enumerators”, (1997) arXiv:quant-ph/9611001
- [9]
- A. Ashikhmin and S. Litsyn, “Upper Bounds on the Size of Quantum Codes”, (1997) arXiv:quant-ph/9709049
- [10]
- P. Shor and R. Laflamme, “Quantum MacWilliams Identities”, (1996) arXiv:quant-ph/9610040
- [11]
- D. Gottesman. Surviving as a quantum computer in a classical world (2024) URL
- [12]
- A. Ashikhmin et al., “Quantum Error Detection I: Statement of the Problem”, (1999) arXiv:quant-ph/9906126
- [13]
- A. J. Scott, “Probabilities of Failure for Quantum Error Correction”, Quantum Information Processing 4, 399 (2005) arXiv:quant-ph/0406063 DOI
- [14]
- C. Cao et al., “Quantum Lego Expansion Pack: Enumerators from Tensor Networks”, (2024) arXiv:2308.05152
- [15]
- C. Hu, S. Yang, and S. S.-T. Yau, “Weight enumerators for nonbinary asymmetric quantum codes and their applications”, Advances in Applied Mathematics 121, 102085 (2020) DOI
- [16]
- C. Cao and B. Lackey, “Quantum weight enumerators and tensor networks”, (2023) arXiv:2211.02756
- [17]
- S. Pirandola et al., “Fundamental limits of repeaterless quantum communications”, Nature Communications 8, (2017) arXiv:1510.08863 DOI
- [18]
- P. Selinger, “Generators and relations for n-qubit Clifford operators”, Logical Methods in Computer Science Volume 11, Issue 2, (2015) arXiv:1310.6813 DOI
- [19]
- D. Gottesman, “The Heisenberg Representation of Quantum Computers”, (1998) arXiv:quant-ph/9807006
- [20]
- E. Knill, private communication, ca. 1998.
- [21]
- A. Barenco et al., “Elementary gates for quantum computation”, Physical Review A 52, 3457 (1995) arXiv:quant-ph/9503016 DOI
- [22]
- A. Y. Kitaev, “Quantum computations: algorithms and error correction”, Russian Mathematical Surveys 52, 1191 (1997) DOI
- [23]
- A. Kitaev, A. Shen, and M. Vyalyi, Classical and Quantum Computation (American Mathematical Society, 2002) DOI
- [24]
- C. M. Dawson and M. A. Nielsen, “The Solovay-Kitaev algorithm”, (2005) arXiv:quant-ph/0505030
- [25]
- “The Solovay–Kitaev theorem”, Quantum Computation and Quantum Information 617 (2012) DOI
- [26]
- J. van de Wetering and M. Amy, “Optimising T-count is NP-hard”, (2023) arXiv:2310.05958
- [27]
- M. Amy, D. Maslov, and M. Mosca, “Polynomial-Time T-Depth Optimization of Clifford+T Circuits Via Matroid Partitioning”, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 33, 1476 (2014) arXiv:1303.2042 DOI
- [28]
- D. Gosset et al., “An algorithm for the T-count”, (2013) arXiv:1308.4134
- [29]
- M. Amy and M. Mosca, “T-Count Optimization and Reed–Muller Codes”, IEEE Transactions on Information Theory 65, 4771 (2019) arXiv:1601.07363 DOI
- [30]
- Y. Nam et al., “Automated optimization of large quantum circuits with continuous parameters”, npj Quantum Information 4, (2018) arXiv:1710.07345 DOI
- [31]
- L. Heyfron and E. T. Campbell, “An Efficient Quantum Compiler that reduces \(T\) count”, (2018) arXiv:1712.01557
- [32]
- V. Gheorghiu, M. Mosca, and P. Mukhopadhyay, “T-count and T-depth of any multi-qubit unitary”, npj Quantum Information 8, (2022) arXiv:2110.10292 DOI
- [33]
- A. Kissinger and J. van de Wetering, “Reducing the number of non-Clifford gates in quantum circuits”, Physical Review A 102, (2020) arXiv:1903.10477 DOI
- [34]
- N. de Beaudrap, X. Bian, and Q. Wang, “Techniques to Reduce π/4-Parity-Phase Circuits, Motivated by the ZX Calculus”, Electronic Proceedings in Theoretical Computer Science 318, 131 (2020) arXiv:1911.09039 DOI
- [35]
- N. de Beaudrap, X. Bian, and Q. Wang, “Fast and effective techniques for T-count reduction via spider nest identities”, (2020) arXiv:2004.05164
- [36]
- A. Kissinger and J. van de Wetering, “Simulating quantum circuits with ZX-calculus reduced stabiliser decompositions”, Quantum Science and Technology 7, 044001 (2022) arXiv:2109.01076 DOI
- [37]
- F. J. R. Ruiz et al., “Quantum Circuit Optimization with AlphaTensor”, (2024) arXiv:2402.14396
- [38]
- Y. Shi, “Both Toffoli and Controlled-NOT need little help to do universal quantum computation”, (2002) arXiv:quant-ph/0205115
- [39]
- M. Möttönen et al., “Quantum Circuits for General Multiqubit Gates”, Physical Review Letters 93, (2004) arXiv:quant-ph/0404089 DOI
- [40]
- D. Gottesman and I. L. Chuang, “Demonstrating the viability of universal quantum computation using teleportation and single-qubit operations”, Nature 402, 390 (1999) arXiv:quant-ph/9908010 DOI
- [41]
- S. X. Cui, D. Gottesman, and A. Krishna, “Diagonal gates in the Clifford hierarchy”, Physical Review A 95, (2017) arXiv:1608.06596 DOI
- [42]
- N. Rengaswamy, R. Calderbank, and H. D. Pfister, “Unifying the Clifford hierarchy via symmetric matrices over rings”, Physical Review A 100, (2019) arXiv:1902.04022 DOI
- [43]
- S. H. Choe and R. Koenig, “How to fault-tolerantly realize any quantum circuit with local operations”, (2024) arXiv:2402.13863
- [44]
- E. Dennis et al., “Topological quantum memory”, Journal of Mathematical Physics 43, 4452 (2002) arXiv:quant-ph/0110143 DOI
- [45]
- O. Fawzi, A. Müller-Hermes, and A. Shayeghi, “A Lower Bound on the Space Overhead of Fault-Tolerant Quantum Computation”, (2022) arXiv:2202.00119 DOI
- [46]
- N. Baspin, O. Fawzi, and A. Shayeghi, “A lower bound on the overhead of quantum error correction in low dimensions”, (2023) arXiv:2302.04317
- [47]
- 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
- [48]
- 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
- [49]
- D. Gottesman, “Fault-tolerant quantum computation with local gates”, Journal of Modern Optics 47, 333 (2000) arXiv:quant-ph/9903099 DOI
- [50]
- D. Aharonov and M. Ben-Or, “Fault-Tolerant Quantum Computation With Constant Error Rate”, (1999) arXiv:quant-ph/9906129
- [51]
- K. M. Svore, B. M. Terhal, and D. P. DiVincenzo, “Local fault-tolerant quantum computation”, Physical Review A 72, (2005) arXiv:quant-ph/0410047 DOI
- [52]
- P. Aliferis, D. Gottesman, and J. Preskill, “Quantum accuracy threshold for concatenated distance-3 codes”, (2005) arXiv:quant-ph/0504218
- [53]
- K. M. Svore, D. P. DiVincenzo, and B. M. Terhal, “Noise Threshold for a Fault-Tolerant Two-Dimensional Lattice Architecture”, (2006) arXiv:quant-ph/0604090
- [54]
- H. Yamasaki and M. Koashi, “Time-Efficient Constant-Space-Overhead Fault-Tolerant Quantum Computation”, Nature Physics 20, 247 (2024) arXiv:2207.08826 DOI
- [55]
- D. Lee and B. Yoshida, “Randomly Monitored Quantum Codes”, (2024) arXiv:2402.00145
- [56]
- C. H. Bennett et al., “Mixed-state entanglement and quantum error correction”, Physical Review A 54, 3824 (1996) arXiv:quant-ph/9604024 DOI
- [57]
- S. Bravyi et al., “How much entanglement is needed for quantum error correction?”, (2024) arXiv:2405.01332
- [58]
- E. M. Rains, “Quantum codes of minimum distance two”, (1997) arXiv:quant-ph/9704043

## Page edit log

- Victor V. Albert (2023-01-08) — most recent
- Sam Gunn (2022-01-08)
- Victor V. Albert (2022-05-07)
- Victor V. Albert (2021-10-29)

## Cite as:

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