4
$\begingroup$

I'm a Computer Scientist undergrad student studying for an exam in Quantum computing. In all of the algorithms I have been studying (Deutsch–Jozsa, Simons, Shors, Grovers) I constantly see multi-qubit Hadamard gates being expended to the normalised sum of all the possible values like so:

$$\left|x\right>\xrightarrow{\mathbb H^{\otimes n}}\frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1}\left|x\right>$$

That makes complete sense to me, however, it's when they perform another hadamard transformation on that state that I get a bit confused with the $(-1)^{x·y}$ that gets multiplied with each part of the superposition like so:

$$\frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1}\left|x\right>\xrightarrow{\mathbb H^{\otimes n}}\sum_{x=0}^{2^n-1}\sum_{y=0}^{2^n-1}\left(-1\right)^{x.y}\left|y\right>$$ where

$$x.y = x_0y_0\oplus x_1y_1\oplus x_2y_2\oplus\ldots\oplus x_{n-1}y_{n-1}$$

I don't quite understand where this $(-1)^{x·y}$ has suddenly appeared from, or I don't have an intuition as to why it is required. My understanding was the performing one Hadamard after another kind of undoes the other?

Any intuition on this would be extremely helpful!

For a full reference I was triggered to ask here after seeing this happen in almost all the algorithms I mentioned above, but most recently here: Deutsch-Jozsa Algorithm

$\endgroup$
  • $\begingroup$ Another Hadamard transformation $H^{\otimes n}$ is applied after oracle $U_f$. Performing two $H^{\otimes n}$ in row would lead to initial state as $H^{\otimes n} H^{\otimes n} = I_n$. $\endgroup$ – Martin Vesely Jan 2 at 7:42
3
$\begingroup$

Your first formula is not correct. The correct formula for Hadamard gates for the arbitrary $|x\rangle$ from the calculational basis is (it can be proved by induction): $$H^{\otimes n}|x\rangle=\frac{1}{\sqrt{2^n}} \sum_{y=0}^{2n-1}{(-1)^{x\cdot y}}|y\rangle$$

where $x\cdot y=x_0y_0\oplus x_1y_1\oplus x_2y_2\oplus ...\oplus x_ny_n$

In case $|x\rangle = |0\rangle$ then $$x\cdot y =0\cdot y = 0$$ and $$H^{\otimes n}|x\rangle=H^{\otimes n}|0\rangle=\frac{1}{\sqrt{2^n}} \sum_{y=0}^{2n-1}{(-1)^{0}}|y\rangle=\frac{1}{\sqrt{2^n}} \sum_{y=0}^{2n-1}|y\rangle$$ in this case $$H^{\otimes n}H^{\otimes n}|0\rangle=H^{\otimes n}(\frac{1}{\sqrt{2^n}} \sum_{y=0}^{2n-1}|y\rangle)=\frac{1}{\sqrt{2^n}} \sum_{y=0}^{2n-1}H^{\otimes n}|y\rangle=$$ $$=\frac{1}{\sqrt{2^n}} \sum_{y=0}^{2n-1}(\frac{1}{\sqrt{2^n}} \sum_{z=0}^{2n-1}{(-1)^{z\cdot y}}|z\rangle)=\frac{1}{2^n} \sum_{y=0}^{2n-1}\sum_{z=0}^{2n-1}{(-1)^{z\cdot y}}|z\rangle=\frac{1}{2^n} \sum_{z=0}^{2n-1}\sum_{y=0}^{2n-1}{(-1)^{z\cdot y}}|z\rangle=\frac{1}{2^n} \sum_{z=0}^{2n-1}|z\rangle(\sum_{y=0}^{2n-1}{(-1)^{z\cdot y}})=\frac{1}{2^n} |0\rangle(\sum_{y=0}^{2n-1}{(-1)^{0\cdot y}})+\frac{1}{2^n} \sum_{z=1}^{2n-1}|z\rangle(\sum_{y=0}^{2n-1}{(-1)^{z\cdot y}})=\frac{1}{2^n} |0\rangle(2^n)+\frac{1}{2^n} \sum_{z=1}^{2n-1}|z\rangle(\sum_{y=0}^{2n-1}{(-1)^{z\cdot y}})=|0\rangle+\frac{1}{2^n} \sum_{z=1}^{2n-1}|z\rangle\cdot0=|0\rangle$$

In the same way it can be proved that: $$H^{\otimes n}H^{\otimes n}|x\rangle=|x\rangle$$

|improve this answer|||||
$\endgroup$
  • $\begingroup$ Thanks for the proof! I was also hoping for an intuition to why the (−1)x⋅y is there at all too? $\endgroup$ – Cascades Jan 2 at 16:49
1
$\begingroup$

The $(-1)^{x\cdot y}$ terms come from the matrix elements of $H^{\otimes n}$.

To see this, start from considering the matrix elements of $H$. You can check that they can be written as $H_{ij}=(-1)^{ij}$ where $i,j\in\{0,1\}$.

The matrix elements of $H^{\otimes n}$ are indexed by tuples of $n$ binary numbers, that is, writing $I\equiv (i_1,...,i_n), J\equiv(j_1,...,j_n)$, we have $$(H^{\otimes n})_{IJ} = \prod_{k=1}^n H_{i_k ,j_k} = \prod_{k=1}^n (-1)^{i_k j_k} = (-1)^{\sum_{k=1}^n i_k j_k} \simeq (-1)^{\boldsymbol i\cdot\boldsymbol j},$$ where in the last step we used the same notation as in the OP.

Note that I'm ignoring the normalisation factors here, so just add back the $1/2^{n/2}$ factors around as needed.

|improve this answer|||||
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.