Why is Hilbert space considered especially large?

Question

In Nielsen & Chuang section 1.2 introduces multiple qubits and Hilbert spaces.

More generally, we may consider a system of n qubits. The computational basis states of this system are of the form $|x_1 x_2 ...x_n\rangle$, and so a quantum state of such a system is specified by $2^n$ amplitudes. For $n = 500$ this number is larger than the estimated number of atoms in the Universe! Trying to store all these complex numbers would not be possible on any conceivable classical computer. Hilbert space is indeed a big place. In principle, however, Nature manipulates such enormous quantities of data, even for systems containing only a few hundred atoms. It is as if Nature were keeping $2^{500}$ hidden pieces of scratch paper on the side, on which she performs her calculations as the system evolves. This enormous potential computational power is something we would very much like to take advantage of. But how can we think of quantum mechanics as computation?

Okay, but for a $n=500$ classical bits you still have $n$ amplitudes, just half as many as the quantum counterpart. And $2^{500}$ is still really huge. Does saying "Hilbert space is is a big place" (Carlton Caves) really mean anything on its own? What do I need to add to this to really differentiate from the classical counterpart?

Answer 1

There is no sense in which the classical and quantum state spaces are both exponential in the number of (qu)bits. That misconception comes from conflating two different notions of the "size" of the state space. Depending on how you think about it, either the classical space is linear and the quantum space is exponential, or the classical space is exponential and the quantum space is doubly exponential. In either case, the quantum space is exponentially larger than the classical space.

There are two different ways of quantifying the "size" of a state space:

1. The total number of possible states that a system can take on.
2. The number of bits of information required to uniquely specify the system's physical state.

The latter quantity is the logarithm (base 2, or another base if you're not using binary) of the former.

A system of $n$ classical bits can take on $2^n$ different possible values. Specifying the value of each of the $n$ bits by definition specifies the state of the $n$-bit system. So the "size" of the state space is $2^n$ according to the first definition and $n$ according to the second definition.

A quantum system of $n$ qubits is fundamentally different: it assigns an amplitude to each of the possible classical bitstring basis states. You don't have the constraint that every amplitude is zero except for one, as you do in the (deterministic) classical case. In "theoretical" quantum mechanics these amplitudes can be arbitrary complex numbers, so we need to provide an infinite amount of information to specify the state of even a single qubit. In order to facilitate counting, let's assume that these amplitudes are discretized to take on $d$ possible values. (The fact that they're complex rather than real isn't really relevant; we can just absorb that distinction into the definition of $d$.) Since each of the $2^n$ complex ampitudes can take on any of $d$ possible values, the total number of possible quantum states is actually a doubly-exponential $d^{2^n}$ by definition 1. If we want to talk about the number of bits required to completely specify a state (definition 2), then it's the log base two of that number, or $2^n \times \log_2 d$, which grows exponentially with $n$.

The point is that for any vector space (over a finite field), the total number of possible vectors is exponentially large in the dimension of the vector space. I personally think it's rather unfortunate that people tend to use the terms "size" and "dimension" of a vector space interchangeably, since to me it's more natural to think of the "size" of a vector space as referring to the number of distinct vectors, which is actually exponential in the vector space dimension (for a vector space over a finite field).

Answer 2

When you have $n$ qubits (or classical bits as well) you can represent $2^n$ basis states (or numbers in classical sense). Hence you need $2^{n+1}$ real numbers to desribe a quantum state of $n$ qubits (real and imaginary part of amplitude for each member of the state).

Consider for example $n=3$. In this case, 3 bits can represent numbers 000, 001, 010, 011, 100, 101, 110 and 111, i.e. eight values ($2^3$). The same is true for qubits. Again for 3 qubits you have eight basis states $|000\rangle, |001\rangle, |010\rangle, |011\rangle, |100\rangle, |101\rangle, |110\rangle$ and $|111\rangle$. And so on for $n=4$, $n=5$ etc.

So with increasing number of qubits, vectors describing quantum states dimension and dimension of matrices describing quatum gates increase exponentially.

EDIT: I based my answer on typo in question, so here is answer you probably looked for:

On classical computer you can operate with discrete bits, each described by its value eiher 0 or 1. However, quantum computer is more or less "continuous" because qubit is represented by vector $\begin{pmatrix}\alpha \\ \beta\end{pmatrix}$, where $\alpha,\beta \in \mathbb{C}$ (of course with condition $|\alpha|^2+|\beta|^2=1$). So you can save more information to a qubit than to a classical counterpart (in theory infinite amount) and process it.

However, when you measure a qubit, you get of course only one bit of information as the qubit collapses to either state 0 or 1. But before the measurement, qubit is in a superposition (and can be also entangled with another qubits) which gives quatum computer higher computational performance in many tasks in comparison with classiccal computer because of "bigger space for computation".

To conclude: I would say that saying about Hilbert space size refers to information processing before measurement. Because of "bigger size of space where computation is done" on quantum computer in comparison with classical one, quantum computer are faster (or at least equally fast).