Doubt in CSS error correction step

Question

At the end of page 3 in Simple proof of security of the BB84 QKD, the following equation (equation 4) is given : $$ \begin{array}{r} \frac{1}{2^{n}\left|C_{2}\right|} \sum_{z}\left[\sum_{w_{1}, w_{2} \in C_{2}}(-1)^{\left(w_{1}+w_{2}\right) \cdot z}\right. \left.\times\left|k^{\prime}+w_{1}+x\right\rangle\left\langle k^{\prime}+w_{2}+x\right|\right] \\ =\frac{1}{\left|C_{2}\right|} \sum_{w \in C_{2}}\left|k^{\prime}+w+x\right\rangle\left\langle k^{\prime}+w+x\right| \end{array} \tag{4} $$ where $z$ is used for phase error syndrome measurement and $x$ is for bit error syndrome measurement for the CSS code $Q_{x,z}$.

I am not sure how the equality of the above equation follows by averaging over $z$. Can you provide me with some argument or result that is used for the above equality?

Answer 1

We can think of an $n$-bit string as a "mask" that specifies a set of positions where the bit string is $1$. For an $n$-bit string $x$ denote with $s(x)\subset\{0, 1, \dots, n-1\}$ the set of positions where $x$ has a $1$.

The key observation is that the dot product $m\cdot z$ of $m$ with another $n$-bit string $z$ is zero when $z$ has an even number of $1$s on the positions in $s(m)$ and $m\cdot z$ is one when $z$ has an odd number of $1$s on the positions in $s(m)$. In other words,

$$ m\cdot z = |s(m)\cup s(z)|\mod 2. $$

Consequently,

$$ (-1)^{m\cdot z} = \begin{cases} +1&\text{if}\quad|s(m)\cup s(z)|\quad\text{is even}\\ -1&\text{if}\quad|s(m)\cup s(z)|\quad\text{is odd}. \end{cases} $$

Therefore,

$$ \sum_z (-1)^{m\cdot z}=\begin{cases} 2^n&\text{if}\,m=0\\ 0&\text{otherwise} \end{cases}\tag{a} $$

where the sum is over all $n$-bit strings. This can be seen by considering the two cases separately. If $m=0$ then $s(m)=\emptyset$ and each of the $2^n$ terms in the sum is $+1$. Now, if $m\ne 0$, then half of the terms in the sum correspond to $z$ with an even number of $1$s on positions in $s(m)$ and half of the terms correspond to $z$ with an odd number of $1$s on positions in $s(m)$. Therefore, all terms cancel and we end up with zero.

Finally, getting back to the sum in $(4)$, we note that we can break it up into two cases $w_1=w_2$ and $w_1\ne w_2$ and then use $(a)$. We get

$$ \begin{align} &\frac{1}{2^n|C_2|}\sum_z\sum_{w_1,w_2\in C_2}(-1)^{(w_1+w_2)\cdot z}|k'+w_1+x\rangle\langle k'+w_2+x|\\ =& \frac{1}{2^n|C_2|}\sum_{w_1,w_2\in C_2}\left(\sum_z(-1)^{(w_1+w_2)\cdot z}\right)|k'+w_1+x\rangle\langle k'+w_2+x|\\ =& \frac{1}{2^n|C_2|}\sum_{w_1,w_2\in C_2\\w_1\ne w_2}\left(\sum_z(-1)^{(w_1+w_2)\cdot z}\right)|k'+w_1+x\rangle\langle k'+w_2+x|\\ +& \frac{1}{2^n|C_2|}\sum_{w\in C_2}\left(\sum_z(-1)^{0\cdot z}\right)|k'+w+x\rangle\langle k'+w+x|\\ =& 0 + \frac{1}{2^n|C_2|}\sum_{w\in C_2}2^n|k'+w+x\rangle\langle k'+w+x|\\ =& \frac{1}{|C_2|}\sum_{w\in C_2}|k'+w+x\rangle\langle k'+w+x| \end{align} $$

as shown in the paper.