# What is size of the state space?

I'm taking my first Quantum Computing MOOC and the image below is from one of the very first slides:

My question is, what is the state space?

I've a guess that it is the set of all possible results that the gate can produce given a set of states. But this guess doesn't explain how classical state is linear in size of input or how quantum state is exponential in size of input.

Can you explain it with a worked-out example?

• I think the course should explain what it means by state space size. The picture explains nothing. I don't want to guess what the picture's author meant, though space size of $2^N$ hints a lot. Aug 2 at 14:13

I'd say that the slide is unfairly cryptic for a first introduction.

The point is a bit elaborate to make if you're new to quantum mechanics, however, fortunately, it's not difficult to understand. :)

Let's say you have a single classical bit. The possible states of this bit are $$0$$ and $$1$$.

On the other hand, when you have a single quantum bit, i.e., a qubit (i.e., the simplest possible quantum mechanical state), the possible states are $$\alpha\vert0\rangle+\beta\vert1\rangle$$ where $$\alpha,\beta\in\mathbb{C}$$ and $$\vert\alpha\vert^2+\vert\beta\vert^2=1$$. The $$\vert 0\rangle$$ and $$\vert 1\rangle$$ are mutually orthogonal vectors that represent the possible outcomes of a measurement of a spin$$-1/2$$ particle's spin-component in $$z$$ direction. If the state of a qubit is $$\vert 0\rangle$$ then it means that the value of its $$z-$$spin is $$1$$ and if the state of the qubit is $$\vert 1\rangle$$ then it means that the value of the $$z-$$spin is $$-1$$. However, if the state of the qubit is $$\alpha\vert 0\rangle+\beta\vert 1\rangle$$ (with $$\alpha,\beta\neq 0$$) then it means that the qubit simply does not have a definite $$z-$$spin. If we nonetheless measure its $$z-$$spin then we'll get $$\vert 0\rangle$$ as the output (i.e., the value of the $$z-$$spin being $$1$$) with a probability $$\vert\alpha\vert^2$$ and we will get $$\vert 1\rangle$$ as the output (i.e., the value of the $$z-$$spin being $$-1$$) with a probability $$\vert \beta\vert^2$$.

Thus, in order to represent a single qubit, you need $$2$$ complex amplitudes (with the constraint that the sum of their squared amplitudes is $$1$$). Similarly, if you have $$2$$ qubits then the possible states are $$\alpha\vert 00\rangle+\beta\vert 01\rangle+\gamma\vert10\rangle+\delta\vert11\rangle$$ with the constraint $$\vert\alpha\vert^2+\vert\beta\vert^2+\vert\gamma\vert^2+\vert\delta\vert^2=1$$. So, you need $$4$$ complex amplitudes to represent all possible states of $$2$$ qubits. In other words, a possible state of $$n$$ qubits is a linear superposition of all possible $$n-$$bit states. This linear superposition involves complex coefficients. Since there are $$2^n$$ possible states of $$n-$$bits, you need $$2^n$$ complex amplitudes to represent an $$n-$$qubit state. Let's say you limit the precision with which you represent a complex amplitude and you need $$p$$ bits to represent one complex amplitude. You still need $$p\cdot 2^n$$ bits to encode an $$n-$$qubit state. Whereas, you only need $$n$$ bits to encode an $$n-$$bit state.

So, the scaling is exponential in the number of qubits whereas it is linear in number of bits. This is what is meant when someone says something along the lines of what your slide says.

P.S.:

• It should be noted that the notion of a qubit is a bit more abstract and need not be tied with the spin of a spin$$-1/2$$ particle. There are various physical ways in which a qubit can be realized, e.g., as polarizations of a photon, as a two-level system in atoms, etc. However, the mathematical structure used to describe a qubit remains the same.

• The normalization constraint that the sum of the squared amplitudes of coefficients ought to be unity does not reduce the degrees of freedom by so much as to affect the scaling.