Qubit code 

Also known as Qubit subspace code.
Root code for the Qubit Kingdom

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.

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

Noise channels

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]). 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 shadow enumerators [7] (see also [10]). There are techniques to compute them for general codes [11]. These notions can be generalized to qudit codes and other error bases [11–13].

Rate

Exact two-way assisted capacities have been obtained for the erasure and dephasing channels [14].

Transversal Gates

A qubit code is \(U\)-quasi-transversal if it can realize the logical gate \(U\) in the third level of the Clifford hierarchy using the physical gate \(C T^{\otimes n}\), where \(C\) is some Clifford gate [15; Def. 4].

Gates

The normalizer of the Pauli group is the Clifford group; see Ref. [16] for generators, relations, and normal form. The Clifford group permutes Pauli operators amongst themselves, and, up to any phases, is equivalent to the symplectic group \(Sp(2n,\mathbb{Z}_2)\). The combined Pauli and Clifford group cannot be expressed as a semidirect product of those two constituents [17].Computing using Clifford gates only can be efficiently simulated on a classical computer, according to the Gottesman-Knill theorem [18,19]. Universal quantum computing can be achieved using Clifford gates and a single type of non-Clifford gate, such as the \(T\) gate [20]. More generally, the Solovay-Kitaev theorem [21,22] states that any subset of gates the generates a dense subgroup of the full \(n\)-qubit gate group can be used to construct any gate to arbitrary accuracy (see [23][24; Appx. 3]). The task of approximating a desired gate by Clifford gates and a fixed set of non-Clifford gates is called gate compilation or circuit synthesis.Non-Clifford gates are typically more difficult to implement than Clifford gates and so are treated as a resource. Optimizing T-gate count in circuit synthesis is \(NP\)-hard [25] and can be done using various procedures [26–31], e.g., ZX calculus (a.k.a. Penrose spin calculus) [32–35] or reinforcement learning [36]. Decompositions in terms of Toffoli and Hadamard gates [37] as well as cosine-sine gates also exist [38]. Gate errors in circuit synthesis can sometimes add up destructively [39].

Clifford hierarchy: The Clifford hierarchy [40–43] 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.

Arbitrary \(n\)-qubit circuits can be implemented fault-tolerantly in a 3D architecture using \(O(n^{3/2}\log^3 n)\) qubits, and in a 2D architecture using only \(O(n^2 \log^3 n)\) qubits [44].

Decoding

Incorporating faulty syndrome measurements can be done using the phenomenological noise model, which simulates errors during syndrome extraction by flipping some of the bits of the measured syndrome bit string. In the more involved circuit-level noise model, every component of the syndrome extraction circuit can be faulty.Hook errors are syndrome measurement circuit faults that cause more than one data-qubit error [45]. 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 to detect hook errors may be necessary to yield fault-tolerant decoders.The decoder determining the most likely error given a noise channel is called the maximum probability error (MPE) decoder. For few-qubit codes (\(n\) is small), MPE decoding can be based by creating a lookup table. For infinite code families, the size of such a table scales exponentially with \(n\), so approximate decoding algorithms scaling polynomially with \(n\) have to be used.Decoders are characterized by an effective distance or 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.

Fault Tolerance

There are lower bounds on the overhead of fault-tolerant QEC in terms of the capacity of the noise channel [46]. A more stringent bound applies to geometrically local QEC due to the fact that locality constrains the growth of the entanglement that is needed for protection [47].Arbitrary \(n\)-qubit circuits can be implemented fault-tolerantly in a 3D architecture using \(O(n^{3/2}\log^3 n)\) qubits, and in a 2D architecture using only \(O(n^2 \log^3 n)\) qubits [44].

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 [48–54]. Such methods require constant-space and polylogarithmic-time overhead, but concatentions using quantum Hamming codes improve this to quasi-polylogarithmic time [55]. Fault-tolerant computations with no notion of locality can be made local on a 2D or 3D geometry with minimial overhead [44].

Measurement threshold: One can derive conditions quantifying how many random single-qubit measurements can be made without destroying the logical information [56]. 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 [56; Thm. 4].

Notes

There is a relation between one-way entanglement distillation protocols and QECCs [57].See Qiskit QEC framework for realizing protocols on IBM machines.There exists a distance- and rate-dependent lower bound on the degree of entanglement of a qubit code [58; Thm. 3i].

Parents

Children

Cousins

  • Gray code — Gray codes are useful for optimizing qubit unitary circuits [59] and for encoding qudits in multiple qubits [60].
  • Reed-Muller (RM) code — Optimizing T gates in a qubit circuit that uses CNOT and T gates is equivalent decoding a paricular RM code [28].
  • 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 [61].
  • Five-qubit perfect code — Every \(((5,2,3))\) code is single-qubit-Clifford-equivalent to the five-qubit code [62; 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]
