Additive Codes: What are they? And how are they related to stabilizer codes?

Question

I recently encountered the term "additive code" in the answer to my question here

What are nontrivial examples of stabilizer codes whose codewords have some $\pm i$ coefficients?

Implicit in the answer seems to be the claim that additive codes are equivalent to stabilizer codes.

Googling "additive code" turns up things like

Why stabilizer codes are named additive quantum codes?

and

https://inst.eecs.berkeley.edu/~cs191/fa05/projectreports/QECC1-report.pdf

which again claim that additive codes are equivalent to stabilizer codes. But they don't seem to actually define what additive means. (Or for that matter what equivalent means in this setting.)

What is the right definition of additive? What do people mean when they say that "additive code is just another name for stabilizer code" (direct quote from appendix of Gottesman's thesis https://arxiv.org/pdf/quant-ph/9705052.pdf)?

Answer 1

Let me add a potentially much simpler explanation here. Consider a vector space over a finite field, $V \subseteq \mathbb{F}^n_q$. These are length $n$ vectors whose elements are in $\mathbb{F}_q$. As a vector space, it is closed under multiplication by scalars, i.e., if $v \in V$, then $cv \in V$ for $c \in \mathbb{F}_q$. This is called linear. Stabilizer codes are generally not linear (not to be confused with nonlinear).

Recall that in the symplectic formulation of stabilizer codes, a stabilizer can be written in the form $(a, b)$ where $a, b \in \mathbb{F}^n_q$. The $a$ part gives the $X$ stabilizers and the $b$ part gives the $Z$ stabilizers. A more compact way to write this is as a length $n$ vector $a + \omega b$, where $\omega$ is now a primitive element for the extension $\mathbb{F}_{q^2}/\mathbb{F}_q$. Basically, recall that $\mathbb{F}_4 = \{0, 1, \omega, \omega^2\}$ and is not equivalent to $\mathbb{Z}_4 = \{0, 1, 2, 3\}$. In this notation we have stabilizers which are elements of $\mathbb{F}^n_{q^2}$ instead of $\mathbb{F}^{2n}_q$.

Now, consider, for example, the $[[15, 1, 3]]$ quantum Reed-Muller code with stabilizers $$ \begin{pmatrix} \omega & 0 & \omega & 0 & \omega & 0 & \omega & 0 & \omega & 0 & \omega & 0 & \omega & 0 & \omega\\ 0 & \omega & \omega & 0 & 0 & \omega & \omega & 0 & 0 & \omega & \omega & 0 & 0 & \omega & \omega\\ 0 & 0 & 0 & \omega & \omega & \omega & \omega & 0 & 0 & 0 & 0 & \omega & \omega & \omega & \omega\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & \omega & \omega & \omega & \omega & \omega & \omega & \omega & \omega\\ 0 & 0 & \omega & 0 & 0 & 0 & \omega & 0 & 0 & 0 & \omega & 0 & 0 & 0 & \omega\\ 0 & 0 & 0 & 0 & \omega & 0 & \omega & 0 & 0 & 0 & 0 & 0 & \omega & 0 & \omega\\ 0 & 0 & 0 & 0 & 0 & \omega & \omega & 0 & 0 & 0 & 0 & 0 & 0 & \omega & \omega\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \omega & \omega & 0 & 0 & \omega & \omega\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \omega & \omega & \omega & \omega\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \omega & 0 & \omega & 0 & \omega & 0 & \omega\\ 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1\\ 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\ \end{pmatrix} $$ In this notation, a $0$ is an $I$, a $1$ is an $X$, an $\omega$ is a $Z$, and an $\omega^2 = 1 + \omega$ is a $Y$. We see this is a CSS code since the stabilizers are purely $X$ or purely $Z$. Applying any stabilizer to itself (repeatedly) is the same as vector addition in this notation. Repeated addition is the same as multiplication, so these stabilizers are closed under multiplication by $\{0, 1\}$. However, you cannot multiply a row by, say, $\omega$, because that would convert an $X$ stabilizer to a $Z$ stabilizer and vice-versa. In this sense, the code is not closed under multiplication by every element of the underlying field. It is therefore not a linear space but only an additive space (closed under addition).

Some stabilizer codes are symmetric and fully linear. Most are not. That's why they are called additive codes. These terms are essentially equivalent, but stabilizer codes are also self-dual (additive codes) under some proper inner product in order to enforce the orthogonality relationship between $X$ and $Z$.

I will add as a side-note that additive codes can give non-intuitive results. Consider a qubit stabilizer code of length $n$. The size of the total space is $2^n$. There are $n - k$ stabilizers, so all possible combinations give a subspace of size $2^{n - k}$. The code therefore has dimension $\log_2(2^n / 2^{n - k}) = \log_2(2^k) = k$. When you go to qudit systems with more complicated finite fields, you get expressions such as $q^n / p^{n - k}$, which may or may not be an integer (here $q = p^m$ and $p$ is the characteristic of the field). This suggests such a code can encode a non-integer number of logical operators. Due to this, classical additive codes are usually expressed in a different symbol then the standard linear notation $[n, k, d]$ that people are used to. This causes a lot of unnecessary confusion.

Answer 2

Let me offer a brief answer for now as I don't have much time today. Much of this material is from a friend's lecture notes. Feel free to ask more questions if you need further clarification.

I'll represent the group action of a group $G$ on a vector space $V$ as $G \curvearrowright V$ and the invariant subspace of $V$ under this group action as $\mathrm{Inv}_G(V) := \{v : gv = v \ \forall g \in G\}$.

If $V = \mathcal H$ is a Hilbert space and $G \curvearrowright V$ is a unitary action and $G$ acts by isometries for a quantum metric then the subspace $\mathrm{Inv}_G(\mathcal H) \subseteq \mathcal H$ is called a stabilizer code in general. The exact definition of a quantum metric is a bit involved; for starters, you can check the first two pages of the Weaver-Kuperberg paper that I linked, or I can explain it later if you wish.

The point now is that if the quantum metric under consideration is the quantum Hamming metric and $G$ is the multi-Pauli group then $\mathrm{Inv}_G(\mathcal H_n) \neq 0 \iff \text{$G$ is abelian}$. Then $\mathrm{Inv}_G(\mathcal H_n)$ is an example of what is called additive code (not the definition!). In the QCQI community, there's a tendency to conflate this with the notion of general stabilizer codes. Well, partly due to the way Gottesman et al. and subsequently Nielsen & Chuang described it in their papers and books. If you're having confusion about terminology, rest assured that you're not alone. :-)

The word "additive code" originally comes from classical coding theory. In full generality, a code $\mathcal C$ is a subset of a space of messages $\mathcal X$, i.e., $\mathcal C \subseteq \mathcal X$, equipped with a metric $d(.,.)$, carefully chosen to allow for detection and correction of errors. One major issue with this fully general case is that if you choose a radius $r$ ball around any arbitrary codeword $C \in \mathcal C$, you're not guaranteed to have an equal number of messages within each such ball. (By the way, if you need a refresher on classical coding theory, check Wootter's lectures.)

