Quantum Error Correcting Codes: An introduction

Piyush P Kurur Department of Computer Science and Engineering Indian Institute of Technology Kanpur, Kanpur, Uttar Pradesh, India

                     email:ppk@cse.iitk.ac.in ^{∗}

Abstract

The aim of this article is to introduce the theory of quantum error correction codes. Starting with classical codes we build the necessary mathematical machinery to construct and analyse quantum codes. We will look at codes over the Hilbert space L^{2}(A) for some additive abelian group A and use the Weyl operators U_{a} and V_{b} to describe errors. We quickly specialise to special codes called stabiliser codes and look at stabiliser codes over finite fields. We also give quantum algorithm for error correction in the case of stabiliser codes.

Key words: Quantum codes, Weyl Operators, stabiliser codes.

1 Introduction

The basic problem of communication is the following: There are two entities, the sender and the receiver. From time to time the sender wishes to send information to the receiver. For this they are provided with a noisy channel. To set up reliable communication over this inherently noisy channel, we incorporate enough redundancy so that even if few errors occur during transmission, the receiver is able to detect and sometimes correct these errors. The goal of classical error correction is to design efficient encoding and decoding methods. For an introduction the reader may consult [4].

The aim of this article is to introduce the subject of quantum error correcting codes. Here the sender and receiver are quantum entities and the channel is a quantum channel. It may appear that classical techniques will not help in this situation because of some of the strange properties of quantum system like the non-cloning theorem. However this is not the case. Starting with classical codes we build up the mathematical machinery for constructing and analysing quantum codes, in the process show how remarkably similar their theory is. We quickly specialise to the beautiful theory of stabiliser codes. We also give a description of error correcting algorithm for stabiliser codes.

∗The author was a Ph.D student at the Institute of Mathematical Sciences when this tutorial lecture was given as part of QICC 2005, IIT Kharagpur

2 Classical Error correction

We begin with a brief overview of classical error correcting codes. An alphabet is a finite set Σ of letters. A word of length n over an alphabet Σ is an element of Σ^{n}. Any channel comes with an underlying alphabet. Letters of the alphabet are the smallest unit of information that can be sent across the channel. Due to noise, during the transmission some of the letters get corrupted.

Assume that we have a sender who, from time to time, sends one of the messages M_{1}, …, M_{k} to a receiver through a channel C. There is an encoding procedure which is agreed upon by both the sender and receiver — a set of words w_{1}, …, w_{k} over the underlying alphabet of the channel, all of which we assume are of length n, are chosen such that the sender sends w_{i} whenever he wishes to send M_{i}. However, since the channel is not ideal, errors creep in. Our task is to find a subset C ⊆ Σ^{n} of size k such that for certain number of errors the receiver can detect (or sometimes correct) it. Such a set C is called a code and n is the length of the code.

We now make some simplifying assumptions. We will assume, without loss of generality, that Σ is an additive abelian group (A, +, 0). Words of length n are now elements of the additive abelian group A^{n}. Errors now become additive errors — suppose a word u is sent and a word v is received then we can think of the channel adding an error of e = v − w. We now define a metric structure on A^{n}.

Definition 2.1 (Hamming Distance). Given words u = u_{1} … u_{n} and v = v_{1} … v_{n} in A^{n} the Hamming distance, d (u, v), is the number of positions i such that u_{i} ≠ v_{i}. For an element u = u_{1} … u_{n}, the weight w (u) is #{u_{i} : u_{i} ≠ 0}.

Note that d (u, v) = w (u − v).

An error that effects t positions is nothing but an additive error of weight t. We are interested in codes C ⊂ A^{n} that can tolerate t-errors. For a code C we define the distance d(C) to be min{d (u, v) : u, v ∈ C and u ≠ v} One has the following theorem.

Theorem 2.2. A code of minimal distance d can detect d − 1 errors and correct ⌊\frac{d−1}{2}⌋ errors.

Proof sketch. An additive error of weight less than d will not take a valid code word to another codeword. So one can detect an error that corrupts at most d − 1 positions.

Decoding is done using nearest neighbour algorithm: Given a word output the nearest code word. This will work provided at most ⌊\frac{d−1}{2}⌋ positions are corrupted. This is because if we consider balls of radius less than ⌊\frac{d−1}{2}⌋ then none of the balls intersect.

3 Quantum error correcting code

We saw that for classical channels there is an underlying alphabet, elements of which are the smallest units of information that can be sent. In the case of quantum channel the analogous entity is a finite dimensional Hilbert space H. Again with out loss of generality we assume that the Hilbert space H is L^{2}(A), the space of functions from an additive abelian group (A, +, 0) to ℂ. This space is nothing but a finite dimensional Hilbert space with orthonormal basis |a⟩, a ∈ A. Vectors in L^{2}(A) are analogous to letters in the classical setting. Naturally “quantum word” of length n should be elements of the tensor product L^{2}(A)^{⊗^{n}}. For a word w = w_{1} … w_{n} in A^{n} we will use |w⟩ to denote the vector |w_{1}⟩⊗…⊗|w_{n}⟩. Thus {|w⟩ : w ∈ A} gives a orthonormal basis for L^{2} (A)^{⊗^{n}}. A quantum code is a subspace C of L^{2} (A)^{⊗^{n}}.

