Glossary of concepts

Construction A

view in context →

Construction \(A\) converts a linear binary code into a sphere packing. Each binary codeword \(c\) of the code is mapped to an infinite set of points \(x\) such that \(x = c\) modulo two. If the underlying binary code is linear, then the resulting set of points forms a lattice.

Finite fields

view in context →

The most common alphabets used in block codes Galois or finite fields \(GF(q)=\mathbb{F}_q\), which are sets of \(q\) elements closed under addition and multiplication. They are finite analogues of the real or complex numbers, and a unique field exists for every power \(q=p^m\) of a prime \(p\). The prime-field case reduces to \(\mathbb{Z}_p\), a group under addition that is promoted to a field by defining multiplication modulo \(p\); the case \(p=2\) yields the binary field \(\mathbb{Z}_2\). Every finite field comes with a 0 element (additive identity), a 1 element (multiplicative identity), and additive (multiplicative) inverses for all (nonzero) elements. An element whose powers exhaust all nonzero field elements is called primitive. Fields come with a trace operation, the field trace, which maps elements \(\gamma \in GF(q)\) to elements of \(GF(p)\) as \begin{align} \text{tr}(\gamma)=\sum_{k=0}^{m-1}\gamma^{p^{k}}~. \tag*{(1)}\end{align} The field trace can be thought of as an averaging over the field's Galois group, which is the cyclic group generated by \(\gamma\to\gamma^p\) [1; pg. 113]. Fields also come with a field norm, \begin{align} N(\gamma)=\prod_{k=0}^{m-1}\gamma^{p^{k}}=\gamma^{(p^{m}-1)/(p-1)}~. \tag*{(2)}\end{align} In the case of the complex numbers, analogues of the field trace and field norm are the real part and norm squared of a complex number, respectively.

Any field \(GF(q)\) can be thought of as an \(m\)-dimensional vector space over \(GF(p)\) a.k.a. the \(m\)th extension of \(GF(p)\) (similar to the complex numbers being an extension of the reals). Conversely, \(GF(p)\) is an example of a subfield of \(GF(q)\). Certain field elements are chosen to be the basis of \(GF(q)\) over \(GF(p)\), and all other elements are expressed as linear combinations of these basis elements. More generally, elements of fields such as \(GF(p^{ml})\) can be written as \(m\)-dimensional vectors over \(GF(p^l)\) or \((m\times l)\)-dimensional matrices over \(GF(p)\). This idea is used to convert between ordinary block codes and matrix-based codes such as disk array codes and rank-metric codes. The field norm and field trace can likewise be defined for fields \(GF(q^m)\) that are extensions of \(GF(q)\) for non-prime \(q\).

Asymptotic notation

view in context →

We are often interested in how parameters of particular infinite block-code families scale with increasing block length \(n\), necessitating the use of asymptotic or Bachmann–Landau notation; see the book [2]. The table below summarizes the notation used throughout the EC Zoo for relating functions \(f,g\) that both grow with \(n\).

