4
$\begingroup$

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)?

$\endgroup$
4
  • 2
    $\begingroup$ I am confused by the connection you make between the support of a stabilizer code and additive codes. Normally, stabilizer codes are connected with additive self-orthogonal codes over $\mathbb F_4$ (c.f. Calderbank et al. "Quantum error correction via codes over GF(4)") and equivalent to those up to phases. Moreover, I don't see why the support of a stabilizer code should be a linear subspace. In the simplest example, stabilizer states, the support is affine, e.g. for $|1\rangle$. For non-maximal codes, the support should be affine too. $\endgroup$ Aug 5 at 14:29
  • 1
    $\begingroup$ @MarkusHeinrich Full disclosure: I just heard about additive codes for the first time two days ago quantumcomputing.stackexchange.com/questions/27594/… I don't know what the defintion is beyond this vague answer quantumcomputing.stackexchange.com/questions/9351/… Basically I'm interested in the claim from the first link that somehow additive codes are equivalent to stabilizer codes. I'll update the question to better reflect this. $\endgroup$ Aug 5 at 17:22
  • 1
    $\begingroup$ @IanGershonTeixeira Have a look in the Calderbank et al. paper which I mentioned. The code spaces arise by mapping the stabilizer group to isotropic subspaces of the symplectic vector space $\mathbb F_2^{2n}$ and then mapping these to subsets of $\mathbb F_4^n$ with a suitable orthogonal structure. This mapping is not linear, so you will only get additive codes over $\mathbb F_4$ in the sense that the code spaces are only closed under addition, not scalar multiplication. The equivalence you're looking for is proven in that paper (Thm. 2) $\endgroup$ Aug 6 at 13:54
  • 1
    $\begingroup$ BTW "additive code" and "linear code" are already defined in classical coding theory. "Additive code is another name for stabilizer code" is just false/misleading. There's the already mentioned connection to additive self-orthogonal codes over $\mathbb F_4$, but that's it. quantumcomputing.stackexchange.com/a/21971/2305 $\endgroup$ Aug 6 at 14:01

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
10
  • $\begingroup$ You mention that $ Inv_G(\mathcal{H}_n) $ is an example of an additive quantum code. And you define a classical additive code on $ n $ bits as a subgroup/subspace of $ \mathbb{F}_2^n $. Could you clarify for me what it means for a code to be additive in the quantum case? Something about a translation invariant metric? And for the difference between additive and linear are you saying that linear just means the norm is both translation and scaling invariant? Thanks for your long answer and offer to clarify. I appreciate it. $\endgroup$ Aug 7 at 16:58
  • $\begingroup$ @IanGershonTeixeira To answer your first question, indeed, it has to do with a translation invariant metric on $\mathcal M_2(\mathbb C)^{\otimes n}$ (the von Neumann algebra on $n$ qubits). In the quantum case, an additive code arises when we use the quantum Hamming metric and the group $G$ is taken to be the multi-Pauli group. Like the classical Hamming metric, the quantum Hamming metric is also translation invariant. You'll find the exact definitions on page 2 here. $\endgroup$ Aug 7 at 22:16
  • $\begingroup$ @IanGershonTeixeira To answer your second question, a linear code is defined as a subspace $\mathcal C$ of a vector space $\mathcal X$. We know that when we want to induce a norm from a metric $d(.,.)$ on a vector space, the metric $d$ must satisfy translation invariance and a scaling property. A general metric on a vector space need not satisfy these properties. However, if we want an additive code, which by definition requires a translation invariant metric, we can have a norm induced from the vector space metric. For example, the Hamming metric. $\endgroup$ Aug 7 at 22:37
  • $\begingroup$ The definition of additive code is this: A subgroup $\mathcal C$ of an abelian group $\mathcal G$, equipped with a translation invariant metric that induces a norm given an appropriate scaling property, or equivalently, equipped with a norm that automatically induces a translation invariant metric. That is what is meant by a norm being an abelian case of a translation invariant metric. $\endgroup$ Aug 7 at 22:56
  • $\begingroup$ Could you provide an example of an additive quantum code and an example of a non additive quantum code and explain how the difference can be determined based on your definitions? For example you could specify which $ \mathcal{G} $ and $ \mathcal{C} $ you are working with. I am aware that in the cases I am interested in $ G $ is the multi qubit Pauli group. What is the abelian group $ \mathcal{G} $? Is it the same as $ \chi $ from your answer above? Are $ \chi $ and $ \mathcal{G} $ abelian subgroups of the multi Pauli group? How does one pick the subgroup $ \mathcal{C} $ in a common example? $\endgroup$ Aug 9 at 15:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.