# Doubt in CSS error correction step

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?

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.