Past exam of the mathematics course of the University of Cambridge / 2019 / ii / Paper 3 / 15D (Quantum Information and Computation)

Let ${\omega }_d=e^{2\pi i/d}$. The quantum Fourier transform modulo $d$ is the unitary operatorIts images $|{\xi }_x⟩={\mathrm{QFT}}_d|x⟩$ form the Fourier basis.

Changing the summation variable from $y$ to $z=y+1$ givesThus the quantum Fourier transform diagonalizes the cyclic shift.

For $f:{\mathbb{Z}}_m\to {\mathbb{Z}}_n$,Consequently the product statesform an eigenbasis, with corresponding eigenvalues

One classical query at any chosen $x_0$ returns only $v=s{x}_0+t$. Every possible slope $s\in {\mathbb{Z}}_3$ is compatible with that answer by choosing $t=v-s{x}_0$, so no one-query classical algorithm can determine $s$ with certainty.

For the quantum algorithm, let $\omega =e^{2\pi i/3}$ and preparePart (b) shows that the single query applies quantum phase kickback:The unknown intercept contributes only a global phase. Applying ${\mathrm{QFT}}_3^{-1}$ to the first register produces $|s⟩$, whose computational-basis measurement determines $s$ with certainty after one query.

Let $X|x⟩=|x+1⟩$ on the input register and let $N|y⟩=|-y⟩$ on the target register. Both are fixed unitary operators independent of $f$. Conjugating the query by the input shift givesbecause the intermediate query is made at $x+1$. Conjugating by target negation givessince $y\mapsto -y\mapsto -y+f(x)\mapsto y-f(x)$. Each construction uses $U_f$ exactly once.

Compose the two constructions in part (d) to obtainusing two queries to $U_f$. Forover ${\mathbb{Z}}_3$, the finite difference isThis is affine with slope $s_g=2a=-a$. Apply the one-query affine procedure from part (c) to the implemented oracle $U_g$. It returns $s_g$ with certainty, after which the fixed classical computationrecovers the quadratic coefficient. Since one use of $U_g$ consists of one use each of $U_{f_1}$ and $U_{f_2}$, the algorithm makes exactly two calls to the original oracle $U_f$.