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.


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

  • $\begingroup$ you are right. I forgot the said factor. I edited the question. $\endgroup$
    – Josh
    Commented Apr 8, 2023 at 5:26
  • $\begingroup$ 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! $\endgroup$
    – Josh
    Commented Apr 8, 2023 at 5:30
  • $\begingroup$ Why does $|1\rangle$ have a factor of $(-1)^{w_i}$ while $|0\rangle$ always has a positive coefficient? $\endgroup$
    – Josh
    Commented Apr 8, 2023 at 5:32
  • $\begingroup$ 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$. $\endgroup$
    – user34722
    Commented Apr 8, 2023 at 5:40

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.