2
$\begingroup$

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

Improve this question
$\endgroup$
1
  • 7
    $\begingroup$ 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. $\endgroup$
    – Peter Shor
    Commented Jul 31, 2013 at 3:01

2 Answers 2

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ The poster juggles with numbers and words well, but is unable to provide an explanation. Why one bit per quantum state (= dimension of state vectors) is sufficient for an emulation? Why namely one bit, not another quantity of classical information? Why one should expect that multiplication of N × N unitary operators with reasonable precision has effectively ∼ N requirement for amount of information, not something less? All these points were missed. $\endgroup$
    – Incnis Mrsi
    Commented Oct 17, 2014 at 6:38
2
$\begingroup$

Intuitively speaking, the reason you'd expect quantum computers to take so much space classically is that a quantum state is a weighting of each possible classical state. With $n$ bits you have $2^n$ possible classical states, so you need $2^n$ weighting factors to represent the state of $n$ qubits... unless you find a way to be clever about it.

One way you can be clever is knowing that you're only dealing with a simple subset of the possible quantum states. For example, if you know you're dealing with non-entangled states, then you can factor things into $n$ complex weights. More commonly, your quantum state may be the output of a stabilizer circuit, and thus efficiently computable classically.

Another way you can be clever is by working through the weights incrementally, so you don't have to store them all at the same time. This takes a lot longer, though. Basically you can lay out the full sequence of matrix multiplications, then iterate through all the paths that can be multiplied together to contribute to one of the weights. Once you have that final weight, flip an appropriately weighted coin over whether to return it or to go to the next weight.

That's right, despite intuitively involving exponentially more values, BQPSpace is equal to PSPace.

Improve this answer
$\endgroup$
4
  • $\begingroup$ [B]asically the same number of classical bits? Dubious, because increasingly long chains of matrix multiplications will require increasingly high precision, otherwise rounding errors (or another kind of computational error) would make the result of the classical simulation irrelevant. $\endgroup$
    – Incnis Mrsi
    Commented Oct 16, 2014 at 14:02
  • 1
    $\begingroup$ @IncnisMrsi Good point. Quantum computers have to use error correcting codes to undo noise, so the classical simulation might get away with the same scheme and just use floats (the rounding error gets fixed by the noise correction)... Regardless, polynomial overhead is a lot better than the exponential people naively expect. $\endgroup$
    – Craig Gidney
    Commented Oct 16, 2014 at 15:13
  • $\begingroup$ BTW could any expert, better than me, improve a community answer physics.stackexchange.com/a/131922/56960 ? A misconception, of course, but not easy to debunk persuasively. $\endgroup$
    – Incnis Mrsi
    Commented Oct 20, 2014 at 7:25
  • $\begingroup$ @IncnisMrsi I don't know enough about physics-style entropy to clear it up. That being said, the computer-science-style entropy (i.e. message length) of an N-qubit state does increase past N as you apply non-trivial operations. You have to add bits to describe the operations; at least until you hit w 2^N bits and it's easier to just describe the weights. $\endgroup$
    – Craig Gidney
    Commented Oct 20, 2014 at 16:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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