= Solution
Apply the <Hadamard transform> to the conditional <coset state>. The amplitude of a first-register output $z$ is
$$
\frac{(-1)^{x_k\cdot z}+(-1)^{(x_k+s)\cdot z}}{\sqrt{2^{n+1}}}=\frac{(-1)^{x_k\cdot z}}{\sqrt{2^{n+1}}}\bigl[1+(-1)^{s\cdot z}\bigr].
$$
When $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)}$. Thus
$$
\boxed{\Pr(z)=\begin{cases}2^{-(n-1)},&z\cdot s=0,\\0,&z\cdot s=1.\end{cases}}
$$
There 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>.
Back to article page
