Past exam of the introduction to quantum information course of the University of Oxford / 2015 / 1 / d / Solution

Apply the Hadamard transform to the conditional quantum state from c. Since $(x_k\oplus s)\cdot z=x_k\cdot z+s\cdot z$ modulo two, its output isIf $s\cdot z=1$, the two probability amplitudes cancel by destructive quantum interference. If $s\cdot z=0$, they add, givingThus every observed string obeys $\boxed{z\cdot s=0}$. This Simon Fourier sampling is uniform on the $(n-1)$-dimensional vector subspace $s^{\perp }$ over the two-element field. Indeed, the nonzero linear functional $z\mapsto z\cdot s$ has a kernel of dimension $n-1$ by the rank-nullity theorem. The distribution does not depend on $k$, so measuring or discarding the second quantum register gives the same statistics for the first.