The sender and receiver are quantum entities and the channel is a quantum channel. The messages that the sender wishes to send come from a finite dimensional Hilbert space H_{M} with orthonormal basis |0⟩ , …, |k⟩. As before the sender and receiver agrees upon a code C with orthonormal basis say |ψ_{0}⟩ , …, |ψ_{k}⟩. To send |i⟩ the sender transmits |ψ_{i}⟩. What if the sender wishes to send an arbitrary unit vector |ϕ⟩ in H_{M} ? He just extend the encoding process linearly. In other words if |ϕ⟩ = ∑ α_{i} |i⟩ then the sender transmits ∑ α_{i} |ψ_{i}⟩.

4 Quantum errors and Weyl Operators

In the classical setting the only errors were the so called position errors. Errors were elements of A^{n} that acted additively on words. In the quantum setting we have to worry about two types of error, position errors and phase errors. These errors are best explained using Weyl Operators.

First position errors. Consider the unitary operator U_{x}, x ∈ A, defined by U_{x} |a⟩ = |a + x⟩ for all a ∈ A. These operators corresponds to position errors. To understand phase errors we have to look at characters of A.

Given an abelian group (A, +, 0) we consider its group of characters (Â, ., 1). Let χ_{1} and χ_{2} be two homomorphisms from A to the unit circle S^{1} = {z : z ∈ ℂ and |z| = 1}. Define the product χ_{1}.χ_{2} to be the homomorphism that maps a ∈ A to χ_{1}(a)χ_{2}(a). The set of all such homomorphisms together with the product forms an abelian group (Â, ., 1) which is called the group of characters of A.

The character group Â is isomorphic to A. We now define an explicit isomorphism between A and Â. Let A be an additive abelian group. By the fundamental theorem of finite abelian group there exists h_{1}, …, h_{k} ∈ A of orders r_{1}, …, r_{k} respectively such that every element of a of A can be expressed as a sum x_{1}h_{1} + … + x_{k}h_{k}, 0 ≤ x_{i} < r_{i}. Fix a basis h_{1}, …, h_{k} for A. For any positive integer n let ζ_{n} = e^{\frac{2πι}{n}} be the primitive n^{th} root of unity. Consider an element a = ∑ x_{i}h_{i} of A. We define the element χ_{a} ∈ Â as follows:

χ_{a} (∑_{i=1}^{k} y_{i}h_{i}) = ∏_{i=1}^{k} ζ_{r_{i}}^{x_{i}.y_{i}}.

The map a ↦ χ_{a} is an isomorphism from the additive group A to the multiplicative group Â. There is nothing canonical about the isomorphism a ↦ χ_{a}. It depends on the basis we have chosen for A. From now on when we talk about χ_{a} we take for granted that an isomorphism from A to Â has been fixed and χ_{a} is the image of a under this isomorphism.

An important property of characters is the so called Schur’s orthogonality property.

Lemma 4.1 (Schur’s Orthogonality).

