Glossary of concepts

Lifting
view in context →

Given the incidence matrix \(A\) of a protograph, each non-zero entry is replaced by a sum of \(\ell\)-dimensional permutation matrices while each zero entry is replaced by the \(\ell\)-dimensional zero matrix. The resulting matrix is called a lift of \(A\). The permutation matrices can be chosen randomly or deterministically, with a deterministic lift also called a permutation voltage assignment in the theory of theory of voltage graphs [1,2].

Cyclic-to-polynomial correspondence
view in context →

Cyclic linear \(q\)-ary codes and their properties can be naturally formulated using the theory of polynomials. Codewords \(c_1 c_2 \cdots c_n\) of a cyclic \(q\)-ary code can be thought of as coefficients in a polynomial \(c_1+c_2 x+\cdots+c_n x^{n-1}\) in the set of polynomials with \(q\)-ary coefficients, \(\mathbb{F}_q[x]\) with \(\mathbb{F}_q=GF(q)\). Polynomials corresponding to codewords of a linear cyclic code form an ideal (i.e., are closed under multiplication and addition) in the ring \(\mathbb{F}_q[x]/(x^n-1)\) (i.e., the set of equivalence classes of polynomials congruent modulo \(x^n-1\)). Multiplication of a codeword polynomial \(c(x)\) by \(x\) in such a ring corresponds to a cyclic shift of the corresponding codeword string.

Dicke states
view in context →

For \(n\)-qubit block codes, an often used basis for the \(n/2\)-dimensional permutation-invariant subspace consists of the Dicke states \(|D^n_w\rangle\) -- normalized permutation-invariant states \(w\) excitations, i.e., a normalized sum over all basis elements with \(w\) ones and \(n - w\) zeroes. Each Dicke state in the code can be shifted by adding a shift \(s\) to both \(n\) and \(w\).

Knill-Laflamme conditions
view in context →

The Knill-Laflamme error-correction conditions [3–5][6; Thm. 10.1] are necessary and sufficient conditions for a code to successfully correct a set of errors in a finite-dimensional Hilbert space. A code (defined by a partial isometry \(U\)) with code space projector \(\Pi = U U^\dagger\) can correct a set of errors \(\{ E_j \}\) if and only if \begin{align} \Pi E_i^\dagger E_j \Pi = c_{ij}\, \Pi\qquad\text{for all \(i,j\),} \tag*{(1)}\end{align} where \(c_{ij}\) can be arbitrary numbers.

Complementary channel
view in context →

A complementary channel \(\mathcal{E}^C\) is obtained from a channel \(\mathcal{E}\) that acts on a system by interpreting the channel as coming from a unitary operation acting on a larger system-environment tensor-product space (i.e., performing an isometric extension) and then tracing out the system factor (instead of the second environmental factor) [7; Sec. 5.2.2]. A noise channel \({\cal E}(\cdot)=\sum_{j}E_{j}(\cdot)E_{j}^{\dagger}\) admits a complementary channel of the form \begin{align} {\cal E}^{C}(\cdot)=\sum_{j,k}\text{Tr}\{E_{j}(\cdot)E_{k}^{\dagger}\}|j\rangle\langle k|~. \tag*{(2)}\end{align}

Pauli-to-polynomial mapping
view in context →

A single-qudit Pauli operator can be specified by the lattice coordinate of the site and the symplectic vector representation of the Pauli operator within the site. In an extension of the sympletic representation, each lattice coordinate can be represented by a Laurent monomial of \(D\) formal variables. For example, when \(D=2\) and \(m=1\), the product of an \(X\) acting on the qubit at lattice coordinate \((-1,2)\) and a \(Z\) acting on the qubit at \((1,0)\) can be represented by the vector \( (x^{-1} y^2 | x) \). The multiplicative group of finitely supported Pauli operators modulo phase factors on the lattice of dimension \(D\) with \(m\) prime-dimensional qubits per site is isomorphic to the additive group of Laurent polynomial column vectors of length \(2m\) in \(D\) formal variables (see Ref. [8] and Sec. IV of Ref. [9]).

BPT bound
view in context →

