2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I think you made a typo, as an $n$-qubit register requires $2^n$ amplitudes to specify, and not $2n$. Hence, specifying a 500-qubit state requires $2^{500}$ amplitudes, and not $n^{500}$ as you wrote. $\endgroup$ – Renaud Vilmart Mar 27 at 11:32
  • $\begingroup$ @RenaudVilmart typo fixed. Thanks $\endgroup$ – Alexander Soare Mar 27 at 11:35
  • $\begingroup$ What is classical qubit? $\endgroup$ – kludg Mar 27 at 11:48
  • $\begingroup$ @kludg it's another typo. Thanks $\endgroup$ – Alexander Soare Mar 27 at 11:52
  • $\begingroup$ Another typo: so a quantum state of such a system is specified by $2^n$ amplitudes. Not $2n$ but $2^n$ $\endgroup$ – kludg Mar 27 at 11:59
2
$\begingroup$

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).

| improve this answer | |
$\endgroup$
  • $\begingroup$ Great! Actually what threw me in N&C was "so a quantum state of such a system is specified by 2𝑛 amplitudes. For 𝑛=500 this number is larger than the estimated number of atoms in the Universe! ". This is true for both quantum and classical so I was left wondering why this part deserved an exclamation mark. I think your answer is telling me to ignore that though, and instead consider that an arbitrary qubit state needs infinite classical bits to describe it. At this point I'm still wondering though... the quoted paragraph seems unnecessary and misleading... $\endgroup$ – Alexander Soare Mar 27 at 16:45
  • $\begingroup$ @AlexanderSoare I don't really know that you mean - a classical system doesn't have any amplitudes. $\endgroup$ – tparker Mar 27 at 17:34
  • $\begingroup$ Ok. Thanks that sorted it for me. I was crossing some things over in my mind. Appreciate it! $\endgroup$ – Alexander Soare Mar 27 at 19:16
2
$\begingroup$

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).

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for this although I'm not sure it's tackling my question. I'm trying to understand why the paragraph is saying something special about qubits specifically vs classical bits. My point is exactly as you describe: their spaces both grow exponentially. Or did I miss something? $\endgroup$ – Alexander Soare Mar 27 at 11:39
  • $\begingroup$ @AlexanderSoare: Sorry, I based my answer on typo in question. Please see edited answer. Hope this is you are looking for. $\endgroup$ – Martin Vesely Mar 27 at 11:50
  • $\begingroup$ Thanks @Martin. That's helpful $\endgroup$ – Alexander Soare Mar 27 at 11:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.