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


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

  • 1
    $\begingroup$ 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 $\endgroup$
    – glS
    Apr 23, 2018 at 8:47
  • $\begingroup$ @glS See my edit. $\endgroup$ Apr 23, 2018 at 9:04
  • 2
    $\begingroup$ still, can you add the complete sentence from which that extract is taken from? $\endgroup$
    – glS
    Apr 23, 2018 at 9:10
  • $\begingroup$ @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. $\endgroup$ Apr 24, 2018 at 5:39

2 Answers 2


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.


The dimension of a vector space is the number of vectors that make up its basis.
For a qubit, there's two basis vectors: [ 1 0 ], and [ 0 1 ]. Therefore the dimension of the vector space is 2.

  • 1
    $\begingroup$ If you read the original question, the issue is not to do with qubits, but with the way that Kaye, Laflamme, and Mosca are using notation. (Having said that, the original title of the question was perhaps a bit confusing.) $\endgroup$ Sep 7, 2018 at 15:10

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.