# How is the probability of success for Simon's algorithm determined?

In step 3 of Simon's algorithm, we are told to "Repeat until there are enough such $$y$$’s that we can classically solve for $$s$$."

It then goes on:

The above are from this course notes.

I am not sure how this probability was calculated. Especially, why are there $$2^{n-1}$$ $$y$$'s such that $$y \cdot s = y_1s_1+y_2s_2 +\cdots y_ns_n = 0$$

I understand that there are n-1 non-trivial, linearly independent solutions to $$y \cdot s = 0$$, but how is $$2^{n-1}$$ obtained?

• it would be better if you could spell out (in the post, not in the comments) your current understanding of the algorithm. This helps people know where exactly your misunderstanding lies
– glS
Jun 23 at 8:24
• And can you link to the paper where you found that probability so people can look at how it's derived? Jun 23 at 15:40

It is a general fact from linear algebra that for a non-zero vector $$v$$ in an $$n$$-dimensional vector space $$V$$ the subset
$$A_v = \{u\in V \,|\, \langle u, v\rangle = 0\}$$
is an $$(n-1)$$-dimensional subspace of $$V$$. The fact can be proven easily by extending $$\{v\}$$ to an orthonormal basis.
Thus, in the specific case of the dot product $$y \cdot s$$ the subset $$A_s = \{y \,|\, y \cdot s = 0\}$$ is the $$(n-1)$$-dimensional vector space over $$\mathbb{F}_2$$.
Now, any two vector spaces of the same finite dimension over the same scalar field are isomorphic. Therefore, $$A_s$$ is isomorphic to $$\mathbb{F}^{n-1}_2$$ which consists of all binary sequences of length $$n-1$$. The isomorphism is a bijection, so $$|A_s| = |\mathbb{F}^{n-1}_2|$$. Conclusion follows from the fact that $$|\mathbb{F}^{n-1}_2|=2^{n-1}$$.