# Use of the term "dimension" in this description of Simon's algorithm?

In Kaye, Laflamme and Mosca (2007) pg106 they write the following (in the context of Simon's algorithm):

...where $S=\{\mathbf{0},\mathbf{s}\}$ is a $2$-dimensional vector space spanned by $\mathbf{s}$.

this is not the only place I have seen this vector space referred to as "2-dimensional". But surely the fact that it is only spanned by one vector, $\mathbf{s}$, means (by definition) that it is only "1-dimensional"?

Am I missing something here or is the use of the term "dimension" different in this area?

More Context

As mentioned above the context is Simon's Algorithm. I.e. there exists a oracle $f:\{0,1\}^n\rightarrow \{0,1\}^n$ such that $f(x)=f(y)$ if and only if $x=y\oplus \mathbf{s}$ where $\mathbf{s}\in \{0,1\}^n$ and $\oplus$ is addition in $\Bbb{Z}_2^n$ (i.e. bit-wise). The aim of the algorithm is to find $\mathbf{s}$.

After applying a relevant circuit the output is a uniform distribution of $\mathbf{z}\in \{0,1\}^n$ such that $\mathbf{z}\cdot\mathbf{s}=z_1s_1+z_2s_2\cdots+ z_ns_n=0$. The statement I have quoted above is refering to the fact that since $\mathbf{0}$ and $\mathbf{s}$ are are solution to this problem you only need $n-1$ linearly independent vectors $\mathbf{z}$ to find $\mathbf{s}$.

Edit

The term is also used in the same context at the end of Pg 4 of this pdf (Wayback Machine version).

• can you add some context for the use of that sentence? What is $\boldsymbol s$, what is $\boldsymbol 0$, are you talking of real/complex vectors spaces, etc. Generally speaking, the dimension of the space in which a state lives is simply the number of different modes supported by the system
– glS
Apr 23, 2018 at 8:47
• @glS See my edit. Apr 23, 2018 at 9:04
• still, can you add the complete sentence from which that extract is taken from?
– glS
Apr 23, 2018 at 9:10
• @glS See my edit. I have posted a link to a pdf that says the same thing in the same context. The reason I have not added the complete sentence is because it does not add anything - it simply defines something that is not relevant to my question. Apr 24, 2018 at 5:39

In order to represent a '$\mathbf 0$' state as a vector in a Hilbert space, the '$\mathbf 0$' vector must in fact be non-zero. Thus, the label '$\mathbf 0$' is just a label for some designated vector (of norm 1) in our computational basis. This is obviously an abuse of notation, but it is a fairly common one. The more usual (and less confusing) notation would be $\left|0\right>$. This notation is even used on the wiki page about qubits.
Building this up from the ground: we have $n$ 2-dimensional vector spaces $V_i$, and we designate basis elements $\left| 0_i \right>$ and $\left| 1_i \right>$ in these vector spaces. Both these elements have norm 1. We then form the $2^n$ dimensional vector space $V = \bigotimes_{i=1}^n V_i$. We can designate a computational basis $\left| b_1 b_2 \ldots b_n \right>$ with $b_1,\ldots,b_n \in \{0,1\}$ for $V$. Within $V$ there are two vectors of interest: $\mathbf 0 = \left|00\ldots0\right>$ and $\mathbf s = \left| s_1 s_2 \ldots s_n \right>$, with $s_1, \ldots, s_n$ the bits of $s$. The vector space $S = \mathbf{\text{span}} \{\mathbf 0, \mathbf s\} \subset V$ is trivially 2-dimensional.