Simon's Algorithm Probability of Independence

Question

In this pdf for the Simon's algorithm we need $n-1$ independent $\mathbf y$ such that: $$ \mathbf y \cdot \mathbf s=0$$ to find $\mathbf s$. On page 6 of the pdf the author writes that the probability of getting $n-1$ independent values of $\mathbf y$ in $n-1$ attempts is: $$P_{\text{ind}}=(1-1/N(\mathbf s))(1-2/N(\mathbf s))\cdots (1-2^{n-1}/N(\mathbf s))\tag{1}$$ where $N(\mathbf s)=2^{n-1}$ if $\mathbf s \ne 0$ and $2^n$ if $\mathbf s=0$. Clearly then $P_{\text{ind}}=0$ for $\mathbf{s}\ne 0$ - which I believe to be wrong.

My question is, therefore: Is formula (1) wrong and if so what is the correct version. If it is not wrong how do we interpret $P_{\text{ind}}=0$ .

Answer 1

At first glance, the formula looks lightly wrong: the last term in the should only be $(1-2^{n-2}/N(s))$, giving $$ P_{ind}=\prod_{k=1}^{n-1}\left(1-\frac{2^{k-1}}{N(s)}\right) $$ overall. Thus every term is a half, or larger.

My reasoning is as follows: you perform a measurement and get a random outcome. The first time you do this, it can be any outcome except the all 0 string. This happens with probability $1-1/N(s)$.

The second time, you want any string except the all zeros, or the answer you got last time, $y_1$. Thus, the term $1-2/N(s)$.

The third time, you want any string except the all zeros, $y_1$, $y_2$ or $y_1\oplus y_2$. Thus, the term $1-4/N(s)$.

Once you have $k-1$ linearly independent strings $y_1$ to $y_{k-1}$ and you're trying top find the $k^{th}$, there are $2^{k-1}$ answers you don't want to get: the $2^{k-1}$ answers that are linearly dependent on the strings you already have (note that this counting includes the all zeros string). You keep going until the last term, $k=n-1$ because you're trying to find $n-1$ linearly independent cases.

Incidentally, this is not the way that I would ever make the argument. Who cares about the probability of needing exactly $n-1$ calls? You can just keep repeating as many times as you need to in order to find $n-1$ linearly independent strings. Since we've already argued that the worst-case probability of finding a new linearly independent string is 1/2, this means that, on average, no more than $2(n-1)$ trials would be required (and actually somewhat less, because early on you're far more likely to get a hit). You could also apply a Chernoff bound to prove that the probability of needing significantly more runs than that is vanishingly small. OK, that's essentially where the solution gets to, it just feels a little excessive (to me).