Lattice qubit codes are limited by the Bravyi-Poulin-Terhal (BPT) bound [10] (see also [11–13]), which states that \(d \leq O(n^{1-1/D})\) and \(k d^{2/D-1} = O(n)\) for \(D\)-dimensional lattice geometries. The Bravyi-Terhal (BT) bound states that \(d = O(L^{D-1})\) [11]. Codes on a \(D\)-dimensional homogeneous Riemannian manifold with diameter \(L\) satisfy \(k = O(L^{D-2})\) [14].

Bravyi-Koenig bound
view in context →

Logical gates implemented via constant-depth quantum circuits on a \(D\)-dimensional lattice stabilizer code whose distance increases with \(n\) lie in the \(D\)th level of the Clifford hierarchy [15]. A refinement can be made that expressed the bound in higher-group symmetries of the topological phases underlying the codes [16; Sec. 5.4.2].

Subsystem BT bound
view in context →

The subsystem BT bound is an upper bound of \(d = O(L^{D-1})\) on the distance [11] of lattice subsystem stabilizer codes arranged in a \(D\)-dimensional lattice of length \(L\) with \(n=L^D\). In particular, \(D=2\)-dimensional subsystem codes satisfy \(kd = O(n)\) [12]. More generally, there is a tradeoff theorem [17] stating that, for any logical operator, there is an equivalent logical operator with weight \(\tilde{d}\) such that \(\tilde{d}d^{1/(D-1)}=O(L^{D})\).

Clifford hierarchy
view in context →

The Clifford hierarchy [18–20] 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*{(3)}\end{align} where \(P\) is any Pauli matrix, and \(C_1\) is the Pauli group.

Computational threshold
view in context →

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

Measurement threshold
view in context →

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

Qubit CSS-to-homology correspondence
view in context →

CSS codes and their properties can be formulated in terms of homology theory, yielding a powerful correspondence between codes and chain complexes, the primary homological structures. There exists a many-to-one mapping from size three chain complexes to CSS codes [31–34] that allows one to extract code properties from topological features of the complexes. Codes constructed in this manner are sometimes called homological CSS codes, but they are equivalent to CSS codes. This mapping of codes to manifolds allows the application of structures from topology to error correction, yielding various QLDPC codes with favorable properties.

Binary symplectic representation
view in context →

In the binary symplectic representation, the single-qubit identity, \(X\), \(Y\), or \(Z\) Pauli matrices represented using two bits as \((0|0)\), \((1|0)\), \((1|1)\), and \((0|1)\), respectively. In other words, the single-qubit Pauli string \(X^a Z^b\) is converted to the vector \(a|b\). The multi-qubit version follows naturally.

\(GF(4)\) representation
view in context →

An \(n\)-qubit Pauli stabilizer can be represented as a length-\(n\) quaternary vector using the one-to-one correspondence between the four Pauli matrices \(\{I,X,Y,Z\}\) and the four elements \(\{0,1,\alpha^2,\alpha\}\) of the quaternary field \(GF(4)\).

Qudit Clifford hierarchy
view in context →

The modular-qudit Clifford hierarchy [18,19,35,36] is a tower of gate sets which includes modular-qudit Pauli and modular-qudit Clifford gates at its first two levels, and non-Clifford qudit 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 modular-qudit Pauli matrix, and \(C_1\) is the modular-qudit Pauli group.

Code switching, code deformation, or stabilizer update rule
view in context →

Code switching is a map between stabilizer codes that is done using a stabilizer group \(\mathsf{F}\) of the \(n\)-qudit Pauli group, \begin{align} \mathsf{S}\to\mathsf{N}_{\left\langle \mathsf{S},\mathsf{F}\right\rangle }\left(\mathsf{F}\right)~, \tag*{(5)}\end{align} where \(\mathsf{Z}\) denotes taking the center of a group (e.g., see [6,30] for proofs). Code switching may not preserve the logical information and instead implement logical measurements; conditions on \(\mathsf{S}\) and \(\mathsf{F}\) such that qubit stabilizer code switching preserves logical information are derived in [37; Prop. II.1]. Clifford operations and Pauli measurements can be expressed as sequences of code switching [38]. In the context of stabilizer codes realizing Abelian topological phases, code switching implements anyon condensation of any anyons represented by operators in the group \(\mathsf{F}\).

Gauge fixing
view in context →

