# Derivation of the effect of the Hadamard transform on a state |x⟩ in the Deutsch–Jozsa algorithm

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]$$

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

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