To symmetrize this scenario and to make analysis easier, a simplifying assumption is that $\mathcal X$ is abelian group and $\mathcal C \subseteq \mathcal X$ is a subgroup, s.t., $d(x, y) = d(x + z, y + z) \ \forall x, y, z \in \mathcal X$ or equivalently $||x|| := d(x, 0)$ so $d(x, y) = ||x - y||$. This means the metric is chosen to be translation invariant. It is this condition that allows us to correspond the abelian group structure and the metric structure -- a norm is an abelian case of a translation invariant metric. Such a code $\mathcal C \subseteq \mathcal X$ is an additive code. Yes, this is the definition that you were looking for.

For example, the usual Hamming distance is a metric that is clearly translation invariant, so we can see the Hamming distance comes from a Hamming norm, a value equal to the Hamming weight $||x||$, or in other words, the number of $1$s appearing in an $x \in \mathcal X$.

Furthermore, if $\mathcal X$ is equipped with a vector space structure, then it is possible for $\mathcal C$ to be a subspace (and thus, be a linear code). We can then expect a relation between $||x||$ and $||\lambda x||$ where $\lambda \in \mathbb F$ (the underlying field of the vector space $\mathcal X$). The Banach relation $||\lambda x|| = |\lambda|.||x||$ is appropriate when say $\mathbb F = \mathbb C$ or $\mathbb F = \mathbb R$ but it doesn't make much sense here. If $\mathbb F = \mathbb Z/p\mathbb Z$ or any finite field, we can instead take the Hamming relation that $||\lambda x|| {=}_{\lambda \neq 0} ||x||$. That is, we treat all non-zero scalars in the same way, or effectively take there to be no relation. We do not need to have an axiom concerning scalar multiplication because if $\mathcal C$ is an additive code then $\mathcal C$ must be a linear code. For the field $\mathbb Z/2\mathbb Z$, linear and additive codes are the same.

Here's a useful theorem. Theorem: If $V$ is a vector space over $\mathbb Z/p\mathbb Z$ and $\mathcal C \subseteq V$ is a subgroup, then it is a subspace. You should note that this theorem is false for fields other than $\mathbb Z/p\mathbb Z$.

The point is that if a metric space $\mathcal X$ is finite, abelian and normed (as is the case if $\mathcal X$ is a Hamming space) then the balls of the same radii $r$ have the same cardinality:

$$|B(x, r)| = |B(y, r)|$$

where $x$ is the ball center and $y$ is the ball radius. This is a reflection of the translation symmetry of a group law, and in such a scenario, analysis of the code becomes much simpler.