Prove by induction $H^{\otimes n} \left| 0 \right>^{\otimes n} = \frac{1}{\sqrt{2^n}} \sum_{i=0}^{2^n -1} \left| i \right>$

Question

Let H be the Hadamard operator. $$ H = (\left| 0 \right> \left< 0 \right| + \left| 0 \right> \left< 1 \right| + \left| 1 \right> \left< 0 \right| -\left| 1 \right> \left< 1 \right| )$$

prove that $$H^{\otimes n} \left| 0 \right>^{\otimes n} = \frac{1}{\sqrt{2^n}} \sum_{i=0}^{2^n -1} \left| i \right>$$

Now, it is evident that this works for $n=1$ and $n=2$, because we know that. $$ \left| 0 \right>^{\otimes 2} = \left| 0 \right> \otimes \left| 0 \right> = \left| 00 \right> $$ Then. $$ H^{\otimes2}\left| 00 \right> = (\left| 0 \right> \left< 0 \right| + \left| 0 \right> \left< 1 \right| + \left| 1 \right> \left< 0 \right| -\left| 1 \right> \left< 1 \right| )(\left| 0 \right> \left< 0 \right| + \left| 0 \right> \left< 1 \right| + \left| 1 \right> \left< 0 \right| -\left| 1 \right> \left< 1 \right| )\left| 00 \right>$$

$$H^{\otimes2}\left| 00 \right> = \frac{1}{2}(\left< 00 \right|\left| 00 \right>\left| 00 \right> + \left< 00 \right|\left| 00 \right>\left| 01 \right> + \left< 00 \right|\left| 00 \right>\left| 10 \right> + \left< 00 \right|\left| 00 \right>\left| 11 \right>)$$

$$H^{\otimes2}\left| 00 \right> = \frac{1}{2}(\left| 00 \right> + \left| 01 \right> + \left| 10 \right> + \left| 11 \right>) = \frac{1}{2}\sum^{3}_{i=0}\left| i \right> = \frac{1}{\sqrt{2^2}}\sum^{2^2 -1}_{i=0}\left| i \right> $$

But I do not know how to prove that it works for $n = k + 1$.

Any clue is very welcome, thank you in advance for your time and advice.

For more information about bra-ket notation, or the Hadamard operator you can consult those links.

Answer 1

To do the step of the induction, you assume that you've already proven that

$$H^{\otimes k} \left| 0 \right>^{\otimes k} = \frac{1}{\sqrt{2^k}} \sum_{i=0}^{2^k -1} \left| i \right>$$ (note the appropriate normalization factor).

Now, you have to consider $H^{\otimes k+1} \left| 0 \right>^{\otimes k+1}$:

$$H^{\otimes k+1} \left| 0 \right>^{\otimes k+1} = \big( H^{\otimes k} \left| 0 \right>^{\otimes k} \big) \otimes \big( H|0\rangle \big) = \big(\frac{1}{\sqrt{2^k}} \sum_{i=0}^{2^k -1} \left| i \right> \big) \otimes \frac{1}{\sqrt2}(|0\rangle + |1\rangle)$$

Once you open the brackets, you'll get $\sum_{i=0}^{2^k -1} \big( | i \rangle \otimes |0\rangle + | i \rangle \otimes |1\rangle \big)$, which is exactly $\sum_{i=0}^{2^{k+1} -1} | i \rangle$ (you'll see it if you write out the binary representations of the sum elements).

Answer 2

As pointed out in the comments, induction is not necessary here. You can simply notice that $$H^{\otimes n}|0\rangle^{\otimes n}\equiv\bigotimes_nH|0\rangle=\bigotimes_n|+\rangle\equiv|+\rangle^{\otimes n}\equiv|\underbrace{+,+,...,+}_n\rangle,\tag A$$ where $|+\rangle\equiv\frac{1}{\sqrt2}(|0\rangle+|1\rangle)$, and thus $$|+\rangle^{\otimes n}=\frac{1}{2^{n/2}}\sum_{i=0}^{2^n-1}|i\rangle.\tag B$$ At the last step we are observing that $|+\rangle^{\otimes n}$ is a balanced sum over all bitstrings of length $n$, which we can write as in the RHS, in which we identify $i$ with the bitstring equal to the $i$-th integer in binary notation.

---

Another way is to observe that the matrix elements of $H$ equal $\sqrt2 H_{ij}=(-1)^{ij}$. From this one can derive the matrix elements of $H^{\otimes n}$: $$(H^{\otimes n})_{I,J}=\prod_{k=1}^n (H)_{i_k,j_k}=2^{-n/2}\prod_{k=1}^n (-1)^{i_k j_k} =2^{-n/2}(-1)^{\sum_k i_k j_k}\equiv 2^{-n/2}(-1)^{I\odot J},$$ where $I\equiv(i_1,...,i_n), J\equiv (j_1,...,j_n)$, and $I\odot J\equiv\sum_k i_k j_k$. In other words, $I,J$ are bitstrings with components $i_k,j_k\in\{0,1\}$.

From this, we can see that $$H^{\otimes n}|0\rangle^{\otimes n}=\sum_I (H^{\otimes n})_{I,\underbrace{(0,...,0)}_{\equiv J}} |I\rangle =2^{-n/2}\sum_I (-1)^{I\cdot \boldsymbol 0}|I\rangle =2^{-n/2}\sum_I |I\rangle,$$ where $\sum_I |I\rangle$ is here just another way to write $\sum_{i=0}^{2^n-1}|i\rangle$.