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.

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.$$
• That's a nice trick to remove the $b$ dependence from the phase!