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:

enter image description here

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?

  • 1
    $\begingroup$ 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 $\endgroup$
    – glS
    Jun 23, 2021 at 8:24
  • 2
    $\begingroup$ And can you link to the paper where you found that probability so people can look at how it's derived? $\endgroup$
    – epelaez
    Jun 23, 2021 at 15:40

1 Answer 1


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


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.