Past exam of the mathematics course of the University of Cambridge / 2010 / iii / Paper 49 / 4

Put $N=2^n$ and label the binary digits of $x$ by $x_{n-1},\dots ,x_0$, with $x={\sum }_{j=0}^{n-1}{2}^j{x}_j$. The Walsh-Hadamard transform prepares the uniform quantum superposition $N^{-1/2}{\sum }_x|x⟩$. Applying the phase gate $R_a^{2^j}$ to the qubit for digit $x_j$ multiplies its basis amplitude by $\exp (2\pi ia{2}^j{x}_j/N)$. Taking their product givesWith the most significant qubit written first, this provesEach power is implemented by repeated uses of the supplied gate. The total is ${\sum }_{j=0}^{n-1}{2}^j=N-1$ uses. This realizes dyadic phase-gate identification without needing an unknown controlled gate or asserting a gate-call cost polynomial in $n$.

The inverse quantum Fourier transform in the original PDF has matrix elements $N^{-1/2}{e}^{-2\pi iky/N}$ multiplying $|y⟩⟨k|$. The converted TeX incorrectly repeats $y$ in the bra; using the actual PDF operator,If $y=a$, every summand of the inner sum is one, so it equals $N$. If $y\ne a$, let $q=e^{2\pi i(a-y)/N}$. Then $q\ne 1$ and $q^N=1$, and the finite geometric series gives ${\sum }_{x=0}^{N-1}{q}^x=(1-q^N)/(1-q)=0$. This is orthogonality of roots of unity. HenceA quantum measurement in the computational basis consequently returns the integer $a$ with probability one.

The eigenvalue on $|0⟩$ of every power is one, and its eigenvalue on $|1⟩$ is $e^{2\pi iak/N}$. ThusIf $a$ is odd, its greatest common divisor with $N=2^n$ is one. Divisibility can therefore be cancelled, givingIn particular, the $N$ powers with $0\le k<N$ are distinct. Each is the phase gate $R_m$ with $m\equiv ak(\mathrm{mod}N)$, and multiplication by $a$ is a permutation of these residue classes. Equivalently, for any desired $m$, choose $k\equiv a^{-1}m(\mathrm{mod}N)$, where $a^{-1}$ is the modular inverse. Then $R_a^k=R_m$, using the representative $0\le k<N$ and repeated forward applications only. Thus the powers generate the entire set. Once the preceding identification procedure has found $a$, these powers can also be labelled and selected classically.

Write the normalized qubit as $|\varphi ⟩=c_0|0⟩+c_1|1⟩$, with $|c_0{|}^2+|c_1{|}^2=1$. Only the $|1⟩$ amplitude changes between the two phase gates, soSince $|e^{i\delta }-1|=2|\sin (\delta /2)|\le |\delta |$,The phase-gate discretization error is uniform over all input states; its exact operator norm is $2|\sin (\delta /2)|$. To choose an approximating gate, round $N\theta /(2\pi )$ to the nearest integer and reduce it modulo $N$. Taking the shortest circular angle difference gives $|\delta |\le \pi /N$, and hence a uniform state-vector error at most $\pi /2^n$. The circular choice handles the identified endpoints $0$ and $2\pi$ correctly.