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?


1 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. $$


$$ (-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} $$


$$ \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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.