relation	behavior
\(f(n)=O(g(n))\)	\(\phantom{c_{2}\geq}{\displaystyle \underset{n\to\infty}{\lim}\frac{|f(n)|}{|g(n)|}}\leq c\)
\(f(n)=\Omega(g(n))\)	\(0<{\displaystyle \underset{n\to\infty}{\lim}\frac{|f(n)|}{|g(n)|}}\phantom{\leq c_{2}}\)
\(f(n)=\Theta(g(n))\)	\(c_{1}\leq{\displaystyle \underset{n\to\infty}{\lim}\frac{|f(n)|}{|g(n)|}}\leq c_{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.

Weight enumerator

view in context →

Determining protection and bounds on code parameters can also be done using the code's weight enumerator (cf. quantum weight enumerators), \begin{align} \begin{split} A(x,y)&=\sum_{j=0}^{n}A_{j}x^{n-j}y^{j}\\ A_{j}&=\text{number of wt-}j\text{ codewords}~. \end{split} \tag*{(3)}\end{align} The weight enumerator and it's Fourier transform the dual weight enumerator satisfy the MacWilliams identity [3,4]; see [1; Ch. 5].

The distance of the code is the value of the first nonzero coefficient \(A_j\), while the dual distance is the first nonzero coefficient of the dual weight enumerator. The number of the code is the number of nonzero \(A_j\)'s, corresponding to the number of distinct nonzero distances between codewords. The external distance is the number of nonzero coefficients of the dual weight enumerator. The distance, dual distance, number and external distance make up the four fundamental parameters of a code [5][1; Ch. 5].

Other types of weight enumerators includes the Hamming weight enumerator, Lee weight enumerator, joint weight enumerator, split weight enumerator, and biweight enumerator [1].

Gilbert-Varshamov (GV) bound

view in context →

The Gilbert-Varshamov [6,7], or Gilbert-Shannon-Varshamov, bound states that the maximum size \(K\) of a \(q\)-ary code with distance \(d\) satisfies \begin{align} K\sum_{j=0}^{d-1}{n \choose j}(q-1)^{j}\geq q^{n}~. \tag*{(4)}\end{align} In other words, if the left-hand side of the above is less than or equal to the right-hand side, then a code with such parameters exists. The GV bound gives rise to the asymptotic GV bound (i.e., GV bound in the \(n\to\infty\) limit), expressed in terms of the maximum achievable rate \(R\) and relative distance \(\delta\), \begin{align} R\geq 1-h_{q}(\delta)~, \tag*{(5)}\end{align} where \(h_q\) is the \(q\)-ary entropy function, \begin{align} h_{q}(\delta)=-\delta\log_{q}\frac{\delta}{q-1}-(1-\delta)\log_{q}(1-\delta)~. \tag*{(6)}\end{align}

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 [8,9].

The matrices can come from a group \(G\) or its group algebra \(\mathbb{F}_q G\), in which case the lift is often called a \(G\)-lift. In this case, matrix entries of a \(\mathbb{F}_q\)-valued matrix \(A\) are substitited with matrices forming the regular representation of \(\mathbb{F}_q G\) according to some rule.

For example, the lift of a binary two-dimensional incidence matrix using two-dimensional permutation matrices associated with the group \(\mathbb{Z}_2\) is as follows: \begin{align} \begin{pmatrix}1 & 1\\ 0 & 1 \end{pmatrix}\to\left(\begin{smallmatrix}0 & 1 & 0 & 1\\ 1 & 0 & 1 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1 \end{smallmatrix}\right)~. \tag*{(7)}\end{align} Here, the two non-zero entries in the top row are replaced by the exchange permutation while the bottom non-zero entry is replaced by the trivial permutation.

Antipodal mapping

view in context →

The antipodal mapping, also known as a Euclidean-space image or \(Y_2\) construction), is a component-wise mapping from binary space into Euclidean space. Each coodinate of a binary string is mapped into a sign, \(0\to +1\) and \(1 \to -1\) [10; Example 1.2.1].

Group-based error basis

view in context →

There are two types of \(X\)-type operators, corresponding to left and right group multiplication. These act on computational basis states \(|h\rangle\) as \begin{align} \overrightarrow{X}_{g}|h\rangle&=|gh\rangle\tag*{(8)}\\ \overleftarrow{X}_{g}|h\rangle&=|hg^{-1}\rangle \tag*{(9)}\end{align} for any group elements \(h,g\). The \(Z\)-type operators can be thought of as matrix-product operators (MPOs) [11] whose virtual dimension is the dimension \(d_{\lambda}\) of their corresponding irrep. The are diagonal in the group-valued basis, yielding the \(d_{\lambda}\)-dimensional irrep matrix \(Z_{\lambda}(g)\) evaluated at the given group element, \begin{align} \hat{Z}_{\lambda}\otimes|g\rangle=Z_{\lambda}(g)\otimes|g\rangle~. \tag*{(10)}\end{align} Each matrix element of this irrep matrix is a generally non-unitary operator on the group-valued qudit. For one-dimensional irreps, the matrix reduces to a single unitary \(Z\)-type operator, and the direct-product symbol is no longer needed.

Rotor generalized Pauli strings

view in context →

For a single rotor, its elements are products of exponentials of the rotor's angular position (\(\hat\phi\)) and angular momentum (\(\hat L\)) operators, acting on the rotor's angular position states \(|\phi\rangle\) for \(\phi\in U(1)\) as \begin{align} e^{-i\varphi\hat{L}}\left|\phi\right\rangle =\left|\phi+\varphi\right\rangle \,\,\text{ and }\,\,e^{i\ell\hat{\phi}}\left|\phi\right\rangle =e^{i\ell\phi}\left|\phi\right\rangle ~, \tag*{(11)}\end{align} where \(\varphi\in U(1)\) and \(\ell\in\mathbb{Z}\). For multiple rotors, error set elements are tensor products of elements of the single-rotor error set, characterized by vectors of angle and integer coefficients multiplying vectors of angular momentum \(\hat{\boldsymbol{L}}\) and angular position \(\hat{\boldsymbol{\phi}}\) operators.

Displacement operators

view in context →

For a single mode, its elements are products of exponentials of the mode's position and momentum operators, acting on the mode's position states \(|y\rangle\) for \(y\in\mathbb{R}\) as \begin{align} e^{-iq\hat{p}}\left|y\right\rangle =\left|y+q\right\rangle \,\,\text{ and }\,\,e^{iq\hat{x}}\left|y\right\rangle =e^{iq y}\left|y\right\rangle ~, \tag*{(12)}\end{align} where \(q\in\mathbb{R}\). The former is also called a translation, while the latter is called a modulation in signal processing. For multiple modes, error set elements are tensor products of elements of the single-oscillator error set, characterized by the vector of coefficients \(\xi\in\mathbb{R}^{2n}\).

Code space complexity

view in context →

One can relate robustness of an approximate quantum code to the quantum circuit complexity [12–15] of creating states in the codespace. For a family of block codes, scaling as order \(O(k/n)\) of a code parameter called the subsystem variance characterizes the transition between code subspaces with low and high circuit complexity [16].

Amplitude damping noise

view in context →

The amplitude damping (AD) channel is a bosonic channel that models loss of particles in a bosonic mode (a.k.a. photon loss, pure loss, or fiber attenuation). Its Kraus operators are proportional to powers of a mode's annihilation operator \(a\), with the power signifying the number of particles lost during the error, \begin{align} E_{\ell}=\left(\frac{\gamma}{1-\gamma}\right)^{\ell/2}\frac{a^{\ell}}{\sqrt{\ell!}}\left(1-\gamma\right)^{\hat{n}/2}\,, \tag*{(13)}\end{align} where \(\gamma\in[0,1)\) is the noise rate [17,18]. For multiple modes, error set elements are tensor products of elements of the single-mode error set.

Restricting the channel to the first two Fock states \(\{|0\rangle,|1\rangle\}\) yields the non-Pauli qubit AD channel, which requires protecting against the loss error \(E_1\propto X+iY\) (instead of \(X\) and \(Y\) Pauli errors individually). Both channels are called AD since the context makes clear which one is being referred to. Other extension to qudits are also known [19].

Quantum GV bound

view in context →

The quantum GV bound [20] (see also Refs. [21–24]) for Galois qudits states that a pure \([[n,k,d]]_q\) Galois-qudit stabilizer code exists if \begin{align} \frac{q^{n-k+2}-1}{q^{2}-1}>\sum_{j=1}^{d-1}(q^{2}-1)^{j-1}\binom{n}{j}~. \tag*{(14)}\end{align} The quantum GV bound gives rise to the asymptotic quantum GV bound (i.e., quantum GV bound in the \(n\to\infty\) limit), expressed in terms of the maximum achievable rate \(R\) and relative distance \(\delta\), \begin{align} R\geq 1-\delta\log_q(q+1) - h_{q}(\delta)~, \tag*{(15)}\end{align} where \(h_q\) is the \(q\)-ary entropy function.

Eastin-Knill theorem

view in context →

Transversal gates are logical gates on block codes that can be realized as tensor products of unitary operations acting on subsets of subsystems whose size is independent of \(n\). For subsets of size one, gates are sometimes called strongly transversal the single-subsystem unitaries are identical and weakly transversal otherwise. A universal gate set for a finite-dimensional block quantum code cannot be transversal for any code that detects single-block errors due to the Eastin-Knill theorem [25].

Absolutely maximally entangled (AME) state

view in context →

A state on \(n\) subsystems is \(d\)-uniform [26,27] (a.k.a. \(d\)-undetermined [28] or \(d\)-maximally mixed [29]) if all reduced density matrices on up to \(d\) subsystems are maximally mixed. A \(K\)-dimensional subspace of \(d-1\)-uniform states of \(q\)-dimensional subsystems is equivalent to a pure \(((n,K,d))_q\) code [30,31]. An AME state (a.k.a. maximally multi-partite entangled state [32,33]) is a \(\lfloor n/2 \rfloor\)-uniform state, corresponding to a pure \(((n,1,\lfloor n/2 \rfloor + 1))_{\mathbb{Z}_q}\) code. The rank-\(n\) tensor formed by the encoding isometry of such codes is a perfect tensor (a.k.a. multi-unitary tensor), meaning that it is proportional to an isometry for any bipartition of its indices into a set \(A\) and a complementary set \(A^{\perp}\) such that \(|A|\leq|A^{\perp}|\).

TQO conditions

view in context →

The TQO-1 condition states that the distance of the ground-state-subspace code is macroscopic, i.e., grows as a positive power of the lattice size [34]. The TQO-2 condition relates the ground states of restrictions of the Hamiltonian to some geometrically local region to those of the full Hamiltonian. Let \(\Pi_{N(X)}\) be the ground-state subspace projector of the Hamiltonian that includes all terms with at least some support on a geometrically local region \(X\), with \(N(X)\) consisting of the smallest region containing the support of all included terms. TQO-2 states that any operator \(O_X\) that annihilates the codespace projector \(\Pi\) also has to annihilate the local projector \(\Pi_{N(X)}\), \begin{align} O_{A}\Pi=0\quad\Rightarrow\quad O_{A}\Pi_{N(A)}=0~. \tag*{(16)}\end{align} This condition implies that any operator supported solely on \(A\) cannot distinguish the global projector from the local one [35,36].

Nice error basis

view in context →

A nice error basis [37–39] for an \(q\)-dimensional vector space is a set \(\{E_g~,~g\in G\}\) of unitary operators, where \(G\) is a (not necessarily Abelian) group of order \(q^2\), and where \begin{align} \text{tr}(E_{g})&=q\delta^{G}_{g,1}\tag*{(17)}\\ E_{g}E_{h}&=\omega_{g,h}E_{gh} \tag*{(18)}\end{align} for all group elements \(g,h\). Above, \(\delta^{G}_{g,1}\) is the group Kronecker-delta function. A basis is called very nice if \(\omega\) is a root of unity. This definition can naturally be extended to continuous groups.

Pseudo-threshold (a.k.a. break-even point)

view in context →

The ultimate goal of error correction is to make sure that the logical error rate is greater than the underlying physical error rate. For a noise model parameterized by a single physical error rate \(p\), the pseudo-threshold or break-even point is the smallest \(p\) at which the logical error rate after error correction is equal to \(p\).

Knill-Laflamme conditions

view in context →

The Knill-Laflamme error-correction conditions [40–42][43; 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*{(19)}\end{align} where the QEC matrix elements \(c_{ij}\) are arbitrary complex numbers.

Degeneracy

view in context →

A code is degenerate with respect to a noise model if different errors map code states to the same error subspace. For a linearly independent error set \(\cal{E}\), degeneracy is equivalent to \(\text{rank}(c_{ij}) < |\cal{E}|\) [44].

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) [45; 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*{(20)}\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. [46] and Sec. IV of Ref. [47]).

For periodic boundary conditions, this mapping can be thought of as a quantum extension of the cyclic-to-polynomial correspondence. For open boundary conditions, this mapping extends the mapping used in quantum convolutional codes to multiple spatial dimensions.

BPT bound

view in context →

Lattice qubit codes are limited by the Bravyi-Poulin-Terhal (BPT) bound [48] (see also [49–51]), 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})\) [49]. Codes on a \(D\)-dimensional homogeneous Riemannian manifold with diameter \(L\) satisfy \(k = O(L^{D-2})\) [52]. Some non-locality is necessary to circumvent these bounds [53].