Gauge fixing is a map between subsystem codes that is done using an Abelian subgroup \(\mathsf{F}\subseteq\mathsf{G}\), \begin{align} \begin{split} \mathsf{S}&\to\left\langle \mathsf{S},\mathsf{F}\right\rangle \\ \mathsf{G}&\to\mathsf{N}_{\mathsf{G}}\left(\mathsf{F}\right)~, \end{split} \tag*{(6)}\end{align} where \(\mathsf{N}_{\mathsf{G}}\left(\mathsf{F}\right)\) is the normalizer of the stabilizer group within \(\mathsf{G}\).

Gauging out
view in context →

Gauging out is a map between subsystem codes that is done using a subgroup \(\mathsf{F}\subseteq\mathsf{P}_n\), \begin{align} \begin{split} \mathsf{S}&\to\mathsf{Z}\left(\left\langle \mathsf{G},\mathsf{F}\right\rangle \right)\\ \mathsf{G}&\to\left\langle \mathsf{G},\mathsf{F}\right\rangle ~. \end{split} \tag*{(7)}\end{align} The stabilizer group of the output subsystem code is a subgroup of that of the input code, \(\mathsf{Z}\left(\left\langle \mathsf{G},\mathsf{F}\right\rangle \right)\subseteq\mathsf{Z}\left(\mathsf{G}\right)\). When \(\mathsf{F}\) is a subgroup of the logical Pauli group, this is also called gauging. If \(\mathsf{F}\) is itself a Pauli group of \(m\) logical qubits of the original subsystem code, then gauging those qubits is equivalent to treating them as gauge qubits.

Galois symplectic representation
view in context →

The single Galois-qudit Pauli string \(X_{a} Z_{b}\) for \(a,b\in GF(q)\) is converted to the vector \(a|b\). The multi Galois-qudit version follows naturally.

\(GF(q^2)\) representation
view in context →

An \(n\)-qubit Galois-qudit Pauli stabilizer can be represented as a length-\(n\) vector over \(GF(q^2)\) using the one-to-one correspondence between the \(q^2\) Galois-qudit Pauli matrices and elements of \(GF(q^2)\).

Weight reduction
view in context →

A related procedure called weight reduction [39] takes in a CSS stabilizer code and outputs another CSS code that admits a set of stabilizer generators whose weight is independent of the number of qubits \(n\).

References

