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

Starting from $|0^n⟩|0^n⟩$, the first layer of Hadamard gates givesThe Boolean quantum oracle then givesUsing the Walsh-Hadamard transform identitythe final state is

When $z=0^n$, the function $f$ is injective, so the states $|f(x)⟩$ are distinct computational basis states and hence form an orthonormal set. Therefore, for arbitrary signs $\phi (x,y)$,

In the final state, the second-register amplitude vector associated with outcome $y$ isFor injective $f$, part (ii) says that its squared norm is $2^{-2n}{2}^n=2^{-n}$. By the Born rule for a product-basis measurement, every $y\in B_n$ is therefore observed with probability $2^{-n}$: the input register is uniformly distributed.

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.