# Derivations of Equations (12.205 - 12.207) in Nielsen Chuang

While proving the security of the BB84 protocol, Nielsen and Chuang demonstrate that it is possible to reduce the CSS protocol to the secure BB84 protocol without requiring Alice to reveal the value of $$z$$. The relevant equations are (12.205 - 12.207):

$$\rho_{v_k,x} = \frac{1}{2^n} \sum\limits_{z} | \xi_{v_k,z,x} \rangle \langle \xi_{v_k,z,x} |$$ $$=\frac{1}{2^n |C_2|} \sum\limits_{z} \sum\limits_{w_1, w_2 \in C_2} (-1)^{z \cdot (w_1 + w_2)} | v_k + w_1 + x \rangle \langle v_k + w_2 + x |$$ $$=\frac{1}{|C_2|}\sum\limits_{w \in C_2} | v_k + w + x \rangle \langle v_k + w + x |$$

There are parts of this derivation that is not clear to me. For example, why can we drop $$2^n$$ in the last line? Where do $$w_1, w_2$$ come from? I am going to share my attempt, which is somewhat close to the derived answer but it is clearly wrong as I obtain a factor $$\frac{1}{2^n}$$ as opposed to $$\frac{1}{|C_2|}$$ in the last line.

Please let me know where I went wrong or what the correct derivation looks like.

My (Worng) Attempt

$$| \xi_{v_k,z,x} \rangle = \frac{1}{\sqrt{|C_2|}}\sum\limits_{w \in C_2} (-1)^{z \cdot w} | v_k + w + x \rangle$$

Therefore,

$$\rho_{v_k,x} = \frac{1}{2^n} \sum\limits_{z} | \xi_{v_k,z,x} \rangle \langle \xi_{v_k,z,x} |$$ $$= \frac{1}{2^n} \sum\limits_{z} \left[ \frac{1}{\sqrt{|C_2|}} \sum\limits_{w_1 \in C_2} (-1)^{z \cdot w_1} | v_k + w_1 + x \rangle \frac{1}{\sqrt{|C_2|}}\sum\limits_{w_2 \in C_2} (-1)^{z \cdot w_2} | v_k + w_2 + x \rangle \right]$$ Because of orthonormality of these states we get

$$= \frac{1}{2^n |C_2|} \sum\limits_{z} \sum\limits_{w \in C_2} (-1)^{z \cdot w} | v_k + w + x \rangle \langle v_k + w + x|$$

Then here we have to make use of Exercise $$10.25$$ that says if $$z \in C_2^\bot$$, then $$\sum\limits_{y \in C_2} (-1)^{z \cdot y} = |C_2|$$, otherwise, the sum is $$0$$. so then we get:

$$= \frac{|C_2|}{2^n |C_2|} \sum\limits_{w \in C_2} | v_k + w + x \rangle \langle v_k + w + x|$$ $$= \frac{1}{2^n} \sum\limits_{w \in C_2} | v_k + w + x \rangle \langle v_k + w + x|$$

I take it you mean $$\begin{eqnarray} \rho_{v_k,x} & = \frac{1}{2^n} \sum\limits_{z} \left( \frac{1}{\sqrt{|C_2|}} \sum\limits_{w_1 \in C_2} (-1)^{z \cdot w_1} | v_k + w_1 + x \rangle \right) \left( \frac{1}{\sqrt{|C_2|}}\sum\limits_{w_2 \in C_2} (-1)^{z \cdot w_2} \langle v_k + w_2 + x | \right) \\ & = \frac{1}{2^n |C_2|} \sum\limits_{z} \sum_\limits{w_1, w_2 \in C_2} (-1)^{z \cdot (w_1 + w_2)} | v_k + w_1 + x \rangle\langle v_k + w_2 + x | \end{eqnarray}$$ ?
In which case the only terms on the RHS that aren't going to come in self-cancelling pairs are when $$w_1 = w_2$$. And when $$w_1 = w_2$$ you will get the same term $$2^N$$ times (one for each value of $$z$$).

• If I understand correctly the statement "if $z \in C_2^\bot$, then $\sum\limits_{y \in C_2} (-1)^{z \cdot y} = |C_2|$" is not applicable in this case, because $w_1 = w_2 \Rightarrow w_1 + w_2 = 0 \Rightarrow (-1)^{z \cdot (w_1 + w_2)} = 1$. Is that correct?
• Yes, because it's a sum over $z \in \mathbb{Z}_2^n$ that identity doesn't help much. When $w_1 \neq w_2$ then for half of the $z$ you'll have $z\cdot(w_1 + w_2) = 0$ and the other half $z\cdot(w_1 + w_2) = 1$. Otherwise when $w_1 = w_2$ it's always $z\cdot(w_1 + w_2) = z \cdot 0 = 0$ like you say. Commented Apr 12, 2023 at 3:12