A. J. Scott, “Probabilities of Failure for Quantum Error Correction”, Quantum Information Processing 4, 399 (2005) arXiv:quant-ph/0406063 DOI
[11]
C. Cao et al., “Quantum Lego Expansion Pack: Enumerators from Tensor Networks”, (2024) arXiv:2308.05152
[12]
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
[13]
C. Cao and B. Lackey, “Quantum weight enumerators and tensor networks”, (2023) arXiv:2211.02756
[14]
S. Pirandola et al., “Fundamental limits of repeaterless quantum communications”, Nature Communications 8, (2017) arXiv:1510.08863 DOI
[15]
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
[16]
P. Selinger, “Generators and relations for n-qubit Clifford operators”, Logical Methods in Computer Science Volume 11, Issue 2, (2015) arXiv:1310.6813 DOI
[17]
S. Burton, E. Durso-Sabina, and N. C. Brown, “Genons, Double Covers and Fault-tolerant Clifford Gates”, (2024) arXiv:2406.09951
[18]
D. Gottesman, “The Heisenberg Representation of Quantum Computers”, (1998) arXiv:quant-ph/9807006
[19]
E. Knill, private communication, ca. 1998.
[20]
A. Barenco et al., “Elementary gates for quantum computation”, Physical Review A 52, 3457 (1995) arXiv:quant-ph/9503016 DOI
[21]
A. Y. Kitaev, “Quantum computations: algorithms and error correction”, Russian Mathematical Surveys 52, 1191 (1997) DOI
[22]
A. Kitaev, A. Shen, and M. Vyalyi, Classical and Quantum Computation (American Mathematical Society, 2002) DOI
[23]
C. M. Dawson and M. A. Nielsen, “The Solovay-Kitaev algorithm”, (2005) arXiv:quant-ph/0505030
[24]
“The Solovay–Kitaev theorem”, Quantum Computation and Quantum Information 617 (2012) DOI
[25]
J. van de Wetering and M. Amy, “Optimising T-count is NP-hard”, (2023) arXiv:2310.05958
[26]
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
[27]
D. Gosset et al., “An algorithm for the T-count”, (2013) arXiv:1308.4134
[28]
M. Amy and M. Mosca, “T-Count Optimization and Reed–Muller Codes”, IEEE Transactions on Information Theory 65, 4771 (2019) arXiv:1601.07363 DOI
[29]
Y. Nam et al., “Automated optimization of large quantum circuits with continuous parameters”, npj Quantum Information 4, (2018) arXiv:1710.07345 DOI
[30]
L. Heyfron and E. T. Campbell, “An Efficient Quantum Compiler that reduces \(T\) count”, (2018) arXiv:1712.01557
[31]
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
[32]
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
[33]
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
[34]
N. de Beaudrap, X. Bian, and Q. Wang, “Fast and effective techniques for T-count reduction via spider nest identities”, (2020) arXiv:2004.05164
[35]
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
[36]
F. J. R. Ruiz et al., “Quantum Circuit Optimization with AlphaTensor”, (2024) arXiv:2402.14396
[37]
Y. Shi, “Both Toffoli and Controlled-NOT need little help to do universal quantum computation”, (2002) arXiv:quant-ph/0205115
[38]
M. Möttönen et al., “Quantum Circuits for General Multiqubit Gates”, Physical Review Letters 93, (2004) arXiv:quant-ph/0404089 DOI
[39]
M. B. Hastings, “Turning Gate Synthesis Errors into Incoherent Errors”, (2016) arXiv:1612.01011
[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]
J. T. Anderson, “On Groups in the Qubit Clifford Hierarchy”, Quantum 8, 1370 (2024) arXiv:2212.05398 DOI
[44]
S. H. Choe and R. Koenig, “How to fault-tolerantly realize any quantum circuit with local operations”, (2024) arXiv:2402.13863
[45]
E. Dennis et al., “Topological quantum memory”, Journal of Mathematical Physics 43, 4452 (2002) arXiv:quant-ph/0110143 DOI
[46]
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
[47]
N. Baspin, O. Fawzi, and A. Shayeghi, “A lower bound on the overhead of quantum error correction in low dimensions”, (2023) arXiv:2302.04317
[48]
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
[49]
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
[50]
D. Gottesman, “Fault-tolerant quantum computation with local gates”, Journal of Modern Optics 47, 333 (2000) arXiv:quant-ph/9903099 DOI
[51]
D. Aharonov and M. Ben-Or, “Fault-Tolerant Quantum Computation With Constant Error Rate”, (1999) arXiv:quant-ph/9906129
[52]
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
[53]
P. Aliferis, D. Gottesman, and J. Preskill, “Quantum accuracy threshold for concatenated distance-3 codes”, (2005) arXiv:quant-ph/0504218
[54]
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
[55]
H. Yamasaki and M. Koashi, “Time-Efficient Constant-Space-Overhead Fault-Tolerant Quantum Computation”, Nature Physics 20, 247 (2024) arXiv:2207.08826 DOI
[56]
D. Lee and B. Yoshida, “Randomly Monitored Quantum Codes”, (2024) arXiv:2402.00145
[57]
C. H. Bennett et al., “Mixed-state entanglement and quantum error correction”, Physical Review A 54, 3824 (1996) arXiv:quant-ph/9604024 DOI
[58]
S. Bravyi et al., “How much entanglement is needed for quantum error correction?”, (2024) arXiv:2405.01332
[59]
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
[60]
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
[61]
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
[62]
E. M. Rains, “Quantum codes of minimum distance two”, (1997) arXiv:quant-ph/9704043
Page edit log

Your contribution is welcome!

on github.com (edit & pull request)— see instructions

edit on this site

Zoo Code ID: qubits_into_qubits

Cite as:
“Qubit code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023. https://errorcorrectionzoo.org/c/qubits_into_qubits
BibTeX:
@incollection{eczoo_qubits_into_qubits, title={Qubit code}, booktitle={The Error Correction Zoo}, year={2023}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/qubits_into_qubits} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/qubits_into_qubits

Cite as:

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

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/quantum/qubits/qubits_into_qubits.yml.