Bravyi-Koenig bound

view in context →

Logical gates implemented via constant-depth quantum circuits on a \(D\)-dimensional lattice stabilizer code whose distance increases at least logarithmically with \(n\) lie in the \(D\)th level of the Clifford hierarchy [54]. A refinement can be made that expresses the bound in terms of higher-group symmetries of the topological phases underlying the codes [55; Sec. 5.4.2]. Conversely, the distance of a code on an \(L^{D}\) lattice is upper bounded by order \(O(L^{D+1-\nu})\) if the code implements an \(\nu\)th-level Clifford hierarchy gate [56]. The code capacity threshold of such a code family is upper bounded by \(1/\nu\) [56].

Subsystem BT bound

view in context →

The subsystem BT bound is an upper bound of \(d = O(L^{D-1})\) on the distance [49] 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)\) [50]. More generally, there is a tradeoff theorem [57] 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})\).

Subsystem PYBK bound

view in context →

The Bravyi-Koenig bound can be extended to subsystem codes by Pastawski and Yoshida. Namely, logical gates implemented via constant-depth quantum circuits on a \(D\)-dimensional lattice subsystem code whose distance increases at least logarithmically with \(n\) lie in the \(D\)th level of the Clifford hierarchy [56].

Dicke states

view in context →

For \(n\)-qubit block codes, an often used basis for the \(n+1\)-dimensional PI subspace consists of the Dicke states \(|D^n_w\rangle\) -- normalized PI states of \(w\) excitations, i.e., a normalized sum over all binary-string basis elements with \(w\) ones and \(n - w\) zeroes. For example, the single-excitation Dicke state on three qubits is \begin{align} |D_{1}^{3}\rangle=\frac{1}{\sqrt{3}}\left(|001\rangle+|010\rangle+|100\rangle\right)~. \tag*{(21)}\end{align} The \(n+1\)-dimensional PI space can be thought of as a standalone spin-\(n/2\) quantum system, yielding a way to convert between permutation-invatiant qubit codes and \(SU(2)\) spin codes. A single-spin code for the \(SU(2)\) group correcting spherical tensors can be mapped into a PI qubit code with an analogous distance [58][59; Thm. 1].