∑_{x∈A} χ_{x}(a) = \{ \begin{matrix}0 if a ≠ 0 \\ #A otherwise \end{matrix}  (1)

∑_{x∈A} χ_{a}(x) = \{ \begin{matrix}0 if a ≠ 0 \\ #A otherwise \end{matrix}  (2)

Here are some properties of characters that will be useful

Proposition 4.2. 1. χ_{a} · χ_{b} = χ_{a+b},

2. χ_{a}(b) = χ_{b}(a),

3. χ_{a}^{−1} = \overline{χ}_{a} = χ_{−a}.

We now define the unitary operator V_{a} as follows : V_{a} |b⟩ = χ_{a}(b) |b⟩. The operators U_{a} and V_{b} are called Weyl operators and satisfies the Weyl commutation relation: χ_{a}(b)U_{a}V_{b} = V_{b}U_{a}. We extend the Weyl operators to L^{2} (A)^{⊗^{n}} as follows. For any word a = a_{1} … a_{n}, U_{a} is the tensor product U_{a_{1}} ⊗…⊗U_{a_{n}}. Similarly V_{a} is the tensor product V_{a_{1}} ⊗ … ⊗ V_{a_{n}}.

Fourier transforms and Phase errors

To make phase errors V_{b} look less mysterious, we show that there is a natural interpretation of phase errors as position errors in the Fourier basis. Consider a character χ ∈ Â. Define the vector |χ⟩ in L^{2}(A) as follows: |χ⟩ = \frac{1}{\sqrt{#A}} ∑_{a∈A} χ(a) |a⟩. Using Schur’s orthogonality we can show that {|χ_{a}⟩ : a ∈ A} also forms a orthonormal basis for L^{2}(A). It is also easy to verify the following proposition V_{a} |χ_{b}⟩ = |χ_{a+b}⟩. This shows that V_{a} is nothing but position errors in the Fourier basis.

The unitary map F that performs the basis change |a⟩ ↦ |χ_{a}⟩ is called the Fourier transform which we denote by F. It is easy to see that F^{†}V_{a}F = U_{a}. If the abelian group A is the field 𝔽_{2} then the Fourier transform is the so called Hadamard matrix.

We denote the unitary matrix \overbrace{F ⊗ … ⊗ F}^{n}, the Fourier transform on L^{2} (A)^{⊗^{n}}, by F_{n}. It is easy to see that F_{n}^{†}V_{a}F_{n} = U_{a}.

5 The Error Group

Consider the Hilbert space H = L^{2}(A). Let B (H) denote the space of linear operators on H. The set B (H) is itself a Hilbert space with inner product ⟨A, B⟩ defined as Tr(A^{†}B).

Together with operator composition, which will be the multiplication, B (H) forms a ring (or in mathematical jargon a C^{∗}-algebra). Unitary operators form a multiplicative subgroup of B (H). The subgroup of unitary operators generated by the Weyl operators {U_{a}V_{b} : a, b ∈ A} is called the error group of the Hilbert space H. The importance of the error group comes form the following proposition.

Proposition 5.1. The error group E(H) forms an orthonormal basis for B (H)

The error group of L^{2} (A)^{⊗^{n}} is the group generated by {U_{a}V_{b} : a, b ∈ A^{n}}.

Let E be the error group of L^{2} (A)^{⊗^{n}}. Our model of quantum communication is as follows. The sender sends a message |ϕ⟩. The noise is modelled as an unknown U ∈ E that gets applied to |ϕ⟩. Recall that a quantum code C is a subspace of L^{2} (A)^{⊗^{n}}. Given a subset A ⊆ E an A-error correcting code is a quantum code that corrects errors arising from the set A, i.e. there should be a unitary operator U acting on L^{2} (A)^{⊗^{n}} ⊗ ℂ^{2}^{⊗^{m}} , for sufficiently large m, such that for any vector |ψ⟩ in C and U_{a}V_{b} ∈ A we have

U(U_{a}V_{b} |ψ⟩) ⊗ |0^{m}⟩ = |ψ⟩ ⊗ |ϕ_{a,b}⟩ .

The following criteria know as the Knill-Laflamme criteria can be used to check when a code C is a A-error correcting code [3].

Theorem 5.2 (Knill-Laflamme theorem). Let C be a code with an orthonormal basis |ψ_{0}⟩ , …, |ψ_{k}⟩. Let A be a subset of the error group then C is an A-error correcting code if and only if for all 0 ≤ i, j ≤ k and U, V ∈ A we have

⟨ψ_{i}| U^{†}V |ψ_{j}⟩ = \{ \begin{matrix}0 if i ≠ j \\ Γ(U^{†}V) otherwise \end{matrix}

where Γ(UV) is a function of UV independent of i and j.

Proof sketch. Let |ψ_{i}⟩, 1 ≤ i ≤ n be a basis for C. Let A = {U_{1}, … U_{M}}. Let H_{i} be the subspace spanned by U_{r} |ψ_{i}⟩, 1 ≤ r ≤ M. Let |ψ_{ij}⟩, 1 ≤ j ≤ n_{i}, be an orthonormal basis for H_{i}.

To prove that the condition is sufficient note that for i ≠ j, H_{i} is orthogonal to H_{j}. There exists a unitary operator acting on L^{2} (A)^{⊗^{n}} ⊗ ℂ^{2}^{⊗^{m}}, for some suitable m such that U |ψ_{ij}⟩ ⊗ |0^{m}⟩ = |ψ_{i}⟩ ⊗ |j⟩. This is the error correction operator.

To prove that the condition is necessary we assume that there is a error correction operator U acting on L^{2} (A)^{⊗^{n}} ⊗ ℂ^{2}^{⊗^{m}} such that for each |ψ⟩ ∈ C and U_{r} ∈ A we have

U(U_{r} |ψ⟩) ⊗ |0^{m}⟩ = |ψ⟩ ⊗ |ϕ_{r}⟩ .

We want to compute ⟨ψ_{i}| U_{r}^{†}U_{s} |ψ_{j}⟩. Note that

⟨ψ_{i}| U_{r}^{†}U_{s} |ψ_{j}⟩ = (⟨0^{m}| ⊗ ⟨ψ_{i}| U_{r}^{†})(U_{s} |ψ_{j}⟩ ⊗ |0^{m}⟩).

Since unitary operators preserve inner products we have

⟨ψ_{i}| U_{r}^{†}U_{s} |ψ_{j}⟩ = (⟨ϕ_{r}| ⊗ ⟨ψ_{i}|)(|ψ_{j}⟩ ⊗ |ϕ_{s}⟩) = ⟨ψ_{i}|ψ_{j}⟩ ⟨ϕ_{r}|ϕ_{s}⟩ .

This above expression is 0 if i ≠ j and is independent of i (is equal to ⟨ϕ_{r}|ϕ_{s}⟩) if i = j.

Intuitively two different basis |ψ_{i}⟩ and |ψ_{j}⟩ under errors U and V should continue to remain orthogonal for error correction to be possible. Remark. Let C be a code that can correct errors arising from the subset A = {U_{1}, …, U_{M}}. From the proof the Knill-Laflamme theorem we can assume a stronger condition on the error correcting algorithm (unitary operator). We can assume that there is a unitary operator U acting on L^{2} (A)^{⊗^{n}} ⊗ ℂ^{2}^{⊗^{m}} such that U(U_{r} |ψ⟩) ⊗ |0^{m}⟩ = |ψ⟩ ⊗ |r⟩ for all |ψ⟩ in C. From now on we will assume this stronger definition of error correcting operator.

To complete the analogy between classical error correction we also define error detection.

Definition 5.3. Let C be a quantum code with basis |ψ_{0}⟩ , …, |ψ_{k}⟩. We say that C can detect error U ∈ E if for all 0 ≤ i, j ≤ k we have

⟨ψ_{i}| U |ψ_{j}⟩ = \{ \begin{matrix}0 if i ≠ j \\ Γ(U) otherwise \end{matrix}

The intuition behind the definition is similar to that of the classical case. We want U |ψ⟩ be orthogonal to all ψ_{i} for the error to be detected. It is easy to see from Theorem 5.2 that C is a A-error correcting code if and only if it is a A^{†}A-error detecting code.

We now want to rephrase the Knill-Laflamme criteria in terms of the projection operator. Since any code is a subspace there is an associated projection operator P. The Knill-Laflamme criteria becomes

Theorem 5.4 (Knill-Laflamme). Let C be a code with P as its associated projection operator. The C is a A-error correcting code if for all U and V in A we have P U^{†}V P = Γ(U^{†}V)P.

Let C be a quantum code. The set of error operators detected by C, denoted by D(C), is the set

D(C) = {U ∈ E|P UP = Γ(U)P }.

Note that C is a A-correcting quantum code if and only if A^{†}A ⊆ D(C).

Let (a, b) ∈ A^{n} × A^{n}. We define the combined weight (which we will abbreviate as weight) as

w (a, b) = #{i|(a_{i}, b_{i}) ≠ (0, 0)}

For t ≤ n define A_{t} to be the subset {U_{a}V_{b}|w (a, b) ≤ t}. A t-error correcting code is an A_{t}-error correcting code. Given a quantum code C with projection operator P. By distance of C, written d(C) we mean the largest integer d such that D(C) ⊇ A_{d−1}. Analogous to Theorem 2.2 in the classical setting we have the following theorem.

Theorem 5.5. A quantum code C of distance d can detect d − 1 errors and correct ⌊\frac{d−1}{2}⌋ errors.

Sometimes it is more natural to use the projection operators while talking about a quantum code. Consider a quantum code C. Let P be the corresponding projection operator. Often when P is more natural to the discussion we will use P instead of C. For example we may use D(P) to denote the set of errors detected by C (i.e. the set D(C)). Similarly we may use d(P) to denote the distance of C.

6 The Calderbank-Shor-Stean code

We now give an example of a quantum error correcting code. This family is the so called Calderbank-Shor-Stean code or the CSS code for short. We pick two classical linear codes C_{1} and C_{2} such that C_{2} ⊆ C_{1}.^{1}

We first describe what linear codes. Fix a finite field 𝔽 say 𝔽_{2}. A linear code C of length n is a subspace of 𝔽^{n}. A linear code C is a [n, k, d] code if C is a subspace of 𝔽^{n} of dimension k and distance d. The minimal distance of a code is given by d(C) = min{w (w) : w ∈ C}.

For a code C let C^{⊥} denote the orthogonal complement of 𝔽^{n}. Let P be the projection operator into the vector space C^{⊥}. Then P usually called the parity check matrix for C. Note that P u = 0 for all code words u ∈ C.

The nearest neighbour decoding procedure of linear codes is quite elegant. On receiving a word m we want to decode it to the nearest code word. Let u be the nearest code word and let e = m − u. Since P annihilates u we have e = P m. We output the code word u by going over all words in C an outputting the nearest codeword to e. For a message m the word e = P m is called the syndrome. Often there are much more elegant algorithm to find the nearest codeword to the syndrome than the boring brute force algorithm. A challenging task is to come up with efficient codes where the brute force algorithm can be avoided.

We are now ready to describe the CSS construction for classical codes C_{1} and C_{2} over 𝔽_{q} such that C_{2} ⊆ C_{1}. If C_{1} is an [n, k_{1}]_{q} code and C_{2} is an [n, k_{2}]_{q} code then the constructed quantum code will be a q^{k_{1}−k_{2}} dimensional code. Also if C_{1} and C_{2}^{⊥} can correct t errors then the constructed code can also correct t quantum errors.

Consider the coset group C_{1}/C_{2}. For a coset x + C_{2} of C_{2} in C_{1} define |x + C_{2}⟩ as follows

|x + C_{2}⟩ = \frac{1}{\sqrt{#C_{2}}} ∑_{y∈C_{2}} |x + y⟩ .

Consider an error E = U_{a}V_{b} such that w (a) and w (b) are less than t. The error E on |x + C_{2}⟩ will give the following vector

1The CSS construction can be carried out for groups codes C_{1} and C_{2} over the alphabet. We leave this as an exercise for the reader.

E |x + C_{2}⟩ = \frac{1}{\sqrt{#C_{2}}} ∑_{y∈C_{2}} χ_{b}(x + y) |x + y + a⟩

The error correction is done in two stages. First the position errors are corrected and then the phase errors. Let H_{1} and H_{2} be the parity check matrix of C_{1} and C_{2}^{⊥} respectively. Let z ∈ 𝔽^{n} be any vector. We define the following unitary matrix

U_{p} |z⟩ ⊗ |w⟩ = |z⟩ |w + H_{1}z⟩

The unitary matrix U_{p} writes down the syndrome in the ancilla register which can now be used to correct error. The classical algorithm for the code C_{1} can be used to correct the position error by measuring the ancilla. This gives the vector

\frac{1}{\sqrt{#C_{2}}} ∑_{y∈C_{2}} χ_{b}(x + y) |x + y⟩

Now to correct the phase errors we can use the error correcting properties of C_{2}^{⊥}. We will use the fact that phase errors are position errors in Fourier domain. Applying the Fourier transform we get (I neglect the normalising factor)

∑_{y∈C_{2}} χ_{b}(x + y) ∑_{z} χ_{z}(x + y) |z⟩ .

This can be rewritten as

∑_{w} ( ∑_{y∈C_{2}} χ_{y}(w)) χ_{x}(w) |w − b⟩ .  (3)

Now (∑_{y∈C_{2}} χ_{y}(w)) is 0 unless w ∈ C_{2}^{⊥} in which case it is #C_{2}. The state is Equation 3 becomes

∑_{w∈C_{2}^{⊥}} χ_{x}(w) |w − b⟩ .

This is as if a position error of −b has occurred. Using the error correcting properties of C_{2} we can correct the error b just like the previous case. Applying the inverse Fourier transform we get be error corrected state.

7 Error correction in the general setting

A more general model of error correction is given through the density matrix formalism for quantum computation. For a quantum channel there is an underlying Hilbert space H. We assume that the sender send a state ρ. On sending a state ρ the receiver gets a state ∑ L_{i}^{†}ρL_{i} where L_{i}’s come from the some subspace A of B (H) such that ∑ L_{i}^{†}L_{i} is identity.

Consider n-fold tensor product H^{⊗^{n}}. A n sized code is a subspace of H^{⊗^{n}}. We say that C is a A-error correcting code if there exists a set of operators M_{1}, …, M_{n} such that for any collection L_{1}, …, L_{r} of operators in A with the property that ∑ L_{i}^{†}L_{i} = I, we have

∑_{i,j} M_{i}^{†}L_{j}^{†}ρL_{j}M_{i} = ρ

for any state ρ with support in C.

We now formalise t-error correcting codes in this model. We define the subspace A_{t} of B (H^{⊗^{n}}) to be the span of operators L which are of the form L_{1} ⊗…⊗L_{n}, L_{i} ∈ B (H) where all but t of the L_{i}’s are identity operator.

How does this model of error compare with whatever we have been talking about in the previous sections ? Is it sufficient to concentrate only on errors of the form U_{a}V_{b} ? We show that indeed this is the case.Without loss of generality we will assume that the Hilbert space H is L^{2}(A) for some additive abelian group A. We make use of the following theorem for Weyl operators.

Theorem 7.1. The collection of operators {U_{a}V_{b} : a, b ∈ A} forms an orthonormal basis for the space B (L^{2}(A)). Moreover an orthonormal basis for B (L^{2} (A)^{⊗^{n}}) is given by {U_{a}V_{b} : a, b ∈ A^{n}}.

It follows from Theorem 7.1 that the space A_{t} of t-errors is spanned by U_{a}V_{b} for a, b ∈ A^{n} of weight w (a, b) ≤ t. Consider a t-error correcting code A as defined in Subsection 5. There is an error correcting algorithm that we modelled as a unitary operator U. Consider a collection of errors L_{i} coming form A_{t}. Each L_{i} can be written as a combination of U_{a}V_{b}. Since U corrects each of the error U_{a}V_{b}, it can correct any linear combination of these errors. Hence it is sufficient to concentrate on the Weyl operators while designing codes. General errors, which are just linear combinations of these operators, will automatically be corrected by linearity.

There is an alternate way of looking at the above mentioned error model. The sender sends a state ρ. Since the channel is not completely isolated from the environment, which we model as a Hilbert space H_{env}, an unknown unitary operator U acts on the combined system H⊗H_{env}. However the receiver has access only to the H portion of the combined system and as a result the state he receives is that which is obtained by tracing out the H_{env} portion of the state. It can be shown that these formalisms are equivalent. Also if H is of dimension d, it is sufficient to consider environments of dimension at most d^{2}. This model, in some sense, is more satisfying from the physics point of view and turns out to be equivalent to the operator formalism.

In view of the discussion we had is this section, we will consider only errors of the type U_{a}V_{b} while designing codes. This simplifies the process of constructing and analysing quantum codes.

8 Stabiliser codes

There are certain quantum codes called stabiliser codes that have a neat description. As before the underlying Hilbert space is L^{2}(A) for some additive abelian group A. Codes of length n are subspaces of L^{2} (A)^{⊗^{n}}. We will use E to denote the error group associated with the L^{2} (A)^{⊗^{n}}.

Consider a subset A ⊆ E. Let C be the subset of vectors of L^{2} (A)^{⊗^{n}} that are stabilised by A, i.e. set of all |ψ⟩ in L^{2} (A)^{⊗^{n}} such that U |ψ⟩ = |ψ⟩ for all U ∈ A. It can be easily verified that C forms a subspace of L^{2} (A)^{⊗^{n}}. Moreover C is stabilised by all the elements in the subgroup of E generated by A. Codes that arise as subspaces stabilised by a subgroup S of E are called stabiliser codes (or sometimes additive codes). Let S be a subgroup of E. We will use C_{S} to denote the stabilised subspace of S. Elements of S are of the form ζU_{a}V_{b} for some root of unity ζ. Not all subgroups of E lead to nontrivial codes. We now look at conditions that S should satisfy so that C_{S} is nontrivial.

Theorem 8.1. Let S be a subgroup of the error group S and let C_{S} be the stabiliser code corresponding to it. For C_{S} to be nontrivial S should satisfy the following conditions:

1. For any nontrivial root of unity ζ, ζI ∉ S.

2. For any two roots of unity ζ and μ if both ζU_{a}V_{b} and μU_{a}V_{b} belong to S then ζ = μ.

3. The subgroup S should be abelian.

Proof sketch.

1. Let ζI ∈ S. For any vector |ψ⟩, ζI |ψ⟩ = ζ |ψ⟩ and hence for C_{S} to be nontrivial ζ = 1.

2. If ζU_{a}V_{b} and μU_{a}V_{b} belong to S then then ζ\overline{μ}I ∈ S and hence ζ = μ.

3. For any two U and V in E the commutator [U, V] = ζI for some root of unity ζ. Again from part 1 of the theorem we have the commutator subgroup [S, S] = {I}.

The above theorem gives the necessary conditions for S to give a nontrivial stabiliser subgroup. By a Gottesman subgroup of the error group we mean a subgroup S such that ζI ∉ S for all nontrivial root of unity ζ. From the proof of Theorem 8.1 it is clear that a Gottesman subgroup S satisfies all the properties of Theorem 8.1. We now show that any Gottesman subgroup leads to a nontrivial stabiliser code and derive a formula for the dimension of the code C_{S}.

Let S be a Gottesman subgroup of the error group and let Ŝ denote its character group. Consider any nontrivial character χ ∈ Ŝ. Define the operator P_{χ} as follows

P_{χ} = \frac{1}{#S} ∑_{s∈S} χ(s)s.

Lemma 8.2.

P_{χ_{1}}P_{χ_{2}} = \{ \begin{matrix}P_{χ_{1}} if χ_{1} = χ_{2}, \\ 0 otherwise. \end{matrix}

Proof sketch. Use Schur’s orthogonality (Lemma 4.1).

The above lemma, in particular, shows that P_{χ} is a projection operator. The following lemma gives the dimension of the subspace Img(P_{χ}).

Lemma 8.3. The dimension of Img(P_{χ}) is \frac{#A^{n}}{#S}.

Proof. The dimension of Img(P_{χ}) is given by T r(P_{χ}). Note that if a and b are elements of A^{n} such that (a, b) ≠ (0, 0) we have T r(U_{a}V_{b}) = 0. As a result T r(χ(s)s) = 0 for all s ≠ I in S. This shows that T rP_{χ} is \frac{1}{#S} T rI = \frac{#A^{n}}{#S}.

.

The Lemmas 8.2 and 8.3 implies that the projections P_{χ} “partition” the Hilbert space L^{2} (A)^{⊗^{n}} into orthogonal subspace, i.e. ∑_{χ∈Ŝ} P_{χ} = I. We can derive the dimension formula now.

Theorem 8.4. For a Gottesman subgroup S of E the stabiliser subspace C(S) is the image of the projection P (S) given by

P (S) = P_{1} = \frac{1}{#S} ∑_{s∈S} s.

Hence C_{S} is of dimension \frac{#A^{n}}{#S}.

Proof sketch. Consider any s ∈ S. We have sP_{χ} = χ(s)P_{χ}. Hence the subspace Img(P_{1}) is a subspace of C_{S}. To prove Img(P_{1}) is indeed C_{S} note that for any operator s ∈ S, Img(P_{χ}) is the eigen space corresponding to the eigen value χ(s). As a result there is no vector |ψ⟩ orthogonal to Img(P_{1}) such that s |ψ⟩ = |ψ⟩ for all s ∈ S.

Consider the homomorphism ϕ from E to A^{n} × A^{n} that maps ζU_{a}V_{b} to (a, b). It follows from Theorem 8.1 that ϕ restricted to S is an injection. Let S denote subgroup ϕ(S). For S to be abelian, it requires that for all a, b, c and d such that (a, b) and (c, d) lies in S, χ_{a}(d) = χ_{b}(c) holds. Together with Theorem 8.1 we have the following characterisation of stabiliser codes.

Theorem 8.5. Any Gottesman subgroup S of E is given by

S = {ρ(a, b)U_{a}V_{b}|(a, b) ∈ S}

where S is a subgroup of A^{n} ×A^{n} and ρ is a function from S to the unit circle in ℂ with the property that for all a, b, c and d such that (a, b) and (c, d) is in S the following condition should hold:

1. χ_{a}(d) = χ_{b}(d) and

2. ρ(a, b)ρ(c, d)χ_{b}(c) = ρ(a + c, b + d).

For a subgroup S of E by C (S) we denote the centraliser of S, i.e. the subgroup of elements of E that commute with every elements of S. For a Gottesman group S we have C (S) ⊇ S. The Knill-Laflamme criteria for stabiliser codes becomes a statement about the centraliser of S.

Theorem 8.6. Let S be a Gottesman subgroup of the error group E. The set of errors that C_{S} cannot detect is C (S) \ S.

Proof sketch. Let P = \frac{1}{#S} ∑_{s∈S} s be the projection operator corresponding to C_{S}. Let g be any element of E. The code C_{S} can detect g if and only if P gP = cP for some scalar c. It can be easily seen that if g ∈ S then P gP = P and if g ∈ E \ C (S) then P gP = 0 = 0P. It can also be seen that P gP for g in C (S) \ S cannot be written as cP for any scalar c. This is because P gP = gP^{2} = gP and since g ∈ C (S) \ S, the operators gP and P have disjoint support. This proves our theorem.

The above theorem leads to the following useful lemma.

Lemma 8.7. Let S be a Gottesman subgroup of the error group and let C_{S} be the corresponding stabiliser code. The distance of the code C_{S} is given by the minimum of w (a, b) over all a and b such that ζU_{a}V_{b} ∈ C (S) \ S.

9 Stabiliser codes over finite fields

In this section we deal with stabiliser codes over finite fields, i.e. quantum codes where the underlying Hilbert space is L^{2}(𝔽_{q}). One hopes that the rich algebraic properties of finite fields can be used to give succinct description of codes and would lead to efficient encoding and decoding algorithms.

We introduce some notations. For q = p^{l}, p a prime, by 𝔽_{q} we mean the unique finite field of cardinality q. We will be interested in quantum codes over L^{2} (𝔽_{q})^{⊗^{n}}. By ((n, r, d))_{q} we mean a quantum code over L^{2} (𝔽_{q})^{⊗^{n}} with distance d and dimension r. For codes with dimension a power of q, we use the notation [[n, k, d]]_{q} to denote a ((n, q^{k}, d))_{q} code over L^{2} (𝔽_{q})^{⊗^{n}}. The notation [[n, k, d]]_{q} is analogous to the notation [n, k, d]_{q} used to denote a n length linear code of dimension k and distance d over 𝔽_{q}.

Consider a nontrivial character ω of 𝔽_{q}. For an element a ∈ 𝔽_{q} define the character ω_{a} which maps x ∈ 𝔽_{q} to ω(ax). The mapping a ↦ ω_{a} is an isomorphism from 𝔽_{q} to its character group. Consider the group 𝔽_{q}^{n}. For a in 𝔽_{q}^{n}, let ω_{a} denote the map x ↦ ω(a^{T} x). Again the mapping a ↦ ω_{a} is an isomorphism from 𝔽_{q}^{n} to its character group. To study stabiliser codes over finite fields, we fix a finite field 𝔽_{q} and a nontrivial character ω of it. Let E be the error group associated with L^{2} (𝔽_{q})^{⊗^{n}}.

We can think of elements of 𝔽_{q}^{n} × 𝔽_{q}^{n} as vectors in 𝔽_{q}^{2n}. Any element u ∈ 𝔽_{q}^{2n} is of the form (a, b) for a and b in 𝔽_{q}^{n}. By U_{u} we mean the operator U_{a}V_{b}. We define the symplectic inner product ⟨⟨ , ⟩⟩ from 𝔽_{q}^{n} × 𝔽_{q}^{n} to 𝔽_{q} as follows: Given u = (a, b) and v = (c, d) in 𝔽_{q}^{n} × 𝔽_{q}^{n}, ⟨⟨u, v⟩⟩ = a^{T} d − b^{T} c

Theorem 8.5 takes the following form

Theorem 9.1. Any Gottesman subgroup S of the error group E is of the form

S = {ω(ρ(u))U_{u} : u ∈ S}.

where S is a additive subgroup of 𝔽_{q}^{n} ×𝔽_{q}^{n} satisfying the symplectic condition ⟨⟨u, v⟩⟩ = 0 for all u and v in S and ρ is a function from S to 𝔽_{q} such that for u = (a, b) and v = (c, d) in S we have ρ(u) + ρ(v) + b^{T} c = ρ(u + v).

Consider a subgroup S of 𝔽_{q}^{n} × 𝔽_{q}^{n}. Define the subgroup \overline{S} to be the set of vectors x such that ⟨⟨x, u⟩⟩ is zero for all u in S. The subgroup \overline{S} is the “orthogonal complement” of S under the symplectic inner product. Let S be a subgroup which together with a function ρ gives a Gottesman subgroup S as in Theorem 9.1. We have the following lemma on the distance of C_{S}.

Lemma 9.2. The subgroup \overline{S} contains S and the distance of C_{S} is the minimum of w (x), x in \overline{S} \ S.

Proof sketch. The result follows from the fact that the centraliser of S consists of elements of the form ζU_{x} for x ∈ \overline{S}.

The task of constructing stabiliser codes involves constructing subgroups S and ρ with the above mentioned properties. For a detailed account on how such an S and ρ can be constructed we refer the reader to [2] and [1]. Here we give two examples.

CSS code as stabiliser code

We show that the codes constructed by the CSS construction in Section 6 can be seen as a stabiliser code. Let C_{1} and C_{2} be linear codes over 𝔽_{q} of length n such that C_{1} ⊇ C_{2}. Recall that we have to construct a subgroup S of 𝔽_{q}^{n} ×𝔽_{q}^{n} and a function ρ satisfying the conditions of Theorem 9.1. It can be readily checked that if ρ is the constant function that takes value 1 and S is the set of all (a, b) such that a ∈ C_{2} and b ∈ C_{1}^{⊥}, the conditions are met. Define S defined as

S = {U_{a}V_{b}|a ∈ C_{2} and b ∈ C_{1}^{⊥}}.

The stabiliser code C_{S} is the required CSS code. Here we took S to be C_{2} × C_{1}^{⊥} and ρ to be the constant function that takes zero at all points.

Let C_{1} and C_{2}^{⊥} be [n, k_{1}, d]_{q} and [n, n − k_{2}, d] code respectively (i.e. C_{2} is a [n, k_{2}]_{q} code). Note that #S is q^{k_{2}}.q^{n−k_{1}}. As a result the dimension of C_{S} is q^{k_{1}−k_{2}} code. Also note that \overline{S} is nothing but C_{1} ×C_{2}^{⊥}. Hence \overline{S} \S consist of elements of weight at least d. In fact a stronger property holds, namely all the non-zero elements of \overline{S} have weight at least d. Such codes are called pure codes. A Gottesman subgroup S is called a d-pure subgroup if the centre C (S) does not contain any element of weight less than d. It is clear that a d-pure Gottesman subgroup yields a distance d stabiliser code C_{S}.

Laflamme code

We give the description of a [[5, 1, 3]]_{q} stabiliser code over 𝔽_{q} which is known as the Laflamme code. The smallest classical code that can correct one error requires at least 3 bit. In the case of quantum code the smallest code that can correct 1 qbit error requires at least 5 qbits (see [2]). For the case when q = 2 the Laflamme code is optimal.

Our base field is 𝔽_{q}. Let C be the subspace of 𝔽_{q}^{5} consisting of vectors (a_{1}, …, a_{5}) such that ∑ a_{i} = 0. Let L be the matrix

L = ( \begin{matrix}0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 \end{matrix} ) .

The matrix L is a so called circulant matrix. If σ denotes the cyclic shift then the rows of L are obtained by applying σ to the row vector (0, 0, 1, 1, 0). Let D be any matrix such that L = D + D^{T}, for example D is the upper triangular matrix whose upper triangle coincides with that of L. It can be easily verified that the subgroup S defined by

S = {ω(a^{T} Da)U_{a}V_{La} : a ∈ C}

is a Gottesman subgroup of the error group. We have chosen the set S to be {(a, Lb) : a ∈ C\} and the function ρ to be a^{T} Da. The dimension of the code is given by \frac{q^{5}}{q^{4}} = q.

To check that distance of C_{S} is 3 we have to verify that \overline{S} \ S had distance 3. The elements of \overline{S} consists of (x, y) such that a^{T} (y − Lx) = 0, i.e. y − Lx belongs to C^{⊥}. One can show that for (x, y) of combined weight 2 this cannot happen.

For the code to be a distance 3 code it was sufficient for \overline{S} \S not to contain elements of weight 2 or less. Also note that the Laflamme code is a 3-pure code.

10 Error correction algorithms for stabiliser codes

In this section we describe error correcting algorithm for quantum stabiliser codes. We will describe the error correcting algorithm for the case when the underlying abelian group is 𝔽_{q}. For codes over L^{2}(A) for abelian groups A, a similar algorithm can be devised. For the purpose of this section we assume that a Gottesman subgroup S is given. Let S = {ω(ρ(u))U_{u} : u ∈ S}. where S and ρ satisfies the conditions of Theorem 9.1. Recall that \overline{S} is “orthogonal complement” of S under the symplectic inner product ⟨⟨ , ⟩⟩. Although the construction of S involves choosing S and ρ with the desired properties, from the error correction point of view it is the subgroups S and \overline{S} that really matters. To simplify things, we assume that S is indeed a subspace of 𝔽_{q}^{n} × 𝔽_{q}^{n}.

Let d be the distance d(C_{S}) of the code C_{S}. This means that for all v ∈ \overline{S} \ S, w (v) > d. Let u_{1}, …, u_{k} be a basis for S. The unitary operators ω(ρ(u_{i}))U_{u_{i}} generate the Gottesman subgroup S. We have the following lemma

Lemma 10.1. For any vectors v_{1} and v_{2}, U_{v_{1}} U_{v_{2}} are in the same coset of C (S) if and only if for all 1 ≤ i ≤ k, ⟨⟨v_{1}, u_{i}⟩⟩ is equal to ⟨⟨v_{2}, u_{i}⟩⟩

Proof. Since u_{i}’s form a basis for S, if ⟨⟨v_{1}, u_{i}⟩⟩ equals ⟨⟨v_{2}, u_{i}⟩⟩ for all i then ⟨⟨v_{1}, u⟩⟩ equals ⟨⟨v_{2}, u⟩⟩ for all u in S. This implies that ⟨⟨v_{1} − v_{2}, u⟩⟩ = 0 for all u in S. As a result v_{1} − v_{2} is in \overline{S} which proves our lemma.

Assume that the sender sends |ψ⟩ and an unknown error U_{x} = U_{x_{1}}V_{x_{2}} occurred. We will give a quantum algorithm for error correction that can correct errors U_{x} for x of weight less than or equal to t = ⌊\frac{d−1}{2}⌋.

The received state is given by |ϕ⟩ = U_{x} |ψ⟩. For (a, b) in S, it is easy to see that |ϕ⟩ is an eigen vector of U_{a}V_{b} with eigen value ⟨⟨(a, b), (x, y)⟩⟩. We now give the error correction algorithm.

1. For each basis element u_{i} = (a_{i}, b_{i}) of S compute the eigen value of the operator U_{a_{i}}V_{b_{i}} corresponding to the vector |ϕ⟩ using Kitev’s phase estimation method. This gives us a sequence of k linear equations one for each basis element.

2. We solve this equation and find a solution of weight less than or equal to t.

3. Let the solution vector be v. The error corrected state is given by U_{v}^{†} |ϕ⟩.

To prove the correctness of the algorithm note that U_{x} and U_{v} are in the same coset of C (S) (by Lemma 10.1). Also since x and v are of weight less or equal to t we have w (x − v) ≤ d and as a result x−v ∈ S (because \overline{S} \S contains vectors of weight greater than d). This proves that U_{v}^{†} |ϕ⟩ = (U_{v}^{†}U_{x}) |ψ⟩ is nothing but ζ |ψ⟩. The correctness of the algorithm follows as the overall phase ζ can be neglected.

References

[1] V. Arvind and K. R. Parthasarathy. A family of stabilizer codes based on Weyl commutation relation over a finite field. Volume in honor of C.S. Seshadri’s 70th birthday, pages 133–153, 2003. Preprint quant-ph/0206174.

[2] Calderbank, Rains, Shor, and Sloane. Quantum Error Correction Via Codes Over GF(4). IEEETIT: IEEE Transactions on Information Theory, 44, 1998.

[3] Emanuel Knill and Raymond Laflamme. A theory of quantum error correcting codes. Physical Review letters, 84:2525–2528, 2000. Preprint quant-ph/9604034.

[4] J. H. van Lint. Introduction to Coding Theory, volume 86 of Graduate Texts in Mathematics. Springer-Verlag, New York Inc, 3^{rd} edition, 1998.