# Derivation of Equation 10.69 in Nielsen Chuang

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.

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).

• you are right. I forgot the said factor. I edited the question.
– Josh
Commented Apr 8, 2023 at 5:26
• Is there a reference that explains how the third and fourth equality obtained? I think these are the types of calculations that I have not seen before. Or if it is not too tedious, it would be appreciated if you could elaborate on them. Thanks!
– Josh
Commented Apr 8, 2023 at 5:30
• Why does $|1\rangle$ have a factor of $(-1)^{w_i}$ while $|0\rangle$ always has a positive coefficient?
– Josh
Commented Apr 8, 2023 at 5:32
• To your last question, that's just the definition of the Hadamard gate ($H|0\rangle = (|0\rangle+|1\rangle)/\sqrt{2}$, $H|1\rangle = (|0\rangle - |1\rangle)/\sqrt{2}$), which should be in Nielsen and Chuang. For understanding the last inequality in my answer, try working out an explicit example with two qubits, like $|w\rangle = |01\rangle$. Commented Apr 8, 2023 at 5:40