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

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

• $H^{\otimes n} |0\rangle^{\otimes n}$ factorizes. You only need to consider a single tensor factor $H |0\rangle$ and take the $n$-fold product. E.g. $H^{\otimes 2} |0\rangle^{\otimes 2} = H |0\rangle \otimes H |0\rangle$. Note how every term appears when again tensoring with $H|0\rangle$. Sep 16 '19 at 19:55

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

• Right-hand side actually - left-hand side is already opened (the first and the second parts of the formula). You'll need to open the brackets in the tensor product of the sum and the single term to get the final expression. Sep 16 '19 at 22:41

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

• Amazing! thank you so much! Sep 16 '19 at 22:13