Classical and Quantum Error-Correcting Codes

Let $F$ be a field, let $n,k\in \mathbb{N}$, and let $G\in M_{n\times k}(F)$. Regard $G$ as the linear map $T_G:F^k\to F^n$, $x\mapsto Gx$, using column vectors. If the columns of $G$ are linearly independent, then $\mathrm{im}{T}_G$ is a $k$-dimensional linear subspace of $F^n$. This includes $k=0$ and $n=0$.

• No Choice axiom is used. The zero-column case is an empty matrix map from the zero space.

Let $V:H\to K$ be a linear isometry between finite-dimensional complex inner-product spaces whose pairings are linear in the first argument. Then $⟨Vx,Vy{⟩}_K=⟨x,y{⟩}_H$ for all $x,y\in H$.

The proof is a direct finite algebra expansion under the root convention and uses no choice principle.

Let $F$ be a finite field of order $q$, let $n\ge 1$, and let $C\le F^n$ be a linear subspace (Finite fields and their order, Vector space over a field, Linear subspace of a vector space). Put $k:={\dim }_{F}C$; since $F^n$ has dimension $n$, $0\le k\le n$ (The standard list $e:n\to F^n$ with $e_i(i)=1_F$ and $e_i(j)=0_F$ for $j\mathrm{\ne }i$ is an ordered basis of $F^n$; hence ${\dim }_F{F}^n=n$, and $F^0$ is the zero space with basis $\mathrm{\varnothing }$ and dimension $0$, If ${\dim }_{F}V=n$ and $U$ is a linear subspace of $V$, then $U$ is finite-dimensional, ${\dim }_{F}U\le n$, and ${\dim }_{F}U=n$ if and only if $U=V$). A classical linear code over $F$ with a specified encoding is the data $(F,n,C,\mathrm{Enc})$, where $\mathrm{Enc}:F^k\to C$ is a linear isomorphism. Such an isomorphism exists because ${\dim }_F{F}^k=k$ and finite-dimensional vector spaces of equal dimension are isomorphic (Two finite-dimensional vector spaces over $F$ are linearly isomorphic if and only if they have the same dimension). The field is part of the data: notation $F_q$ does not identify the field with $\mathbb{Z}\mathrm{/}q\mathbb{Z}$; that quotient is a field only when $q$ is prime.

If $C=\{0\}$, then $k=0$, $F^0=\{0\}$, and the encoding is the unique map between these zero spaces. If an encoding is represented by a full-column-rank matrix $G\in M_{n\times k}(F)$, its image has dimension $k$ by A full-column-rank matrix has image dimension equal to its number of columns.

The code is the linear subspace together with a declared message encoding. No field existence or uniqueness theorem is repeated here.

For $x=(x_0,\dots ,x_{n-1})\in F^n$, its Hamming weight is $\mathrm{wt}(x):=\mathrm{\mid }\{j<n:x_j\mathrm{\ne }0\}\mathrm{\mid }$. For $x,y\in F^n$, their Hamming distance is $d_H(x,y):=\mathrm{wt}(x-y)$. For a nonzero code $C\le F^n$, define its minimum distance by $d(C):={\min }_{0\mathrm{\ne }c\in C}\mathrm{wt}(c)$. This minimum exists because its nonempty set of values lies in $\{1,\dots ,n\}$ and the natural numbers are well ordered (The well-ordering principle). For the zero code $C=\{0\}$, set $d(C):=n+1$ by convention; this sentinel exceeds every possible Hamming weight and makes the usual radius statements vacuously valid for distinct codewords.

The code parameters are written $[n,k,d{]}_q$, where $q=\mathrm{\mid }F\mathrm{\mid }$ and $d=d(C)$. This notation records a finite-field alphabet and does not imply that $F=\mathbb{Z}\mathrm{/}q\mathbb{Z}$.

The identity $d_H(x,y)=\mathrm{wt}(x-y)$ is used over every characteristic; only in characteristic two does subtraction equal addition.

