Understanding (theoretical) computing power of quantum computers

Question

I am very new to quantum computing and just try to understand things from a computer scientist's perspective.

In terms of computational power, what I have understood,

100 ideal qubits ... can equate to [$2^n$ pieces of information]

Now Rigetti Computing has announced a 128 qubit computer.

Let's imagine they indeed release it next year.

This leads me to the following thoughts, please correct me if I am wrong:

• let's say hypothetically due to the noise about 28 qubits can't be taken into consideration (as used for the fault tolerance for example)
• that is, we could work with 100 qubits as in the example above.

Could we say then, we have an analog of von Neumann architecture i.e. say 64 qubits go for memory and 32 qubits for the instruction set (say remaining 4 are reserved).

Does this mean then (oversimplified!):

• we get 2^32 bits equivalent ~ 537 MB worth of "register bits" for CPU instructions, altogether with caches (no idea who might need that but could probably become a many-core "die" see for example Quantum 4004), compared to say 512KB=2^15 bits cache for one level on a classical computer

• and for "RAM", we get remaining 2^64 bits equivalent = 2.3 exabytes worth memory? (way more than current supercomputers have; Google had though reportedly total disk storage of 10 exabytes in 2013)

Answer 1

It isn't really like that, for a few reasons.

For the link saying "100 ideal qbits can equate to $2^{100}$ pieces of information", that's talking about logical qbits. Logical qbits are composed of many (perhaps hundreds or even thousands) of physical qbits entangled in a quantum error correction scheme, functioning together as a single qbit. So with 128 physical qbits maybe we can make a single sort-of-okay logical qbit.

Now, even if we had 100 perfect logical qbits, those $2^{100}$ pieces of information are not equivalent to $2^{100}$ classical bits. It's much easier to understand with math; here's a single qbit:

$|\psi\rangle = \begin{bmatrix} \alpha \\ \beta \end{bmatrix}$, where $\alpha, \beta \in \mathbb{C}$ and $|\alpha|^2 + |\beta|^2 = 1$

So with this single qbit, we do have $2^1=2$ "pieces of information" ($\alpha$ and $\beta$, actually called amplitudes). However, this doesn't mean we can store two classical bits of information in it. Rather, the amplitudes just encode the probabilities that the qbit will collapse to the classical bit 0 or 1 upon measurement; the probability it collapses to 0 is given by $|\alpha|^2$, and the probability it collapses to 1 is given by $|\beta|^2$. It's a bit more complicated than that because there are other ways we can measure it where it won't collapse to 0 or 1, but we won't worry about those here. The upshot is that at the end of the day, you can only get a single bit of classical information out of the qbit.

Let's look at two qbits. We represent multiple qbits with something called the tensor product, which is where the exponential growth comes in:

$|\phi_0\rangle \otimes |\phi_1\rangle = \begin{bmatrix} \alpha_0 \\ \beta_0 \end{bmatrix} \otimes \begin{bmatrix} \alpha_1 \\ \beta_1 \end{bmatrix} = \begin{bmatrix} \alpha_0\alpha_1 \\ \alpha_0\beta_1 \\ \beta_0\alpha_1 \\ \beta_0\beta_1 \end{bmatrix}$

When we measure these two qbits, $|\alpha_0\alpha_1|^2$ is the probability the system collapses to 00, $|\alpha_0\beta_1|^2$ to 01, $|\beta_0\alpha_1|^2$ to 10, and $|\beta_0\beta_1|^2$ to 11. So even though the number of amplitudes we have is growing exponentially (with three qbits there would be eight amplitudes), again at the end of the day you can only get out as many classical bits as you have qbits. This principle is also known as Holevo's bound.

If quantum computers don't get their speedup from storing & operating upon exponential numbers of amplitudes, where do they get it from? It's tricky to boil it down to a single thing. You should know this exponential growth property we're talking about (called the exponential size of the Hilbert space) is an important component, but isn't the full story. It's true that when we don't measure the qbits and continue to operate on them within the quantum computer, we indeed manipulate an exponential number of amplitudes at once. However, you have to be very clever when you do this, because at the end of the day you can only extract a very small number of classical bits from the system - you can never know the actual values of the amplitudes themselves - and so only very specific problems are amenable to speedup on a quantum computer.

If you're interested in learning more, I gave a video lecture on quantum computing aimed at computer scientists that you might enjoy.

Answer 2

100 ideal qubits ... can equate to [$2^n$ pieces of information]

This is really not the case. Taking an equivalent line from the same article:

To put this all into perspective, 100 normal bits just equals 100 pieces of information, while 100 ideal qubits (qubits we get in a computer simulation: they are perfect and are not influenced by external factors that influence a physical qubit) can equate to 1,267,650,600,228,229,401,496,703,205,376 pieces of information.

Simply, No. It looks a bit like this, but it's very misleading. This is no more true for a quantum computer than it is for a probabilistic classical computer where you describe the state at any moment in time by a set of $2^n$ probabilities. In both cases, if you measure the state, the maximum information you can retrieve (on average) is $n$ bits.

let's say hypothetically due to the noise about 28 qubits can't be taken into consideration (as used for the fault tolerance for example)

This isn't how error corrected computing (classical or quantum) works. For one level of error correction, you'll have to encode every logical qubit in 7 physical qubits (let's say). You'll get some improvement in the error rate, but you're already down to only have 18 useful qubits. But if that's not enough, you need a second level of error correction, so effectively you've got 1 logical qubit for every 49 physical qubits. So, you're down to 2 logical qubits. (If you have $k$ levels of error correction, then roughly speaking you need $7^k$ physical qubits per logical qubit, but the per-qubit error rate is doubly exponentially reduced.)

Your discussion of the structure of the (processor,RAM, etc.) is probably also not appropriate to the Rigetti device. Why do classical computers have hard drives, RAM, cache etc? We have a bunch of different technologies which all have different trade-offs in terms of speed of access, volatility of storage, capacity etc. A computer is a careful combination of all of these things to get the most cost effective, fast computation possible. But a device such as Rigetti's will have all the qubits essentially the same (there'll be some local variation depending on where they are on the chip, but this is a very small effect). There is no reason to split up the architecture in terms of RAM, cache, hard drive etc. These concepts only become relevant when you are interfacing several different hardware types.

Even if you were using the device in such a way then, to repeat a previous statement, you don't get to store $2^{128}$ bits of information, only 128 bits.

If you're looking for the source of a quantum speed-up, then think about classical computation in terms of universals sets of logic gates. For example, everything can be built out of NAND gates. If I suddenly gave you a new gate that cannot be built out of NAND gates, then suddenly you have a new tool that might, on a case by case basis, give you the potential to improve algorithms. This is basically what a quantum computer does.