Let $\mathcal{H}_{d}$ denote a $d$-dimensional state space with orthonormal basis $\left\{|y\rangle: y \in \mathbb{Z}_{d}\right\}$. For any $f: \mathbb{Z}_{m} \rightarrow \mathbb{Z}_{n}$ let $U_{f}$ be the operator on $\mathcal{H}_{m} \otimes \mathcal{H}_{n}$ defined by

$$U_{f}|x\rangle|y\rangle=|x\rangle|y+f(x) \bmod n\rangle$$

for all $x \in \mathbb{Z}_{m}$ and $y \in \mathbb{Z}_{n}$.

(a) Define $Q F T$, the quantum Fourier transform $\bmod d$ (for any chosen $d)$.

(b) Let $S$ on $\mathcal{H}_{d}$ (for any chosen $d$ ) denote the operator defined by

$$S|y\rangle=|y+1 \bmod d\rangle$$

for $y \in \mathbb{Z}_{d}$. Show that the Fourier basis states $\left|\xi_{x}\right\rangle=Q F T|x\rangle$ for $x \in \mathbb{Z}_{d}$ are eigenstates of $S$. By expressing $U_{f}$ in terms of $S$ find a basis of eigenstates of $U_{f}$ and determine the corresponding eigenvalues.

(c) Consider the following oracle promise problem:

Input: an oracle for a function $f: \mathbb{Z}_{3} \rightarrow \mathbb{Z}_{3}$.

Promise: $f$ has the form $f(x)=s x+t$ where $s$ and $t$ are unknown coefficients (and with all arithmetic being $\bmod 3)$.

Problem: Determine $s$ with certainty.

Can this problem be solved by a single query to a classical oracle for $f$ (and possible further processing independent of $f)$ ? Give a reason for your answer.

Using the results of part (b) or otherwise, give a quantum algorithm for this problem that makes just one query to the quantum oracle $U_{f}$ for $f$.

(d) For any $f: \mathbb{Z}_{3} \rightarrow \mathbb{Z}_{3}$, let $f_{1}(x)=f(x+1)$ and $f_{2}(x)=-f(x)$ (all arithmetic being $\bmod 3$ ). Show how $U_{f_{1}}$ and $U_{f_{2}}$ can each be implemented with one use of $U_{f}$ together with other unitary gates that are independent of $f$.

(e) Consider now the oracle problem of the form in part (c) except that now $f$ is a quadratic function $f(x)=a x^{2}+b x+c$ with unknown coefficients $a, b, c$ (and all arithmetic being mod 3), and the problem is to determine the coefficient $a$ with certainty. Using the results of part (d) or otherwise, give a quantum algorithm for this problem that makes just two queries to the quantum oracle for $f$.