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

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.