Take the 2-minute tour ×
Physics Stack Exchange is a question and answer site for active researchers, academics and students of physics. It's 100% free, no registration required.

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$?

share|improve this question
10 qubits require a 1024-dimensional Hilbert space. It's basis elements are $|0000000000\rangle$, $|0000000001\rangle$, $|0000000010\rangle$,$|0000000011\rangle$, $\ldots$, $|111111111\rangle$. Here $|0001010010\rangle$ is short for $|0\rangle\otimes|0\rangle \otimes|0\rangle\otimes |1\rangle\otimes|0\rangle \otimes|1\rangle\otimes|0\rangle\otimes|0\rangle\otimes|1\rangle\otimes|0\rangle‌​$. See equations 1.5 and 1.6 in Preskill's notes. –  Peter Shor Jul 31 '13 at 3:01
add comment

2 Answers

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.

share|improve this answer
add comment

This question is a bit more complicated than you might expect, because the number of bits you need depends on whether or not you care about how long the computation takes.

If you're willing to wait an amount of time that's exponentially longer than the quantum computer would take, then you can simulate a quantum computer with a classical computer that has basically the same number of classical bits as the quantum computer has qubits. That is to say: BQPSpace = PSPace.

(I think the trick is to represent the quantum computation as a chain of matrix multiplications. Instead of computing the intermediate matrices or states, which would take too much space, you slowly but surely iterate over all the ways each path through the matrices can contribute to the probability of a final state and return the state with that probability.)

Informally speaking, the reason quantum computers might take so much more space (we haven't actually proven this) is that their state is a weighting of each possible classical state. With $n$ bits you have $2^n$ classical states, so you need $2^n$ weighting factors to represent $n$ qubits (unless you're somehow clever about it).

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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