= Solution
{c}
An observed value $k$ must lie in the <image> of $f$. Choose either <preimage> $x_k$. The <two-to-one function> promise and $s\ne0^n$ imply that its <preimages> are exactly $x_k$ and $x_k\oplus s$. A <computational-basis measurement> of the second <quantum register> projects the joint <quantum state> onto the unnormalized vector
$$
2^{-n/2}\bigl(|x_k\rangle+|x_k\oplus s\rangle\bigr)|k\rangle.
$$
By the <Born rule>, $\Pr(k)=2^{1-n}$. Dividing by its square root gives the conditional first-register <pure state>
$$
\boxed{|\psi_k\rangle=\frac{|x_k\rangle+|x_k\oplus s\rangle}{\sqrt2}.}
$$
Choosing the other <preimage> merely interchanges the two summands. The result is a <Simon coset state>, retaining <quantum coherence> between the two inputs that share the measured function value. Outcomes outside the <image> have <probability> zero and hence no conditional state to normalize.
Back to article page
