How does $U_f$ act on a qudit state in the Deutsch-Jozsa Algorithm

Question

The problem starts with the given the input state $|\psi_{in} \rangle = |0 \rangle |1 \rangle$, I'm asked to calculate $|\psi'\rangle = H_d \otimes H_d |\psi_{in} \rangle$ where $H_d$ is the Hadamard gate for $d=4$ dimensional system.

$$H_d = \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1\\ 1 & -1 & 1 & -1\\ 1 & 1 & -1 & -1\\ 1 & -1 & -1 & 1 \end{pmatrix}$$ Well, $H_d|0\rangle = |0\rangle + |1\rangle + |2\rangle + |3\rangle$ and $H_d |1 \rangle = |0\rangle - |1\rangle + |2 \rangle - |3 \rangle$. So $|\psi'\rangle = H_d \otimes H_d |\psi_{in} \rangle = \frac{1}{4} \sum_{x,y=0}^{d-1} (-1)^{y} |x\rangle |y \rangle$. The problem suggests that the $\frac{1}{4}$ is not part of the new state, but I think it is.

Now the question I'm stuck on is using the unitary operator $U_f | x,y \rangle = |x, y \oplus f(x) \rangle$, show that $U_f|\psi'\rangle = \Big( \sum_{x=0}^{d-1}(-1)^{x} |x\rangle \Big) |1 \rangle_H$

$|1\rangle_H$ is not defined in the problem but I'm guessing it's equivalent to $H_d|1\rangle$

My problem is we don't know what $f(x)$ is, only that it might be constant or balanced. So why is $|y\rangle$ always transformed into $|1\rangle_H$?

Here, a function $f$ in $d$ dimensions is defined as constant if $f(0) \oplus f(1) \oplus \ldots \oplus f(d-1) = 0$ and it is balanced if $f(0) \oplus f(1) \oplus \ldots \oplus f(d-1) = \frac{d}{2}$ where $\oplus$ is addition mod $d$.

Answer 1

This is how I understand exercise 9.6 from the book.

Firstly note that

$$|1_H\rangle = |0\rangle - |1\rangle + |2\rangle -|3\rangle = \sum_{y = 0}^{d-1} (-1)^{y}|y\rangle$$

so let's write $|\psi'\rangle$ in a slightly different way:

$$ |\psi'\rangle = H_d \otimes H_d |01 \rangle = \sum_{x,y=0}^{d-1} (-1)^{y} |x\rangle |y \rangle = \sum_{x}^{d-1} |x\rangle |1_H \rangle $$

Here I drop the normalization factors ($\frac{1}{4}$ or $\frac{1}{2}$) like in the book. Also I assume that $f(x)$ is a binary function $f(x) = 0$ or $f(x) = 1$, and when we have this definition for $U_f$

$$U_f |x,y\rangle = |x,y \oplus f(x)\rangle$$

then

$$U_f |\psi'\rangle = \sum_{x}^{d-1} |x\rangle |1_H \oplus f(x)\rangle$$

If $f(x) = 0$, then $|1_H \oplus f(x)\rangle = |1_H \rangle$ and if $f(x) = 1$, then $|1_H \oplus f(x)\rangle = -|1_H \rangle$, so

$$U_f |\psi'\rangle = \Big( \sum_{x=0}^{d-1}(-1)^{f(x)} |x\rangle \Big) |1_H \rangle$$

Here I have a difference with the book. In the book instead of $(-1)^{f(x)}$ we have $(-1)^{x}$ that I guess is a typo in the exercise. If $f(x)$ is constant then it can be proved that either $f(x) = 0$ or $f(x) = 1$ always with the given definition for the constant functions and by taking into account my assumption that $f(x)$ is a binary function. So in the constant case:

$$U_f |\psi'\rangle = \Big( \sum_{x=0}^{d-1}(-1)^{f(x)} |x\rangle \Big) |1 \rangle_H = \pm\Big( \sum_{x=0}^{d-1} |x\rangle \Big) |1_H \rangle = \pm |0_H\rangle |1_H\rangle$$

And if we will apply an $H_d$ on the first qudit $H_d|0_d\rangle = |0\rangle$ we will always obtain $|0\rangle$.

If it's a balanced function with the given definition and the assumption that $f(x)$ is a binary function it can be proved that in the half cases (2) $f(x) = 0$ and in the other half cases (2) $f(x) = 1$, so

$$\sum_{x=0}^{d-1}(-1)^{f(x)} |x\rangle = \pm |1_H\rangle \text{ or } \pm |2_H\rangle \text{ or } \pm |3_H\rangle$$

In all cases if we will apply $H_d$ we will never obtain $|0\rangle$ after the measurement, so the measurement will indicate that we had a balanced function. Here I have used the definition from the exercise for $H_d$:

$$H_d |x\rangle = \frac{1}{\sqrt{d}}\sum_{y = 0}^{d-1} (-1)^{x \cdot y} |y\rangle$$

And hence $H_d^2|j\rangle = H_d |j_H\rangle = |j\rangle$, where $j \in \{0,1,2,3\}$.

In the end the author writes that "Finally, apply qudit Hadamard gates to the first set of qudits" and I don't see from where in the exercise the first qudit became quditS, but I imagine that it can be generalized in a similar fashion to the multiple input qudit case.