Derivation of Equation 10.69 in Nielsen Chuang

Question

In the proof of correctness of CSS codes in Nielsen and Chuang, we see that equation $(10.68)$:

$$ \frac{1}{\sqrt{|C_2|}} \sum\limits_{y \in C_2} (-1)^{(x+y)\cdot e_2} |x+y \rangle $$

can be transformed to equation $(10.69)$ by applying Hadamard gates to each qubit to obtain:

$$ \frac{1}{\sqrt{|C_2|2^n}} \sum\limits_{z} \sum\limits_{y \in C_2} (-1)^{(x+y)\cdot (e_2+z)} |z \rangle $$

I am having difficulty to see how we can go from $(10.68)$ to $(10.69)$. Specifically, why $|x+y \rangle$ in equation $(10.68)$ is being transformed to $| z \rangle$, and why doesn't same apply to the exponent: That is in the exponent $x+y$ remains unchanged while in $(10.69)$ we take its dot product with $e_2 + z$ this time around.

It would be much appreciated if the answer explains the math behind it step-by-step.

Answer 1

It all comes down to the following useful fact about Hadamard gates; let $w$ be a bit string with $n$ digits

$$H^{\otimes n}|w\rangle = H^{\otimes n} |w_1 w_2...w_n\rangle = \bigotimes_{i=1}^n\frac{1}{\sqrt{2}}(|0\rangle+(-1)^{w_i}|1\rangle) = \frac{1}{\sqrt{2^n}}\sum_{z=1}^{2^n} (-1)^{w\cdot z}|z\rangle$$

The second equality comes from applying the Hadamard gate $H$ to each qubit $|x_i\rangle$. The third equality comes from expanding out the product, which contains all $2^n$ bit strings, and working out the phase in front of each $z$. Taking $w=x+y$ and plugging into your (10.68) gives (10.69) (which is missing a $1/\sqrt{2^n}$ factor I think).