Single-sample distribution in Simon's algorithm
= Single-sample distribution in Simon's algorithm
{c}
If the hidden string is zero, one oracle-Hadamard run samples every $y\in\mathbb F_2^n$ with probability $2^{-n}$. If the hidden string is nonzero, it samples every $y$ satisfying $y\cdot p=0$ with probability $2^{-(n-1)}$ and every other string with probability zero. Pairing $x$ with $x\mathbin\oplus p$ makes the forbidden amplitudes cancel.