Pauli strings

view in context →

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*{(22)}\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.

Quantum weight enumerator

view in context →

Determining protection and bounds on code parameters can also be done using the code's Shor-Laflamme quantum weight enumerator [60] (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*{(23)}\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).

Clifford group

view in context →

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. [44,61–63] for generators, relations, and normal form. The group cannot be expressed as a semidirect product of the Pauli and symplectic groups [64]. There is a canonical form for Clifford circuits [65,66]. 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 [67].

Clifford hierarchy

view in context →

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

Effective distance and hook errors

view in context →

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 [73]. 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 [44]) to detect hook errors may be necessary to yield fault-tolerant decoders.

Computational threshold

view in context →

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 [74–80]; 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 [81]. Subsequently, thresholds were determined for infinite families of lattice stabilizer codes, starting with the toric code [73]; 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 [82].

Measurement threshold

view in context →

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

Steane enlargement

view in context →

An \([[n,2k-n,d]]\) CSS code can be converted to a \([[n,k+k^{\prime}−n,\min(d,\left\lceil 3d^{\prime}/2\right\rceil )]]\) code for particular \(k^{\prime}\) and \(d^{\prime}\) via the Steane enlargement construction [88].

Symplectic representation

view in context →

In the 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,\omega^2,\omega\}\) of the quaternary Galois field \(GF(4)\).

