= Expected query count for Simon sampling
{title2=$\mathbb E T=\sum_{k=0}^{n-2}(1-2^{k-(n-1)})^{-1}$}
With a nonzero hidden period, <Simon's algorithm> samples uniformly from its $(n-1)$-dimensional <orthogonal complement over the binary field>. At rank $k$, a new sample raises the rank with probability $1-2^{k-(n-1)}$. Summing the geometric waiting times gives an expected $n-1+\sum_{j=1}^{n-1}(2^j-1)^{-1}<n+1$ queries. After $n-1+c$ samples, the probability of insufficient rank is less than $2^{-c}$, by a <union bound> over the nonzero linear functionals that could annihilate all samples.
Back to article page
