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

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.