The Exercise

A linear code $C$ of length $n$ over a field $K$ is a subspace of $K^n$, the space of words of $n$ letters from $K$; its elements are the codewords, and $|C|$ is their number. The exercise concerns binary codes, $K = \mathbb{Z}_2$, whose words are strings of $n$ bits added position by position modulo 2.

Fix a word $x$ and give each codeword $y$ of a binary code the sign $(-1)^{x \cdot y}$, where $$x \cdot y = \sum_{i=1}^{n} x_i y_i$$(1) is the dot product, computed here modulo 2. The exercise asks for the sum of these signs over the whole code. Up to normalisation, that sum is the amplitude of $|x\rangle$ when $n$ Hadamard gates, $H^{\otimes n}$, act on the equal superposition $\sum_{y \in C} |y\rangle$ of the codewords.

The Dual Code

The dual code $C^\perp$ of a linear code $C$ of length $n$ over $K$ is the linear code of all words orthogonal to every codeword of $C$, with the dot product (1) computed in $K$: $$C^\perp = \{\, x \in K^n : x \cdot y = 0 \ \text{for all}\ y \in C \,\}.$$(2)^✦

The Claim

What Is Checked