Simon Fourier sampling
= Simon Fourier sampling
{c}
{title2=$\Pr(z)=2^{1-n}\mathbf1_{z\cdot s=0}$}
Apply the <Hadamard transform> to a <Simon coset state>. The <probability amplitude> of $|z\rangle$ is $2^{-(n+1)/2}(-1)^{x\cdot z}[1+(-1)^{s\cdot z}]$. Destructive <quantum interference> eliminates exactly those $z$ with $z\cdot s=1$. A <computational-basis measurement> therefore samples the <kernel> $s^\perp$ uniformly, independently of the representative $x$.