= Discrete-logarithm Fourier sampling
{title2=$c_2\equiv-yc_1\pmod M$}
For a <generator of a group> $g$ of order $M$ and $x=g^y$, the function $f(a,b)=g^ax^{-b}$ hides the <subgroup> $\{(yb,b):b\in\mathbb Z_M\}$ of $\mathbb Z_M^2$. Each <fiber> is an affine <coset> $\{(yb+k,b):b\in\mathbb Z_M\}$. Measuring the function register gives its normalized <coset state>. Applying the positive-exponent <quantum Fourier transform> to both input registers gives amplitude
$$
\frac{e^{2\pi ikc_1/M}}{M\sqrt M}\sum_{b=0}^{M-1}e^{2\pi ib(yc_1+c_2)/M}.
$$
The <finite geometric series> vanishes off $c_2=-yc_1$ and equals $M$ on that line. Thus each allowed output pair has <probability> $1/M$, independently of the coset offset. If $\gcd(c_1,M)=1$, a <modular inverse> recovers $y=-c_2c_1^{-1}$.
Back to article page
