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