Past exam of the mathematics course of the University of Cambridge / 2025 / ii / Paper 2 / 15C (Quantum Information and Computation)

The order of $a$ modulo $N$ is the least positive integer $r$ such thatIt exists because $a$ is a unit in the finite group $(\mathbb{Z}/N\mathbb{Z}{)}^{\times }$.

Defineusing the inverse of $a$ for negative $x$. Since $a^r\equiv 1$, $f(x+r)=f(x)$. Conversely, if $f(x)=f(y)$ then $a^{x-y}\equiv 1$, so the definition of order gives $r\mid x-y$. Two integers in the same block of $r$ consecutive integers cannot differ by a nonzero multiple of $r$. Hence $f$ is one-to-one within each period.

Since $r$ is even,The first factor is not divisible by $N$, since that would contradict minimality of $r$, and the second is not divisible by $N$ by hypothesis. Nevertheless their product is divisible by $N$. Thereforeand Euclid's algorithm computes a nontrivial factor. One can also compute $\gcd (a^{r/2}+1,N)$; together the two gcds expose factors lying on opposite sides of the congruence $a^{r/2}\equiv \pm 1$ modulo the prime-power divisors of $N$.

With the positive-exponent convention,The opposite sign convention is equivalent after conjugating all Fourier phases.

Put $Q=2^m$. Applying the transform term by term giveswhereThus, when $e^{2\pi iru/Q}\ne 1$,If the denominator vanishes, the continuous limiting value isThe magnitude is a Dirichlet-kernel peak near integers $u$ for which $ru/Q$ is close to an integer.

The assumed measurement estimate givesbecause $Q=2^m>N^2$. Since $(k,r)=1$, the fraction $k/r$ is reduced.

Suppose two distinct reduced fractions $k/r$ and $k^{\prime }/r^{\prime }$ with $r,r^{\prime }<N$ both obeyed $(\ast )$. ThenBut distinct reduced fractions satisfya contradiction. Hence at most one such fraction exists.

Here $N^2=441$, so the least power of two exceeding it is $Q=2^9=512$. The continued fraction iswhose convergents beginThe only nontrivial convergent with denominator below $N=21$ is $5/6$, and indeedThe uniqueness result therefore givesAs a check, $10^6\equiv 1(\mathrm{mod}21)$, while $10^2\not\equiv 1$ and $10^3\not\equiv 1$, so the order is exactly six.