Why does a bitwise product show up in Simon’s algorithm?

Question

I’m reading up on Simon’s problem from the Qiskit textbook, but don’t understand the second Hadamard transform of the first qubit register.

Mathematically, they are stating that a state that looks like this

$$ \frac{1}{\sqrt{2}} ( | x \rangle + | x \oplus b \rangle ) $$

Becomes this after a Hadamard transform

$$ \frac{1}{\sqrt{2^{n+1}}} \sum_{z \in \{0, 1\}^n} \left [ (-1) ^ { x \cdot z } + (-1) ^ {y \cdot z} \right ] |z\rangle $$

But I don’t see how at all that step was made. Can someone explain how the $x$ and $y$ jumped into the power, and somehow got the bitwise product operation performed on them?

These are the steps I am referencing

Answer 1

Can someone explain how the x and y jumped into the power, and somehow got the bitwise product operation performed on them?

It is helpful to write out a few examples to see what is happening.

1-bit Example: $$ H|0\rangle = \frac{1}{\sqrt{2}}|0\rangle + |1\rangle = \frac{1}{\sqrt{2}}\sum_z |z\rangle (-1)^{0\cdot z} $$ $$ H|1\rangle = \frac{1}{\sqrt{2}}|0\rangle - |1\rangle = \frac{1}{\sqrt{2}}\sum_z |z\rangle (-1)^{1\cdot z} $$

---

2-bit Example: $$ H|00\rangle = \frac{1}{\sqrt{2^2}}(|0\rangle + |1\rangle)(|0\rangle + |1\rangle) = \frac{1}{\sqrt{2^2}}(|00\rangle + |01\rangle + |10\rangle + |11\rangle) $$ $$ = \frac{1}{\sqrt{2^2}}\sum_z |z\rangle (-1)^{[00]\cdot z} $$

$$ H|01\rangle = \frac{1}{\sqrt{2^2}}(|0\rangle + |1\rangle)(|0\rangle - |1\rangle) = \frac{1}{\sqrt{2^2}}(|00\rangle - |01\rangle + |10\rangle - |11\rangle) $$ $$ = \frac{1}{\sqrt{2^2}}\sum_z |z\rangle (-1)^{[01]\cdot z} $$

$$ H|10\rangle = \frac{1}{\sqrt{2^2}}(|0\rangle - |1\rangle)(|0\rangle + |1\rangle) = \frac{1}{\sqrt{2^2}}(|00\rangle + |01\rangle - |10\rangle - |11\rangle) $$ $$ = \frac{1}{\sqrt{2^2}}\sum_z |z\rangle (-1)^{[10]\cdot z} $$

$$ H|11\rangle = \frac{1}{\sqrt{2^2}}(|0\rangle - |1\rangle)(|0\rangle - |1\rangle) = \frac{1}{\sqrt{2^2}}(|00\rangle - |01\rangle - |10\rangle + |11\rangle) $$ $$ = \frac{1}{\sqrt{2^2}}\sum_z |z\rangle (-1)^{[11]\cdot z} $$

---

You see that, whatever the starting ket in our six above examples, and whether the number of qubits $n$ is 1 or 2, the expression on the far RHS is always the same, namely: $$ H|x\rangle = \frac{1}{\sqrt{2^n}}\sum_z |z\rangle(-1)^{x\cdot z}\;. $$

You can convince yourself that this is quite reasonable since wherever we have a single $|0\rangle$ ket in the direct product of the starting ket we get a $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ and wherever we have a single $|1\rangle$ ket in the direct product of the starting ket we get a $\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$. So, we can only pick up (and must pick up) minus signs in the expansion of the direct product when we expand through a $|1\rangle$.

---

If you want to prove it, try induction.

Answer 2

You can simply use the definition of the Hadamard gate: $$H|x\rangle=\frac{1}{\sqrt{2^n}}\sum_z(-1)^{x\cdot z}|z\rangle$$ Thus, we have: $$\begin{align} H\left(\frac{1}{\sqrt{2}}\left(|x\rangle+|y\rangle\right)\right)&=\frac{1}{\sqrt{2^{n+1}}}\left[\sum_{z}(-1)^{x\cdot z}|z\rangle+\sum_{z}(-1)^{y\cdot z}|z\rangle\right]\\ &=\frac{1}{\sqrt{2^{n+1}}}\sum_{z}\left[(-1)^{x\cdot z}+(-1)^{y\cdot z}\right]|z\rangle \end{align}$$