For $x,y\in F^n$, define the standard bilinear dot product $x\cdot y:={\sum }_{j<n}{x}_j{y}_j$. For any linear subspace $C\le F^n$ (Linear subspace of a vector space)—in particular, the codeword subspace of a classical linear code as in Classical linear code over a finite field—its dual code is

$C^{\perp }:=\{y\in F^n:x\cdot y=0\text{ for every }x\in C\}\mathrm{.}$

This is a bilinear pairing over $F$; it is not a positive-definite or Hermitian inner product. The proof that $C^{\perp }$ is a linear subspace, has dimension $n-k$, and satisfies $(C^{\perp }{)}^{\perp }=C$ is Dimension and double-dual identity for finite-field code duals.

Let ${\mathcal{H}}_L$ be a finite-dimensional complex inner-product space and let ${\mathcal{H}}_P={⨂}_{j<n}{\mathcal{H}}_j$ be a fixed ordered finite register tensor product with $n\ge 1$, supplied by the QC register interface. A quantum code is an isometric encoding $V:{\mathcal{H}}_L\to {\mathcal{H}}_P$. Its code subspace is $\mathcal{C}:=\mathrm{im}V$, its logical dimension is $K:=\dim {\mathcal{H}}_L$, and its physical block length is the number $n$ of tensor factors. When each physical factor is a qubit, ${\mathcal{H}}_P\cong ({\mathbb{C}}^2{)}^{\otimes n}$; a logical $k$-qubit register has $K=2^k$. Require $K\ge 1$.

Using the root library's adjoint convention, the code projector is $P:=V{V}^{\ast }\in \mathrm{End}({\mathcal{H}}_P)$. The theorem An isometric quantum encoding gives an orthogonal code projector ↗ proves $V^{\ast }V=I_{{\mathcal{H}}_L}$, $P^{\ast }=P=P^2$, and $\mathrm{im}P=\mathcal{C}$, including one-dimensional logical spaces and the full-space code.

The QC02 suppliers set $Q_d={\mathbb{C}}^d$ for $d\ge 1$, order qubit strings lexicographically with the first wire most significant, and distinguish the empty register $\mathbb{C}$ from ${\mathbb{C}}^0$ (Finite registers and their ordered computational bases). Ordered tensor registers use the factorwise product pairing, linear in the first argument, and declared wire permutations have inverse permutations (Ordered tensor registers, their inner product, and wire permutations). These are the conventions used here.

For every finite field $F$ and $n\in \mathbb{N}$, $d_H(x,y)=\mathrm{wt}(x-y)$ is a metric on $F^n$. If $n\ge 1$ and $C\le F^n$ is the codeword subspace of a classical linear code, then for nonzero $C$, ${\min }_{x\mathrm{\ne }y\in C}{d}_H(x,y)={\min }_{0\mathrm{\ne }c\in C}\mathrm{wt}(c)=d(C)$. For $C=\{0\}$ there are no distinct codewords, and the distance parameter is the stated convention $n+1$.

This proof is independent of the field characteristic and uses no choice principle.

Let $F$ be a finite field, $n\in \mathbb{N}$, and let $D\le F^n$ be a linear subspace (Linear subspace of a vector space) of dimension $r$. Then $D^{\perp }$ is a linear subspace of dimension $n-r$, and $(D^{\perp }{)}^{\perp }=D$. In particular this holds for every classical linear code, including $D=\{0\}$ and $D=F^n$ (Classical linear code over a finite field).

The coordinate pairing is nondegenerate over every field because the standard coordinate rows form a basis. No complex conjugation is used, and no choice principle is needed in finite dimension.

Let ${\mathcal{H}}_L,{\mathcal{H}}_P$ be finite-dimensional complex inner-product spaces and let $V:{\mathcal{H}}_L\to {\mathcal{H}}_P$ be a linear isometry. Then $V^{\ast }V=I_{{\mathcal{H}}_L}$. Consequently $P:=V{V}^{\ast }$ is self-adjoint and idempotent and is the orthogonal projection onto $\mathrm{im}V$. If $K=\dim {\mathcal{H}}_L$ and $N=\dim {\mathcal{H}}_P$, then $0\le K\le N$; when $K=1$ the code is a line, and when $K=N$ the code subspace is all of ${\mathcal{H}}_P$ and $P=I_{{\mathcal{H}}_P}$.

