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.

  • 1
    $\begingroup$ $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$. $\endgroup$ Sep 16, 2019 at 19:55

2 Answers 2


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

  • $\begingroup$ 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. $\endgroup$ Sep 16, 2019 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$.

  • $\begingroup$ Amazing! thank you so much! $\endgroup$
    – MrKet
    Sep 16, 2019 at 22:13

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.