2

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

Mozibur Ullah
  • 14,713

2 Answers2

2

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.

Folau
  • 568
2

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.

Craig Gidney
  • 7,172