Past exam of the mathematics course of the University of Cambridge / 2004 / iii / Paper 53 / 2 / 4 / Solution

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.