= Solution
{c}
Apply the <Hadamard transform> to the conditional <quantum state> from <1/c>. Since $(x_k\oplus s)\cdot z=x_k\cdot z+s\cdot z$ modulo two, its output is
$$
H^{\otimes n}|\psi_k\rangle
=\frac1{\sqrt{2^{n+1}}}\sum_z(-1)^{x_k\cdot z}\bigl[1+(-1)^{s\cdot z}\bigr]|z\rangle.
$$
If $s\cdot z=1$, the two <probability amplitudes> cancel by destructive <quantum interference>. If $s\cdot z=0$, they add, giving
$$
\boxed{\Pr(z\mid k)=
\begin{cases}
2^{1-n},&z\cdot s=0,\\
0,&z\cdot s=1.
\end{cases}}
$$
Thus \b[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.
Back to article page
