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?

enter image description here

  • $\begingroup$ Out of curiosity, what book are you using? $\endgroup$ – Abhinav Feb 20 '15 at 12:07
  • $\begingroup$ An Introduction to Quantum Computing by Kaye, Laflamme, Mosca. $\endgroup$ – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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