A quantum computer with 10 qubits is classically equivalent to $2^{10}$ bits. How is this equivalence worked out?
I understand that a single qubit is a vector in a 2-dimensional hilbert space, whose base we can label as $|0>$ and $|1>$.
So, 10 qubits will require a 20-dimensional hilbert space.
According to these notes by Preskill:
Any satisfactory description of the state of thequbits must characterize these nonlocal correlations, which are exceedingly complex. This is
why a classical simulation of a large quantum system requires vast resources.
(When such nonlocal correlations exist among the parts of a system, we say
that the parts are “entangled,” meaning that we can’t fully decipher the state
of the system by dividing the system up and studying the separate parts.)
Is there some way of quantifying this simply to get the classical equivalent of N qubits, is $2^N$?
Best Answer
By allowing the computer to exist as a probability of each of these states, as opposed to classical computer being set as one, we have a greater number of potential calculations performed, as multiple states can be acted on simultaneously. For a three qubit quantum computer we could have:
111 112 121 211 122 212 221 222
Giving us our $2^{3}=8$ states (n=3). This compares to a single state classical computer, which would require 8 bits to achieve this.
The reason it is $2^{n}$ is simply due to the two state qubit. There are qutrits and larger that rely on 3+ states and hence use higher dimension hilbert space. So a two qutrit computer would look like:
11 12 13 21 22 23 31 32 33
Now having $3^{2}=9$ states. Now our classical computer would require 9 bits.
As to the Hilbert Space, I believe that the 20 dimensions in your example are mapped onto two dimensions.