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

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

• Please provide a reference to the source where the Deutsch-Jozsa algorithm was described with qudits. Jan 2 at 9:55
• This is exercise 9.6 in Quantum Computing Explained by David McMahon. The chapter describes the Deutsch-Jozsa algorithm on qubits (not qudits), but the exercise is a 3 part problem asking me to discover how the algorithm works on qudits Jan 3 at 6:40
• It is not true that $U_f|\psi'\rangle = \Big( \sum_{x=0}^{d-1}(-1)^{x} |x\rangle \Big) |1 \rangle$ in general. For example, if we set $f(x)=0$, then $U_f$ is identity and $U_f|\psi'\rangle = |\psi'\rangle = H_d|0\rangle \otimes H_d|1\rangle$, so the second qudit is in the state $H_d|1\rangle \ne |1\rangle$. Perhaps there is a missing Hadamard somewhere? Jan 3 at 22:39
• What is the codomain of $f$? $\{0, 1, 2, 3\}$? What does it mean for it to be balanced? What does $\oplus$ denote? Jan 3 at 22:42
• please try to be more specific on the question you are asking in the title of the post (e.g. what specifically do you want to know about "Deutsch-Josza Algorithm on qudit"?)
– glS
Jan 4 at 0:09

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.

• Wow, great explanation! He has lots of typos but part of my confusion was the independence of $f(x)$ in $U_f | \psi' \rangle$, so $(-1)^{f(x)}$ makes a lot of sense. Jan 5 at 0:38