Past exam of the mathematics course of the University of Cambridge / 2017 / iii / Paper 324 / 1

Use the positive-exponent quantum Fourier transform convention $F_N|x⟩=N^{-1/2}{\sum }_t{e}^{2\pi ixt/N}|t⟩$. The period of a function here is the least positive translation leaving the function unchanged on the cyclic group ${\mathbb{Z}}_N$. The injective promise means $f(x)=f(x^{\prime })$ exactly when $x\equiv x^{\prime }(\mathrm{mod}r)$. In particular $r\mid N$: the subgroup of period translations is generated by $r$, and wrapping the argument by $N$ preserves its value. This is exact quantum period finding on a finite cyclic group, rather than the truncated, nondividing-period version requiring continued fractions.

Prepare a uniform superposition state in the first quantum register using $F_N|0⟩$, and perform a reversible computation of the function into a second quantum register, cleaning its workspace by uncomputation:A quantum measurement in the computational basis of the second quantum register leaves a periodic coset state in the first:For the quantum Fourier transform of this periodic coset state, the finite geometric series vanishes unless the measured label is $t=mN/r$. On those labels its normalized amplitude is $r^{-1/2}{e}^{2\pi iam/r}$. Thus $m$ has the uniform distribution on a finite set on $\{0,\dots ,r-1\}$, irrespective of $a$.

Compute the greatest common divisor by the Euclidean algorithm, and set $q=N/\gcd (t,N)$, with $\gcd (0,N)=N$. Since $t=mN/r$,The exact period recovery from a Fourier sample is therefore certified by testing $f(q\mathrm{mod}N)=f(0)$. Every candidate $q$ divides $r$ and lies between $1$ and $r$, so the injective promise makes that equality equivalent to $q=r$. This includes $r=N$, where the test uses input $0$, and $r=1$, which always succeeds. The test does not assert that an arbitrary equality of function values certifies an arbitrary period; the Fourier-derived divisor restriction is essential.

The concise result isHere $\phi$ is the Euler totient function, with $\phi (1)=1$. The totient lower bound from the Mertens product gives $\phi (r)/r=\Omega (1/\max \{1,\log \log N\})$ for $r\le N$. Each trial uses polynomial time quantum Fourier transforms, function evaluations and Euclidean algorithm arithmetic in $\log N$. Repeating $O(\max \{1,\log \log N\})$ independent trials gives constant success probability; the herald accepts only correct answers.

The printed asymptotic bound has the wrong direction for this argument. In Big O notation, the stated upper bound on the number of coprime integers supplies no success lower bound and is itself false uniformly: for prime $N$, $\phi (N)=N-1$, not $O(N/\log \log N)$. Likewise the single-trial success need not be $O(1/\log \log N)$, since it tends to one for $r=N$ prime. The meaningful corrected guarantee is the lower bound above. If an upper-bounded success rate is literally required, one may deliberately retain an accepted result with an independent probability proportional to $1/\max \{1,\log \log N\}$; this discards useful successes and is unnecessary for efficient recovery.

First require $x\ne 0$. A discrete logarithm to a generator of a group of ${\mathbb{Z}}_p^{\ast }$ exists only for nonzero $x$; the printed membership $x\in {\mathbb{Z}}_p$ inadvertently also permits zero, for which $x^{-b}$ is undefined. Zero can be rejected before any quantum circuit.

Put $M=p-1$ and write $x=g^y$. Since $g$ is a generator of a group of order $M$, the map $k\mapsto g^k$ is a bijection from ${\mathbb{Z}}_M$ to the multiplicative group of a finite field. Hence every nonzero $c$ has a unique $k\in {\mathbb{Z}}_M$ with $c=g^k$. Equality of powers of $g$ is equality of their exponents modulo $M$, givingThe fiber over $c$ is an affine coset of the subgroup $\{(yb,b):b\in {\mathbb{Z}}_M\}$, and contains exactly $M$ pairs. This identifies the hidden subgroup problem underlying discrete-logarithm Fourier sampling; knowing $k$ numerically is not needed to construct the coset state.

Let $k_0$ be the unique discrete logarithm of the measured value $c_0$, so that $c_0=g^{k_0}$. The fiber calculation gives exactly the pairs $(yb+k_0,b)$ with $b\in {\mathbb{Z}}_M$, where $M=p-1$. The initial amplitude of each pair is $1/M$, so the Born rule assigns probability $M/M^2=1/M$ to this outcome.

After projective measurement and normalization, the first two quantum registers are in the coset stateThe measured third quantum register factors as $|c_0⟩$ and may be omitted. There is no loss of coherence between the $M$ terms in this post-measurement state: the quantum measurement reveals the common function value, not an individual input pair.

Apply the same positive-exponent quantum Fourier transform to each of the two quantum registers. The amplitude at $(c_1,c_2)$ of the coset state isThe finite geometric series is $M$ when $y{c}_1+c_2\equiv 0(\mathrm{mod}M)$ and zero otherwise. ThereforeThere are $M$ allowed pairs, with $c_1$ following the uniform distribution on a finite set. The factor $e^{2\pi i{k}_0{c}_1/M}$ changes the probability amplitudes by phases depending on the output label $c_1$, but has no effect on their probabilities. Using an inverse rather than forward quantum Fourier transform on both quantum registers gives the same support relation.

A modular inverse of $c_1$ exists precisely when $\gcd (c_1,M)=1$. In that case the discrete logarithm isIt cannot generally be determined from every allowed pair. Put $d=\gcd (c_1,M)$. The supported linear congruence has $d$ solutions modulo $M$, and determines only $y$ modulo $M/d$; $(0,0)$ gives no information when $M>1$. For instance $p=5$ and $(c_1,c_2)=(2,2)$ are compatible with both $y=1$ and $y=3$. One may verify a candidate by modular exponentiation, checking $g^y=x$. Repeated discrete-logarithm Fourier sampling finds an invertible $c_1$ with per-trial probability $\phi (M)/M$, which has the same totient lower bound from the Mertens product as before. When $p=2$, the group is trivial and $x=1,y=0$ are determined without Fourier samples.