Description
Encodes \(K\)-dimensional Hilbert space into a \(2^n\)-dimensional (i.e., \(n\)-qubit) Hilbert space. Usually denoted as \(((n,K))\) or \(((n,K,d))\), where \(d\) is the code's distance.
The qubit codes are equivalent if the codespace of one code can be mapped into that of the other under a tensor product of single-qubit unitary operations and a qubit permutation.
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. Tensor products of \(X\) (\(Z\)) Paulis acting on different qubits are called \(X\)-type (\(Z\)-type) Pauli strings. Combining the \(X\)-type and \(Z\)-type strings with \(i\) forms a group called the Pauli group on \(n\) qubits, while combining them with \(-1\) forms the real Pauli group.
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).
Noise channels
A quantum channel that admits a set of Pauli strings as its Kraus operators is called a Pauli channel, and such channels are typically more tractable than the more general, non-Pauli channels. Relevant Pauli channels include dephasing noise and depolarizing noise (a.k.a. Werner-Holevo channel [2]). Relevant non-Pauli channels are AD noise, 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,4].
Quantum weight enumerators
Quantum weight enumerator: Determining protection and bounds on code parameters can also be done using the code's Shor-Laflamme quantum weight enumerator [5] (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 [5]; see [6; Ch. 7]. It gives rise to quantum linear programming (LP) bounds [7,8]; see the book [6].
The distance \(d\) of a code is the smallest \(j=d\) at which \(A_j \neq B_j\) [9]. 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 [6].
Other types of quantum weight enumerators are the Rains unitary enumerators [10] and the Rains shadow enumerators [7] (see also [11]), with the latter related to Bell sampling [12]. These notions can be generalized to qudit codes and other error bases [13–15]. There are techniques to compute them for general codes [15]. Semidefinite programming (SDP) hierarchies and a quantum Delsarte bound have been developed [16].
Rate
Transversal Gates
Gates
Clifford group: The Clifford group is the normalizer of the Pauli group. The group consists of the Pauli group as well as elements that permute Pauli operators amongst themselves. Up to any phases and Pauli strings, the group is equivalent to the symplectic group \(Sp(2n,\mathbb{Z}_2)\). See Refs. [6,19–21] for generators, relations, and normal form. The group cannot be expressed as a semidirect product of the Pauli and symplectic groups [22]. There is a canonical form for Clifford circuits [23,24]. Restricting the group to real-valued elements yields the real Clifford group. Single-qubit Clifford gates, together with Paulis, realize a group with \(192\) elements. Modding out phases yields the \(48\)-element \(2O\) binary octahedral subgroup of \(SU(2)\). Further modding out the Pauli group, which corresponds to the quaternion group \(Q\), yields the permutation group \(S_3\), which consists of permutations of the three non-identity single-qubit Pauli matrices. Subgroups of the two-qubit Clifford group have been classified [25].
Clifford hierarchy: The Clifford hierarchy [48–51] 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, where \(C_1\) is the Pauli group, and where \(C_2\) is the Clifford group.
Decoding
Effective distance and hook errors: Decoders are characterized by an effective distance (a.k.a. circuit-level distance), the minimum number of faulty operations during syndrome measurement that is required to make an undetectable error. A code is distance-preserving if it admits a decoder whose circuit-level distance is equal to the code distance. A particularly dangerous class of syndrome measurement circuit faults are hook errors, which are faults that cause more than one data-qubit error [54]. Hook errors occur at specific places in a syndrome extraction circuit and can sometimes be removed by re-ordering the gates of the circuit. If not, the use of flag qubits (see [6]) to detect hook errors may be necessary to yield fault-tolerant decoders.
Fault Tolerance
Threshold
Computational threshold: A fault-tolerant computational threshold is the maximum noise rate in a particular single-parameter 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 recursively concatenated stabilizer code families [57–63]; such a threshold is called a concatenated threshold. Such methods require constant-space and polylogarithmic-time overhead, but concatenations using quantum Hamming codes improve this to quasi-polylogarithmic time [64]. Subsequently, thresholds were determined for infinite families of lattice stabilizer codes, starting with the toric code [54]; such a threshold is colloquially called a topological threshold. Fault-tolerant computations with no notion of locality can be made local on a 2D or 3D geometry with minimal overhead [52].
Measurement threshold: One can derive conditions quantifying how many random single-qubit measurements can be made without destroying the logical information [65]. 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 [65; Thm. 4].
Notes
Parents
- Operator-algebra (OA) qubit code — An OA qubit code which has no gauge qubits and no block structure is a qubit code.
- 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
- Conformal-field theory (CFT) code
- Kim-Preskill-Tang (KPT) 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
- Self-complementary quantum code
- Union stabilizer (USt) code
- XP stabilizer code
- PI qubit code
- Concatenated qubit code
- Neural network code
- Cubic theory code
- Chen-Hsin invertible-order code
Cousins
- Gray code — Gray codes are useful for optimizing qubit unitary circuits [68] and for encoding qudits in multiple qubits [69].
- Reed-Muller (RM) code — Optimizing T gates in a qubit circuit that uses CNOT and T gates is equivalent to decoding a particular RM code [36].
- 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.
- Hybrid qubit code — A hybrid qubit code storing no classical information reduces to a qubit code. Conversely, any qubit code can be converted into a hybrid qubit code by using some its qubits to store only classical information [70].
- Five-qubit perfect code — Every \(((5,2,3))\) code is single-qubit-Clifford-equivalent to the five-qubit code [71; 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]
- R. Klesse and S. Frank, “Quantum Error Correction in Spatially Correlated Quantum Noise”, Physical Review Letters 95, (2005) arXiv:quant-ph/0505153 DOI
- [4]
- S. Milz and K. Modi, “Quantum Stochastic Processes and Quantum non-Markovian Phenomena”, PRX Quantum 2, (2021) arXiv:2012.01894 DOI
- [5]
- P. Shor and R. Laflamme, “Quantum MacWilliams Identities”, (1996) arXiv:quant-ph/9610040
- [6]
- D. Gottesman. Surviving as a quantum computer in a classical world (2024) URL
- [7]
- E. M. Rains, “Quantum shadow enumerators”, (1997) arXiv:quant-ph/9611001
- [8]
- A. Ashikhmin and S. Litsyn, “Upper Bounds on the Size of Quantum Codes”, (1997) arXiv:quant-ph/9709049
- [9]
- A. Ashikhmin et al., “Quantum Error Detection I: Statement of the Problem”, (1999) arXiv:quant-ph/9906126
- [10]
- E. M. Rains, “Quantum Weight Enumerators”, (1996) arXiv:quant-ph/9612015
- [11]
- A. J. Scott, “Probabilities of Failure for Quantum Error Correction”, Quantum Information Processing 4, 399 (2005) arXiv:quant-ph/0406063 DOI
- [12]
- D. Miller et al., “Experimental measurement and a physical interpretation of quantum shadow enumerators”, (2024) arXiv:2408.16914
- [13]
- 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
- [14]
- C. Cao and B. Lackey, “Quantum weight enumerators and tensor networks”, (2023) arXiv:2211.02756
- [15]
- C. Cao et al., “Quantum Lego Expansion Pack: Enumerators from Tensor Networks”, (2024) arXiv:2308.05152
- [16]
- G. A. Munné, A. Nemec, and F. Huber, “SDP bounds on quantum codes”, (2024) arXiv:2408.10323
- [17]
- S. Pirandola et al., “Fundamental limits of repeaterless quantum communications”, Nature Communications 8, (2017) arXiv:1510.08863 DOI
- [18]
- E. T. Campbell and M. Howard, “Unified framework for magic state distillation and multiqubit gate synthesis with reduced resource cost”, Physical Review A 95, (2017) arXiv:1606.01904 DOI
- [19]
- J. Dehaene and B. De Moor, “Clifford group, stabilizer states, and linear and quadratic operations over GF(2)”, Physical Review A 68, (2003) arXiv:quant-ph/0304125 DOI
- [20]
- M. V. den Nest, “Classical simulation of quantum computation, the Gottesman-Knill theorem, and slightly beyond”, (2009) arXiv:0811.0898
- [21]
- P. Selinger, “Generators and relations for n-qubit Clifford operators”, Logical Methods in Computer Science Volume 11, Issue 2, (2015) arXiv:1310.6813 DOI
- [22]
- S. Burton, E. Durso-Sabina, and N. C. Brown, “Genons, Double Covers and Fault-tolerant Clifford Gates”, (2024) arXiv:2406.09951
- [23]
- S. Bravyi and D. Maslov, “Hadamard-Free Circuits Expose the Structure of the Clifford Group”, IEEE Transactions on Information Theory 67, 4546 (2021) arXiv:2003.09412 DOI
- [24]
- D. Ostrev, “Canonical Form and Finite Blocklength Bounds for Stabilizer Codes”, (2024) arXiv:2408.15202
- [25]
- E. Kubischta and I. Teixeira, “Classification of the Subgroups of the Two-Qubit Clifford Group”, (2024) arXiv:2409.14624
- [26]
- D. Gottesman, “The Heisenberg Representation of Quantum Computers”, (1998) arXiv:quant-ph/9807006
- [27]
- E. Knill, private communication, ca. 1998.
- [28]
- A. Barenco et al., “Elementary gates for quantum computation”, Physical Review A 52, 3457 (1995) arXiv:quant-ph/9503016 DOI
- [29]
- A. Y. Kitaev, “Quantum computations: algorithms and error correction”, Russian Mathematical Surveys 52, 1191 (1997) DOI
- [30]
- A. Kitaev, A. Shen, and M. Vyalyi, Classical and Quantum Computation (American Mathematical Society, 2002) DOI
- [31]
- C. M. Dawson and M. A. Nielsen, “The Solovay-Kitaev algorithm”, (2005) arXiv:quant-ph/0505030
- [32]
- “The Solovay–Kitaev theorem”, Quantum Computation and Quantum Information 617 (2012) DOI
- [33]
- J. van de Wetering and M. Amy, “Optimising quantum circuits is generally hard”, (2024) arXiv:2310.05958
- [34]
- 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
- [35]
- D. Gosset et al., “An algorithm for the T-count”, (2013) arXiv:1308.4134
- [36]
- M. Amy and M. Mosca, “T-Count Optimization and Reed–Muller Codes”, IEEE Transactions on Information Theory 65, 4771 (2019) arXiv:1601.07363 DOI
- [37]
- Y. Nam et al., “Automated optimization of large quantum circuits with continuous parameters”, npj Quantum Information 4, (2018) arXiv:1710.07345 DOI
- [38]
- L. Heyfron and E. T. Campbell, “An Efficient Quantum Compiler that reduces \(T\) count”, (2018) arXiv:1712.01557
- [39]
- 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
- [40]
- 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
- [41]
- 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
- [42]
- N. de Beaudrap, X. Bian, and Q. Wang, “Fast and Effective Techniques for T-Count Reduction via Spider Nest Identities”, (2020) arXiv:2004.05164 DOI
- [43]
- 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
- [44]
- F. J. R. Ruiz et al., “Quantum Circuit Optimization with AlphaTensor”, (2024) arXiv:2402.14396
- [45]
- Y. Shi, “Both Toffoli and Controlled-NOT need little help to do universal quantum computation”, (2002) arXiv:quant-ph/0205115
- [46]
- M. Möttönen et al., “Quantum Circuits for General Multiqubit Gates”, Physical Review Letters 93, (2004) arXiv:quant-ph/0404089 DOI
- [47]
- M. B. Hastings, “Turning Gate Synthesis Errors into Incoherent Errors”, (2016) arXiv:1612.01011
- [48]
- 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
- [49]
- S. X. Cui, D. Gottesman, and A. Krishna, “Diagonal gates in the Clifford hierarchy”, Physical Review A 95, (2017) arXiv:1608.06596 DOI
- [50]
- 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
- [51]
- J. T. Anderson, “On Groups in the Qubit Clifford Hierarchy”, Quantum 8, 1370 (2024) arXiv:2212.05398 DOI
- [52]
- S. H. Choe and R. Koenig, “How to fault-tolerantly realize any quantum circuit with local operations”, (2024) arXiv:2402.13863
- [53]
- E. Kubischta and I. Teixeira, “Flexible Fault Tolerant Gate Gadgets”, (2024) arXiv:2409.11616
- [54]
- E. Dennis et al., “Topological quantum memory”, Journal of Mathematical Physics 43, 4452 (2002) arXiv:quant-ph/0110143 DOI
- [55]
- 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
- [56]
- N. Baspin, O. Fawzi, and A. Shayeghi, “A lower bound on the overhead of quantum error correction in low dimensions”, (2023) arXiv:2302.04317
- [57]
- 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
- [58]
- 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
- [59]
- D. Gottesman, “Fault-tolerant quantum computation with local gates”, Journal of Modern Optics 47, 333 (2000) arXiv:quant-ph/9903099 DOI
- [60]
- D. Aharonov and M. Ben-Or, “Fault-Tolerant Quantum Computation With Constant Error Rate”, (1999) arXiv:quant-ph/9906129
- [61]
- 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
- [62]
- P. Aliferis, D. Gottesman, and J. Preskill, “Quantum accuracy threshold for concatenated distance-3 codes”, (2005) arXiv:quant-ph/0504218
- [63]
- 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
- [64]
- H. Yamasaki and M. Koashi, “Time-Efficient Constant-Space-Overhead Fault-Tolerant Quantum Computation”, Nature Physics 20, 247 (2024) arXiv:2207.08826 DOI
- [65]
- D. Lee and B. Yoshida, “Randomly Monitored Quantum Codes”, (2024) arXiv:2402.00145
- [66]
- C. H. Bennett et al., “Mixed-state entanglement and quantum error correction”, Physical Review A 54, 3824 (1996) arXiv:quant-ph/9604024 DOI
- [67]
- S. Bravyi et al., “How much entanglement is needed for quantum error correction?”, (2024) arXiv:2405.01332
- [68]
- J. J. Vartiainen, M. Möttönen, and M. M. Salomaa, “Efficient Decomposition of Quantum Gates”, Physical Review Letters 92, (2004) arXiv:quant-ph/0312218 DOI
- [69]
- N. P. D. Sawaya et al., “Resource-efficient digital quantum simulation of d-level systems for photonic, vibrational, and spin-s Hamiltonians”, npj Quantum Information 6, (2020) arXiv:1909.12847 DOI
- [70]
- I. Kremsky, M.-H. Hsieh, and T. A. Brun, “Classical enhancement of quantum-error-correcting codes”, Physical Review A 78, (2008) arXiv:0802.2414 DOI
- [71]
- 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