On pg. 35 of Nielsen and Chuang, there's the following paragraph:

By checking the cases $x=0$ and $x=1$ separately we see that for a single qubit $H|x\rangle=\sum_x (-1)^{xz}|z\rangle/\sqrt{2}$.

I'm especially confused about its parts that involve $z$, such as why the power is $xz$ and what's the difference between $x$ and $z$. I can understand that the reason the denominator is $\sqrt{2}$ is due to $n=1$ in the summation part of the following formula: $$ |\psi_2\rangle=\sum_x \frac{(-1)^{f(x)}|x\rangle}{\sqrt{2^n}}\left[\frac{|0\rangle-|1\rangle}{\sqrt{2}}\right] $$

  • $\begingroup$ x is the input state index and z is the output state index. $\endgroup$ Sep 14, 2021 at 20:11

1 Answer 1


TLDR: These formulas have nothing to do with each other. The first one is the definition of the Hadamard gate, the other one the state we're left with after having applied $f$. In the latter, the $z$ comes from the application of the Hadamard gate.

These formulas are not linked. The first one simply describes that, for a single qubit state $|x\rangle$, we have: $$H|x\rangle=\frac{|0\rangle + (-1)^x|1\rangle}{\sqrt{2}}.$$ Indeed, we know that: $$H|0\rangle=\frac{|0\rangle + |1\rangle}{\sqrt{2}}$$ and: $$H|1\rangle=\frac{|0\rangle - |1\rangle}{\sqrt{2}}$$ Thus we can write: $$H|x\rangle=\frac{|0\rangle + (-1)^x|1\rangle}{\sqrt{2}}=\frac{1}{\sqrt{2}}\left[(-1)^{x\cdot 0}|0\rangle+(-1)^{x\cdot 1}|1\rangle\right]=\frac{1}{\sqrt{2}}\sum_z(-1)^{x\cdot z}|z\rangle.$$ Note that this formula is always true, it is not specific to the Deutch-Josza algorithm, but is a property/definition of the Hadamard gate.

The second formula describes the state just after we've applied the function $f$ to the state: $$\left|\psi_2\right\rangle=\frac{1}{\sqrt{2^n}}\sum_x(-1)^{f(x)}|x\rangle\left[\frac{|0\rangle-|1\rangle}{\sqrt{2}}\right]$$

What we want to do now is to apply an Hadamard gate on the first register. In order to do this, we can use the definition of the multi-qubit Hadamard gate which is given in the following paragraph and which can be seen as a generalization of the Hadamard gate for more than one qubit: $$H|x\rangle=\frac{1}{\sqrt{2^n}}\sum_{z}(-1)^{x\cdot z}|z\rangle$$ This is where $z$ comes from: from the application of the Hadamard gate. Using this definition, we can now compute $\left|\psi_3\right\rangle$ by linearity: $$\left|\psi_3\right\rangle=\frac{1}{\sqrt{2^n}}\sum_x(-1)^{f(x)}H|x\rangle\left[\frac{|0\rangle-|1\rangle}{\sqrt{2}}\right]$$ which is, according to the formula of $H|x\rangle$: $$\left|\psi_3\right\rangle=\frac{1}{2^n}\sum_x(-1)^{f(x)}\sum_z(-1)^{x\cdot z}|z\rangle\left[\frac{|0\rangle-|1\rangle}{\sqrt{2}}\right]$$ which is also equal to: $$\left|\psi_3\right\rangle=\frac{1}{2^n}\sum_z\sum_x(-1)^{x\cdot z+f(x)}|z\rangle\left[\frac{|0\rangle-|1\rangle}{\sqrt{2}}\right]$$ which is the state described by Nielsen and Chuang in equation (1.51).


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.