0
$\begingroup$

I am learning about quantum error correction which is for a part based on classical linear error correcting code.

There is a very basic answer on an exercice I do not understand. Here is the problem (From Nielsen & Chuang, page 450, exercice 10.25)

Let $C$ be a linear code. Show that if $x \in C^{\perp} $, then: $\sum_{y \in C} (-1)^{x.y} = |C|$ Show that if $x \notin C^{\perp}$, then: $\sum_{y \in C} (-1)^{x.y}=0$

I can show the first one using the definition, basically if $x \in C^{\perp}$ by definition $\forall y \in C$ I have $x.y=0$

Thus: $\sum_{y \in C} (-1)^{x.y} = \sum_{y \in C} (-1)^0 = |C|$ (where I assume that what is called $|C|$ is the number of element in the linear code which is $2^k$ if we want to encode $k$ bits an information right ?

However I don't understand the second one. Indeed, if $x \notin C^{\perp}$ then $x.y=1$ (We work with modulo 2 scalar product). And we have:

$$\sum_{y \in C} (-1)^{x.y}=\sum_{y \in C} (-1)=-|C|$$

Where is my mistake ?

In summary my questions are:

  • Do you agree with me that if we want to encode $k$ bits of info, then $|C|=2^k$
  • Why for $x \notin C^{\perp}$ $\sum_{y \in C} (-1)^{x.y}=0$
$\endgroup$
1
$\begingroup$

Suppose that $e_1, \ldots, e_k$ are (linearly independent) rows of the generator matrix of $C$. We can find vectors $e_{k+1}, \ldots, e_{n}$ s.t. $\{e_i\}_{i=1}^n$ is a basis in $\mathbb{F}_2^n$ (not necessarily orthogonal).

$\textbf{Claim 1.}$ $\exists i \in [k],$ s.t. $\langle x, e_i \rangle = 1$. Otherwise, for $\forall y \in C$ the inner product $\langle x, y \rangle = \sum_{i=1}^k \beta_i \langle x, e_i \rangle = 0,$ where $y = \sum_{i=1}^k\beta_ie_i$ is the basis decomposition of $y$ (all operations are modulo 2). Hence, the assumption that $x \notin C^{\perp}$ is incorrect.

Without loss of generality, $\langle x, e_1\rangle = \ldots = \langle x, e_s\rangle = 1$, $\langle x, e_{s+1}\rangle = \ldots = \langle x, e_k\rangle = 0$ for some $s \in [k]$.

Then $\langle x, y\rangle = \sum_{i=1}^s\beta_i$. The number of sequences $\{\beta_i\}_{i=1}^s$ of an even weight is the same as the number of odd-weight sequences, and it's equal to $2^{s-1}$, which concludes the proof.

$\endgroup$

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.