In this question you may assume the following fact about the quantum Fourier transform $Q F T \bmod N:$ if $N=A r$ and $0 \leqslant x_{0}<r$, where $A, r, x_{0} \in \mathbb{Z}$, then

$$Q F T \frac{1}{\sqrt{A}} \sum_{k=0}^{A-1}\left|x_{0}+k r\right\rangle=\frac{1}{\sqrt{r}} \sum_{l=0}^{r-1} \omega^{x_{0} l A}|l A\rangle$$

where $\omega=e^{2 \pi i / N}$.

(a) Let $\mathbb{Z}_{N}$ denote the integers modulo $N$. Let $f: \mathbb{Z}_{N} \rightarrow \mathbb{Z}$ be a periodic function with period $r$ and with the property that $f$ is one-to-one within each period. We have one instance of the quantum state

$$|f\rangle=\frac{1}{\sqrt{N}} \sum_{x=0}^{N-1}|x\rangle|f(x)\rangle$$

and the ability to calculate the function $f$ on at most two $x$ values of our choice.

Describe a procedure that may be used to determine the period $r$ with success probability $O(1 / \log \log N)$. As a further requirement, at the end of the procedure we should know if it has been successful, or not, in outputting the correct period value. [You may assume that the number of integers less than $N$ that are coprime to $N$ is $O(N / \log \log N)]$.

(b) Consider the function $f: \mathbb{Z}_{12} \rightarrow \mathbb{Z}_{10}$ defined by $f(x)=3^{x} \bmod 10$.

(i) Show that $f$ is periodic and find the period.

(ii) Suppose we are given the state $|f\rangle=\frac{1}{\sqrt{12}} \sum_{x=0}^{11}|x\rangle|f(x)\rangle$ and we measure the second register. What are the possible resulting measurement values $y$ and their probabilities?

(iii) Suppose the measurement result was $y=3$. Find the resulting state $|\alpha\rangle$ of the first register after the measurement.

(iv) Suppose we measure the state $Q F T|\alpha\rangle$ (with $|\alpha\rangle$ from part (iii)). What is the probability of each outcome $0 \leqslant c \leqslant 11$ ?