Cleaning lemma

view in context →

If all logical operators act trivially on some subset of qubits in a stabilizer code, then any logical Pauli operator can be represented on the complementary qubit subset via a stabilizer. More technically, given any subset \(M\) of qubits that is correctable (under erasure), any logical Pauli operator \(P\) can be cleaned off of \(M\) using a stabilizer \(S\) such that \(PS\) is supported on \(M^{\perp}\). More generally, for any \(M\), we have \(g(M)+g(M^{\perp}) = 2k\), where \(g(M)\) is the number of logical-\(X\) and logical-\(Z\) Pauli operators supported fully on \(M\) (up to stabilizers). The Cleaning Lemma was originally proven [49], where an analogous result is states for subsystem codes; see also Ref. [89].

Destabilizers

view in context →

A Clifford encoding circuit maps the first \(r = n-k\) qubits to the logical qubits of the code, and the Pauli \(Z\) operators of those first \(r\) qubits are mapped into a set of stabilizer generators. The set of Pauli \(X\) operators of the first \(r\) qubits that are mapped into a set of generators for the destabilizer group [90,91]. Each such generator anticommutes with only one stabilizer generator while commuting with the rest of the stabilizer generators.

Modular-qudit Pauli strings

view in context →

For a single qudit, this set consists of products of powers of the modular-qudit Pauli matrices \(X\) and \(Z\), which act on computational basis states \(|k\rangle\) for \(k\in\mathbb{Z}_q\) as \begin{align} X\left|k\right\rangle =\left|k+1\right\rangle \,\,\text{ and }\,\,Z\left|k\right\rangle =e^{i\frac{2\pi}{q}k}\left|k\right\rangle ~, \tag*{(25)}\end{align} with addition performed modulo \(q\). For multiple qudits, error set elements are tensor products of elements of the single-qudit error set. Tensor products of \(X\) (\(Z\)) modular-qudit Paulis acting on different qudits are called \(X\)-type (\(Z\)-type) modular-qudit Pauli strings. Combining the \(X\)-type and \(Z\)-type strings with a primitive \(q\)th root of unity forms a group called the modular-qudit Pauli group (on \(n\) modular qudits.

Qudit Clifford hierarchy

view in context →

The modular-qudit Clifford hierarchy [56,68,69,92] 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*{(26)}\end{align} where \(P\) is any modular-qudit Pauli matrix, and \(C_1\) is the modular-qudit Pauli group.

Modular symplectic representation

view in context →

The single modular-qudit Pauli string \(X_{a} Z_{b}\) for \(a,b\in \mathbb{Z}_q\) is converted to the vector \((a|b)\in \mathbb{Z}_q^2\). The multi modular-qudit version follows naturally.

Stabilizer code switching, code deformation, or 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\)-modular-qudit Pauli group, \begin{align} \mathsf{S}\to\mathsf{N}_{\left\langle \mathsf{S},\mathsf{F}\right\rangle }\left(\mathsf{F}\right)~, \tag*{(27)}\end{align} where \(\mathsf{Z}\) denotes taking the center of a group (e.g., see [43,83] 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 [93; Prop. II.1]. Clifford operations and Pauli measurements can be expressed as sequences of code switching [94]. 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}\). Code switching can be done using only transversal gates for qubit stabilizer codes [95].

