# The Simon's Algorithm, confusing equation

I'm approaching the Simon's Algorithm and have troubles with understanding a logic in an introduction.

Above the eq. 6.5.4 they introduce that set S which has 2 elements. As far as I understand, these are: n zeroes (0) and an arbitrary string of n [zeroes and ones] (s). As 6.5.4 suggests, the set S contains vectors which are 'forbidden' for the z (in the sum they indicate that z belongs to s perpendicular which is orthogonal to S). The idea behind introducing that subspace of S is to eliminate kets for which the phase is 0 (s$*$z=1). But if z takes 00..., the bitwise inner product with anything is 0 and it seems to be what we want, so why is it in the 'forbidden' set S?

Could you please bring me back on the right track?

• Out of curiosity, what book are you using? – Abhinav Feb 20 '15 at 12:07
• An Introduction to Quantum Computing by Kaye, Laflamme, Mosca. – Makaveli Feb 20 '15 at 12:12

Here, the idea behind introducing the subspace $S$ and its orthogonal complement $S^\bot$ was to show that all vectors on the RHS of equation 6.5.1 and 6.5.2 form a vector space of dimension $n-1$.

As you say, indeed, the zero vector $\mathbf{0}$ is a vector that we need, but you are wrong in saying that it is 'forbidden' because it appears in the subspace $S$.

Let's go over the definitions again: $S^\bot$ is the vector space in $\mathbb{Z}_2^n$ such that $$S^\bot = \{\mathbf{z} \in \mathbb{Z}_2^n | \mathbf{s}\cdot \mathbf{z} = 0 \}$$ This includes the zero vector since it satisfies the definition.

$S$ is the subspace that is orthogonal to $S^\bot$, and this is the set $\{ \mathbf{0}, \mathbf{s} \}$. Note that it includes the zero vector, because its scalar product with itself is 0. This is not surprising because all subspaces of a vector space must have the zero vector.

Ultimately, you can see that the entire vector space of $\mathbb{Z}_2^n$ breaks into two sets: one whose scalar product with $\mathbf{s}$ is 0, and another whose scalar product is 1. Both sets have the same number of elements, thus reducing the dimension of the RHS in 6.5.4 from $n$ to $n-1$.