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

  • 1
    $\begingroup$ Please provide a reference to the source where the Deutsch-Jozsa algorithm was described with qudits. $\endgroup$ Commented Jan 2, 2021 at 9:55
  • $\begingroup$ 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 $\endgroup$
    – jmacuna
    Commented Jan 3, 2021 at 6:40
  • $\begingroup$ 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? $\endgroup$ Commented Jan 3, 2021 at 22:39
  • $\begingroup$ What is the codomain of $f$? $\{0, 1, 2, 3\}$? What does it mean for it to be balanced? What does $\oplus$ denote? $\endgroup$ Commented Jan 3, 2021 at 22:42
  • $\begingroup$ 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"?) $\endgroup$
    – glS
    Commented Jan 4, 2021 at 0:09

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


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

  • $\begingroup$ 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. $\endgroup$
    – jmacuna
    Commented Jan 5, 2021 at 0:38

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.