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$ .


1 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).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.