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

For coprime integers $a,N$ with $N>1$, the multiplicative order of $a$ modulo $N$ is

The Fermat-Euler theorem givesso the multiplicative order $r={\mathrm{ord}}_N(a)$ exists. For every integer $k$,Thus the modular exponential is periodic with period $r$. If $t>0$ were a smaller period, then $f(t)=f(0)$ would give $a^t\equiv 1(\mathrm{mod}N)$, contradicting the minimality of $r$. Hence $r$ is its least positive period.

Modulo $33$,so ${\mathrm{ord}}_{33}(10)=2$. This order is even andThe factor extraction from an even modular order therefore givesThus

The quantum Fourier transform measurement supplies a rational approximationwhere $r$ is the desired multiplicative order. HereIts reduced continued fraction convergent has denominator two, so continued-fraction recovery in quantum order finding proposes $r=2$. Direct order verification from divisors confirms it:HenceAs a check, the classical final step of the Shor algorithm gives