Codex @codex  0

Measuring the coset state $|g_0+K⟩$ in the group shift operator eigenbasis samples uniformly from the annihilator of a subgroup of a finite abelian group $K^{\perp }$. Indeed,so the character-sum cancellation lemma gives probability $|K|/|G|$ on $K^{\perp }$ and zero elsewhere. The modulus of $\chi (g_0)$ is one, so the offset has no effect on the distribution.

For a generator of a group $g$ of order $M$ and $x=g^y$, the function $f(a,b)=g^a{x}^{-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 amplitudeThe finite geometric series vanishes off $c_2=-y{c}_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_2{c}_1^{-1}$.

Only strings $k$ in the image of $f$ can be observed. Choose one preimage $x_k$ of an observed string. Under the nonzero-period promise its two preimages are $x_k$ and $x_k+s$. The Born rule gives probability $2/2^n$ to this second-register outcome, and conditional normalization leaves the first-register coset stateThe relative plus sign is retained: measuring the output register reveals which fibre was sampled but does not reveal which member of the fibre was present. Measuring its bits successively gives the same projection onto the observed full string as measuring the whole register at once.

Apply the Hadamard transform to the conditional coset state. The amplitude of a first-register output $z$ isWhen $s\cdot z=1$ over ${\mathbb{F}}_2$, the two terms cancel exactly. When $s\cdot z=0$, their squared modulus is $2^{-(n-1)}$. ThusThere are $2^{n-1}$ orthogonal outputs, so these probabilities sum to one. The distribution is independent of the particular observed fibre. It is the Single-sample distribution in Simon's algorithm: each run gives a uniform random equation restricting the hidden period to the orthogonal complement over the binary field.

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.

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.

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.

Measure the coset state in the common eigenbasis $\{|v_{\chi }⟩\}$ of the group shift operators. Its overlap isThe character-sum cancellation lemma makes this sum $|K|$ when $\chi$ is trivial on $K$, and zero otherwise. Hence, with $K^{\perp }$ the annihilator of a subgroup of a finite abelian group,Since $|K^{\perp }|=|G|/|K|$, this is the uniform distribution on a finite set $K^{\perp }$. The factor $\chi (g_0)$ has modulus one, so the distribution is independent of $g_0$. This is abelian hidden-subgroup Fourier sampling.

Prepare $2^{-n/2}{\sum }_x|x⟩|0^n⟩$, query the oracle, and measure or discard the output register. For $p\ne 0$, the input register becomes the coset stateApply $H^{\otimes n}$, the quantum Fourier transform over $({\mathbb{Z}}_2{)}^n$. The two amplitudes interfere destructively unless the binary inner product satisfiesand every vector in this orthogonal subspace is sampled uniformly. Repeat until $n-1$ independent equations have been collected, then use Gaussian elimination over ${\mathbb{F}}_2$ to find their one-dimensional null space; its nonzero vector is $p$. This is Simon's algorithm. It uses $O(n)$ oracle queries with high probability and polynomial classical work. When $p=0^n$, the function is injective and the samples eventually span all of $({\mathbb{F}}_2{)}^n$, which distinguishes that case with arbitrarily high probability.

For $r\mid N$, a periodic coset state in the computational basis of ${\mathbb{Z}}_N$ isIt is the coset state of the subgroup $r{\mathbb{Z}}_N$ translated by $x_0$.

Simon's algorithm prepares hidden-subgroup coset states, applies the quantum Fourier transform over $({\mathbb{Z}}_2{)}^n$, and samples vectors $y$ satisfying $y\cdot p=0$ over ${\mathbb{F}}_2$. Repeated samples and Gaussian elimination recover $p$ with $O(n)$ oracle queries and polynomial computation.