The root inner product is linear in the first argument; no bra-ket convention is imported. The norm-preservation implication is proved locally in Finite complex linear isometries preserve inner products, so this argument uses no choice principle.

Let $C\le F^n$ have distance parameter $d=d(C)$ and put $t=\lfloor (d-1)\mathrm{/}2\rfloor$. For distinct codewords $c,c^{\mathrm{\prime }}\in C$, the closed Hamming balls $B_t(c):=\{r:d_H(r,c)\le t\}$ and $B_t(c^{\mathrm{\prime }})$ are disjoint.

Let $C\le F^n$ have dimension $k$. A generator matrix for $C$ is a matrix $G\in M_{n\times k}(F)$ with linearly independent columns and column space $C$. A parity-check matrix for $C$ is a matrix $H\in M_{(n-k)\times n}(F)$ with linearly independent rows and nullspace $C$. With column-vector conventions, $G:F^k\to F^n$ and $H:F^n\to F^{n-k}$; the product $HG$ is defined and is the zero matrix. Existence for every code, the identity $HG=0$, and the boundary shapes are proved in Every finite-field linear code has generator and parity-check matrices.

The row vectors of $H$, identified with their coordinate columns by transpose and the bilinear dot product, span $C^{\perp }$. No Hermitian conjugation is used. The matrices have shapes $n\times k$ and $(n-k)\times n$, including $n\times 0$ and $0\times n$ matrices.

Fix an ordered physical register ${\mathcal{H}}_P={⨂}_{j<n}{\mathcal{H}}_j$ with finite-dimensional factors. For $S\subseteq [n]:=\{0,\dots ,n-1\}$, form ${\mathcal{H}}_S$ and ${\mathcal{H}}_{S^c}$ in the inherited order, and let ${\mathrm{\Pi }}_S:{\mathcal{H}}_P\to {\mathcal{H}}_S\otimes {\mathcal{H}}_{S^c}$ be the declared bijective wire permutation. An operator $E\in \mathrm{End}({\mathcal{H}}_P)$ is supported in $S$ if there is $E_S\in \mathrm{End}({\mathcal{H}}_S)$ with

${\mathrm{\Pi }}_{S}E{\mathrm{\Pi }}_S^{-1}=E_S\otimes I_{S^c}\mathrm{.}$

Its weight is $\mathrm{wt}(E):=\min \{\mathrm{\mid }S\mathrm{\mid }:E\text{ is supported in }S\}$. The minimum exists because the full set $[n]$ supports every operator and $[n]$ has finitely many subsets. Let ${\mathcal{H}}_{\mathrm{\varnothing }}=\mathbb{C}$; scalar identity operators have weight zero. The weight is invariant under reordering the tensor factors by their declared wire permutation (Operator support weight is invariant under wire permutation ↗).

Here $E_S\otimes I_{S^c}$ is the tensor map of Tensor products of finitely many linear maps. The product factors may have arbitrary finite dimensions; qubits are the special case $\dim {\mathcal{H}}_j=2$ for every $j$.

The register tensor pairing and exact permutation convention are supplied by Ordered tensor registers, their inner product, and wire permutations and Finite wire permutations are unitary basis permutations. Their current bodies were inspected; Operator support weight is invariant under wire permutation ↗ proves the resulting weight invariance.

Let $C\le F^n$ have dimension $k$. There are matrices $G\in M_{n\times k}(F)$ and $H\in M_{(n-k)\times n}(F)$ such that the columns of $G$ form a basis of $C$, the rows of $H$ form a basis of $C^{\perp }$ after transpose identification, $\ker H=C$, and $HG=0$. This includes $k=0$ and $k=n$.

The choices in steps 1.1 and 1.2 are choices of one finite basis at a time; the finite-dimensional basis theorem used here is choice-free. For $k=0$, $H$ can be chosen as the identity matrix of size $n$; for $k=n$, $G$ can be chosen as the identity and $H$ is the unique $0\times n$ matrix.

