I'm reading this paper and have a question about the computation to go from (3) to (4). Define the state $\vert\psi\rangle = \sum_b\alpha_b\vert b\rangle$.

In (3), we have the state

$$\sum_{b \in\{0,1\}} \alpha_b|b\rangle\left|x_{b, y}\right\rangle$$

where $b$ is a bit, $y$ is a bit string and $x_{b,y}$ is also a bit string determined by $b$ and $y$. If one applies the Hadamard to both registers, one obtains (according to (4))

$$\frac{1}{\sqrt{|\mathcal{X}|}} \sum_{d \in \mathcal{X}} X^{d \cdot\left(x_{0, y} \oplus x_{1, y}\right)} H|\psi\rangle \otimes Z^{x_{0, y}}|d\rangle$$

Can someone show exactly what happened here? My solution attempt is as follows. Using $H\vert x\rangle = \sum_y (-1)^{y.x}\vert y\rangle$, we get

$$H\otimes H\sum_{b \in\{0,1\}} \alpha_b|b\rangle\left|x_{b, y}\right\rangle = \sum_{d}\alpha_0\frac{1}{\sqrt{2}}(\vert 0 \rangle + \vert 1\rangle)(-1)^{x_{0,y}.d}\vert d \rangle + \alpha_1\frac{1}{\sqrt{2}}(\vert 0 \rangle - \vert 1\rangle)(-1)^{x_{1,y}.d}\vert d \rangle$$

I'm not sure how to proceed to obtain (4) although I see that you gather the $\vert d\rangle$ terms and manipulate the phase somehow.


1 Answer 1


This is a little fiddly to get right the first time. Let's start by rewriting eq (3) as $$ \sum_{b\in\{0,1\}}\alpha_b|b\rangle\otimes X^{x_{b,y}}|0\rangle. $$ Now, it probably helps to think of this $X^{b,y}$ operation as two steps: always apply $X^{x_{0,y}}$ and then, if the first qubit is in state $b=1$, apply $X^{x_{0,y}\oplus x_{1,y}}$.

Now you can apply the Hadamard transform. We have the relation $$ HX^p=Z^pH $$ First, let's just apply the Hadamard to the second register $$ I\otimes H\sum_{b\in\{0,1\}}\alpha_b|b\rangle\otimes X^{x_{b,y}}|0\rangle=\sum_{b\in\{0,1\}}\alpha_b|b\rangle\otimes Z^{x_{b,y}}\sum_d|d\rangle. $$ Let's think about that $Z^{x_{b,y}}$ operation again. Always apply $Z^{x_{0,y}}$ and then apply a phase $Z^{x_{0,y}\oplus x_{1,y}}$ if $b=1$. So that second part wants to introduce a minus sign if $b=1$ and $d\cdot (x_{0,y}\oplus x_{1,y})=1\text{ mod }2$. We can achieve this effect not by acting on the second system, but by acting on the first using $Z^{d\cdot (x_{0,y}\oplus x_{1,y})}$. Thus, after $I\otimes H$, we have $$ \sum_d\sum_{b\in\{0,1\}}\alpha_bZ^{d\cdot (x_{0,y}\oplus x_{1,y})}|b\rangle\otimes Z^{x_{0,y}}|d\rangle $$ In doing so, nothing depends on the $b$ index any more, so we can substitute back the original state $$ \sum_dZ^{d\cdot (x_{0,y}\oplus x_{1,y})}|\psi\rangle\otimes Z^{x_{0,y}}|d\rangle. $$ Finally, we can apply the first Hadamard, $H\otimes I$, to give $$ \longrightarrow \sum_dX^{d\cdot (x_{0,y}\oplus x_{1,y})}H|\psi\rangle\otimes Z^{x_{0,y}}|d\rangle. $$

  • $\begingroup$ That's a nice trick to remove the $b$ dependence from the phase! $\endgroup$
    – JRT
    Jan 22 at 12:26

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.