Past exam of the mathematics course of the University of Cambridge / 2020 / ii / Paper 3 / 15C / b / iv / Solution

Now let $z\ne 0^n$ and choose one representative $x$ from each pair $\{x,x\oplus z\}$. Since $f(x)=f(x\oplus z)$ andthe unnormalized second-register amplitude for outcome $y$ isIf $y\cdot z=1$, every paired contribution cancels, so the probability is zero. If $y\cdot z=0$, every coefficient has magnitude two. The $2^{n-1}$ distinct pair values give orthogonal states, so the squared norm before the overall $2^{-n}$ factor is $4\cdot 2^{n-1}=2^{n+1}$. The probability is thereforeThus one run samples uniformly from the $2^{n-1}$ strings in the orthogonal complement over the binary field $\{y:y\cdot z=0\}$, which is the sampling step in Simon's algorithm.