Symplectic doubling

view in context →

Any \([[n,k,r,d]]_{\mathbb{Z}_q}\) subsystem stabilizer code can be mapped onto a \([[2n,2k,2r,\geq d]]_{\mathbb{Z}_q}\) subsystem CSS code, with the mapping preserving geometric locality of a code up to a constant factor [96] (see also [97][98; Thm. 1]). In the modular symplectic representation, the gauge-group generator matrix of the former is mapped into that of latter as follows, \begin{align} \begin{pmatrix}G_{X} & G_{Z}\end{pmatrix} \to \begin{pmatrix} 0 & 0 & G_{Z} & -G_{X}\\ G_{X} & G_{Z} & 0 & 0 \end{pmatrix}~, \tag*{(28)}\end{align} where the first two columns of the latter matrix correspond to the \(X\)-type part of the gauge-group generator matrix of the output subsystem CSS code. In the case of a stabilizer code, the stabilizer generator matrix is mapped instead to yield a two-block CSS code (see [98; Thm. 1] for the case of qubit stabilizer codes). For geometrically local 2D stabilizer codes with twist defects, this mapping yields a twisted double cover of the underlying qudit geometry [64].

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*{(29)}\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*{(30)}\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 qudits of the original subsystem code, then gauging out those qudits is equivalent to treating them as gauge qubits. Gauging out should not be confused with gauging (or ungauging) symmetries [99–102], a different process rooted in gauge theory which can be done to stabilizer or subsystem codes and which can change \(n\).

Galois-qudit Pauli strings

view in context →

For a single Galois qudit, this set consists of products of \(X\)-type and \(Z\)-type operators labeled by elements \(\beta \in GF(q)\), which act on computational basis states \(|\gamma\rangle\) for \(\gamma\in GF(q)\) as \begin{align} X_{\beta}\left|\gamma\right\rangle =\left|\gamma+\beta\right\rangle \,\,\text{ and }\,\,Z_{\beta}\left|\gamma\right\rangle =e^{i\frac{2\pi}{p}\text{tr}(\beta\gamma)}\left|\gamma\right\rangle~, \tag*{(31)}\end{align} where \(\text{tr}\) is the field trace. For multiple Galois qudits, error set elements are tensor products of elements of the single-qudit error set. Tensor products of \(X\) (\(Z\)) Galois-qudit Paulis acting on different qudits are called \(X\)-type (\(Z\)-type) Galois-qudit Pauli strings. Combining the \(X\)-type and \(Z\)-type strings with a \(p\)th root of unity forms a group called the Galois-qudit Pauli group (on \(n\) Galois qudits.

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)\in GF(q)^2\). 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)\). Given a basis \((\beta,\beta^q)\) for \(GF(q^2)\) over \(GF(q)\), the vector \((a|b)\in GF(q)^2\) (representing a Galois-qudit Pauli string in the Galois symplectic representation) is in one-to-one correspondence with element \(a \beta + b \beta^q \in GF(q^2)\) [103][104; Thm. 27.3.8].

Weight reduction

view in context →

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