[1]
C. A. Kelley and J. L. Walker, “LDPC codes from voltage graphs”, 2008 IEEE International Symposium on Information Theory (2008) DOI
[2]
L. W. Beineke et al., editors , Topics in Topological Graph Theory (Cambridge University Press, 2009) DOI
[3]
E. Knill and R. Laflamme, “Theory of quantum error-correcting codes”, Physical Review A 55, 900 (1997) DOI
[4]
C. H. Bennett et al., “Mixed-state entanglement and quantum error correction”, Physical Review A 54, 3824 (1996) arXiv:quant-ph/9604024 DOI
[5]
J. Preskill. Lecture notes on Quantum Computation. (1997–2020) URL
[6]
M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information (Cambridge University Press, 2012) DOI
[7]
M. M. Wilde, Quantum Information Theory (Cambridge University Press, 2013) DOI
[8]
J. Haah, “Algebraic Methods for Quantum Codes on Lattices”, Revista Colombiana de Matemáticas 50, 299 (2017) arXiv:1607.01387 DOI
[9]
J. Haah, L. Fidkowski, and M. B. Hastings, “Nontrivial Quantum Cellular Automata in Higher Dimensions”, Communications in Mathematical Physics 398, 469 (2022) arXiv:1812.01625 DOI
[10]
S. Bravyi, D. Poulin, and B. Terhal, “Tradeoffs for Reliable Quantum Information Storage in 2D Systems”, Physical Review Letters 104, (2010) arXiv:0909.5200 DOI
[11]
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) arXiv:0810.1983 DOI
[12]
S. Bravyi, “Subsystem codes with spatially local generators”, Physical Review A 83, (2011) arXiv:1008.1029 DOI
[13]
S. T. Flammia et al., “Limits on the storage of quantum information in a volume of space”, Quantum 1, 4 (2017) arXiv:1610.06169 DOI
[14]
J. Haah, “A degeneracy bound for homogeneous topological order”, SciPost Physics 10, (2021) arXiv:2009.13551 DOI
[15]
S. Bravyi and R. König, “Classification of Topologically Protected Gates for Local Stabilizer Codes”, Physical Review Letters 110, (2013) arXiv:1206.1609 DOI
[16]
M. Barkeshli et al., “Higher-group symmetry in finite gauge theory and stabilizer codes”, (2024) arXiv:2211.11764
[17]
J. Haah and J. Preskill, “Logical-operator tradeoff for local quantum codes”, Physical Review A 86, (2012) arXiv:1011.3529 DOI
[18]
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
[19]
S. X. Cui, D. Gottesman, and A. Krishna, “Diagonal gates in the Clifford hierarchy”, Physical Review A 95, (2017) arXiv:1608.06596 DOI
[20]
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
[21]
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
[22]
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
[23]
D. Gottesman, “Fault-tolerant quantum computation with local gates”, Journal of Modern Optics 47, 333 (2000) arXiv:quant-ph/9903099 DOI
[24]
D. Aharonov and M. Ben-Or, “Fault-Tolerant Quantum Computation With Constant Error Rate”, (1999) arXiv:quant-ph/9906129
[25]
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
[26]
P. Aliferis, D. Gottesman, and J. Preskill, “Quantum accuracy threshold for concatenated distance-3 codes”, (2005) arXiv:quant-ph/0504218
[27]
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
[28]
H. Yamasaki and M. Koashi, “Time-Efficient Constant-Space-Overhead Fault-Tolerant Quantum Computation”, Nature Physics 20, 247 (2024) arXiv:2207.08826 DOI
[29]
S. H. Choe and R. Koenig, “How to fault-tolerantly realize any quantum circuit with local operations”, (2024) arXiv:2402.13863
[30]
D. Lee and B. Yoshida, “Randomly Monitored Quantum Codes”, (2024) arXiv:2402.00145
[31]
A. Y. Kitaev, “Quantum computations: algorithms and error correction”, Russian Mathematical Surveys 52, 1191 (1997) DOI
[32]
H. Bombin and M. A. Martin-Delgado, “Homological error correction: Classical and quantum codes”, Journal of Mathematical Physics 48, (2007) arXiv:quant-ph/0605094 DOI
[33]
S. Bravyi and M. B. Hastings, “Homological Product Codes”, (2013) arXiv:1311.0885
[34]
N. P. Breuckmann, “PhD thesis: Homological Quantum Codes Beyond the Toric Code”, (2018) arXiv:1802.01520
[35]
M. Howard and J. Vala, “Qudit versions of the qubitπ/8gate”, Physical Review A 86, (2012) arXiv:1206.1598 DOI
[36]
F. Pastawski and B. Yoshida, “Fault-tolerant logical gates in quantum error-correcting codes”, Physical Review A 91, (2015) arXiv:1408.1720 DOI
[37]
D. Aasen et al., “Measurement Quantum Cellular Automata and Anomalies in Floquet Codes”, (2023) arXiv:2304.01277
[38]
M. E. Beverland, S. Huang, and V. Kliuchnikov, “Fault tolerance of stabilizer channels”, (2024) arXiv:2401.12017
[39]
M. B. Hastings, “Weight Reduction for Quantum Codes”, (2016) arXiv:1611.03790
  • Home
  • Code graph
  • Code lists
  • Concepts glossary
  • Search

Classical Domain

  • Binary Kingdom
  • Galois-field Kingdom
  • Matrix Kingdom
  • Analog Kingdom
  • Spherical Kingdom
  • Ring Kingdom
  • Group Kingdom

Quantum Domain

  • Qubit Kingdom
  • Modular-qudit Kingdom
  • Galois-qudit Kingdom
  • Bosonic Kingdom
  • Spin Kingdom
  • Group Kingdom
  • Category Kingdom

Classical-quantum Domain

  • Binary c-q Kingdom
  • Bosonic/analog c-q Kingdom

  • Add new code
  • Team
  • About

  • 🌒
≡
Error correction zoo by Victor V. Albert, Philippe Faist, and many contributors. This work is licensed under a CC-BY-SA License. See how to contribute.