Simon independent-sample rank process

Fix integers $n\ge 1$ and $m\ge n-1$, and fix one total oracle $f:\{0,1{\}}^n\to \{0,1{\}}^m$ satisfying the Simon hidden-XOR-period promise, with its hidden nonzero mask $s$. Put $d=n-1$ and use the coordinate vector space ${\mathbb{F}}_2^n$ of The coordinate vector space over F2. Start with an empty ordered list of accepted rows and $V_0=\{0\}=\mathrm{span}(\mathrm{\varnothing })$. On each round, reset both registers and run a fresh One Simon Fourier-sampling sample for this same fixed oracle $f$. Its measurement outcomes are independent across these freshly initialized executions: every finite $R$-round history is an outcome in a finite probability space Finite probability spaces, outcome weights, events, and event probabilities with the product of its one-sample probabilities. Obtain its sample row $y$. At current rank $k$, let $V_k$ be the span of the $k$ accepted rows. If $y\mathrm{\notin }{V}_k$, append $y$ and set $V_{k+1}:={\mathrm{span}}_{{\mathbb{F}}_2}(V_k\cup \{y\})$; if $y\in V_k$, discard it and leave the list and span unchanged. Stop once the span has dimension $d$.

The sample law Simon samples uniformly from s-perp places every row in $s^{\perp }$, and The Simon annihilator is an (n−1)-dimensional binary subspace proves that this subspace has dimension $d$, so this stopping target is attainable and never exceeds the available rank. This is an unbounded rank-collection process, with one oracle query in every sampling round. Its probability and expected-query claims use finite prefix experiments as in Expected query cost from finite execution prefixes; a finite cap and failure output are specified separately.