Let the source register have ordered factors ${\mathcal{H}}_0,\dots ,{\mathcal{H}}_{n-1}$, and let the target register have factors in the QC02 order ${\mathcal{H}}_{\sigma (0)},\dots ,{\mathcal{H}}_{\sigma (n-1)}$. Let ${\mathrm{\Pi }}_{\sigma }$ be the corresponding wire bijection and set $E^{\mathrm{\prime }}:={\mathrm{\Pi }}_{\sigma }E{\mathrm{\Pi }}_{\sigma }^{-1}$. An original factor labeled $i$ is in target position ${\sigma }^{-1}(i)$. Thus $E$ is supported in $S$ exactly when $E^{\mathrm{\prime }}$ is supported in ${\sigma }^{-1}(S)$; consequently $\mathrm{wt}(E^{\mathrm{\prime }})=\mathrm{wt}(E)$.

The QC02 bodies were inspected. This proof uses their declared factor-order action and bijective inverse; it does not identify differently ordered registers without a map.

Let $V:{\mathcal{H}}_L\to {\mathcal{H}}_P$ be an isometric encoding into a fixed ordered $n$-factor register with $n\ge 1$, $K:=\dim {\mathcal{H}}_L\ge 1$, and code projector $P=V{V}^{\ast }$. An operator $E\in \mathrm{End}({\mathcal{H}}_P)$ is detectable by the code if there is a scalar ${\lambda }_E\in \mathbb{C}$ such that

$PEP={\lambda }_{E}P\mathrm{.}$

When $K\ge 2$, define the quantum distance by

$d:=\min \{\mathrm{wt}(E):E\in \mathrm{End}({\mathcal{H}}_P),PEP\mathrm{\notin }\mathbb{C}P\},$

where $\mathbb{C}P:=\{\lambda P:\lambda \in \mathbb{C}\}$.

When $K=1$, set $d:=n+1$ by convention; the non-detectable set is empty in that case, as proved in Detectable operators form a subspace and quantum distance is well defined ↗. The same theorem proves that the minimum for $K\ge 2$ exists, the condition is linear in $E$, and changing $V$ to $VU$ for a logical unitary $U$ leaves $d$ unchanged.

This definition distinguishes detection from recovery: no recovery map or correction criterion is asserted here. In particular the distance theorem on this page only proves detection below $d$; correction maps are deferred to QC19.

The convention $n+1$ for a one-dimensional logical space is a sentinel larger than every possible operator weight. It avoids treating a minimum of an empty set as an ordinary integer minimum.

Let $P$ be the code projector of an isometric encoding into an $n$-factor register and let $K$ be the logical dimension. Then:

1. The set $\mathcal{D}(P):=\{E:PEP\in \mathbb{C}P\}$ of detectable operators is a complex linear subspace of $\mathrm{End}({\mathcal{H}}_P)$.
2. Replacing the encoding $V$ by $VU$ for any unitary $U$ on ${\mathcal{H}}_L$ leaves $P$, detectability, and distance unchanged.
3. If $K=1$, every operator is detectable, so the distance convention $n+1$ is appropriate. If $K\ge 2$, a non-detectable operator of weight at most $n$ exists, while every weight-zero operator is detectable; hence the minimum defining distance exists and lies in $\{1,\dots ,n\}$.

No Pauli-only reduction is used: the definition and proof range over all endomorphisms. The current QC02 register and wire-permutation definitions fix the factor order used by the code and support definitions.

Let $C\le F^n$ have parity-check matrix $H\in M_{(n-k)\times n}(F)$. The syndrome map is $s:F^n\to F^{n-k}$, $s(r):=Hr$, defined on every received word $r$. If $r=c+e$ with transmitted codeword $c\in C$ and error vector $e\in F^n$, its syndrome is the vector $s(r)$. The identity $s(r)=He$ is proved in A received-word syndrome depends only on the error vector. A syndrome is not itself a decoded error; a decoding rule is additional data.