Quantum Computing Stack Exchange is a question and answer site for engineers, scientists, programmers, and computing professionals interested in quantum computing. It only takes a minute to sign up.
Sign up to join this community
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'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.
As you say, state space is the set of all possible results (if we are discussing the output of a function) or just the set of all possible states of a system. Normally, it is just a vector space of a particular dimension that can accommodate a full description of the (state of) system at any given time. (Sometimes, this is called configuration space.) This dimension is conventionally meant by the "size" of the system. So, to give a full description of the classical system of $n$ bits, you need to specify a value for each of them -- hence, the dimension is $n$ (and it grows proportionally, that is, linear in $n$). A quantum system of $n$ bits (qubits) requires, however, $2^n$ values -- one for each $|i_1 i_2 \dots i_n \rangle$, where $i_k \in \{0, 1\}$ -- to have a full specification of state (of the system). This is what is occasionally meant by the exponential in the number of qubits.
Here is a blog post that might be helpful. It's a good explanation of classical vs. quantum state spaces, and why the former is linear and the other exponential in the size of the register (i.e. the number of bits/qubits).
Here are some excerpts about classical state spaces:
In general, the state space of some (physical or logical) system is a vector space where each vector is a complete representation of the state of the system. The dimensions of the state space are, intuitively, the system’s “independent degrees of freedom”, so that defining a vector with a value in each dimension gives a faithful representation of state.
In the classical world, the state space for a computer with an N-bit register has one dimension for each bit, i.e. has dimension N. This is because each bit is an “independent degree of freedom”. That is, you can toggle a bit independently of the others, and describing the state of each bit describes the entire system.
The blog post goes on to explain how the postulates of quantum mechanics imply that the state space for a register of $N$ qubits has size $2^N$.
