# How are quantum computers more powerful than classical computers? [duplicate]

I feel the answer to this question is just out of reach - I "understand" the implication that a quantum computer uses all combinations of bits simultaneously compared to a classic computer, and that clearly gives a huge boost to processing times, however I'm struggling to quite grasp how.

I watched a TED talk on quantum computing in which the gentleman said that a 300 qubit QC would be more powerful than a regular PC with one bit of memory for every atom in the universe. They also mentioned that Google have created a QC with 53 qubits.

So to try and get my head around it, I decided to compare this to my PC.

Forgetting memory needed for anything other than storing combinations, if I have 16GB of RAM available, that's 217'179'869'184 possible combinations, or ~57 million lots of 53 bits (with each one in one specific combination).

So for each cycle of combinations, my PC is able to hold ~57 million combinations of 53 bits, and if my PC is running at 4.1GHz, that's 7.0E+19, or in the region of 266 combinations per second.

Now I have a good PC, but it seems to be reasonably on a par with Google's quantum computer, which just seems wrong. I know that I've not used an exact science to calculate things but I can't follow where I've screwed up the maths?

The claim for the 300 qubit QC I also can't follow with the above logic.

As excel won't work with stupidly large numbers I tried to do this on paper, so bear with me:

There are 10E+80 atoms in the universe, so this number of bits would give 2(10E+80), or 2800 combinations. An unholy number that no-one could possibly comprehend.

For the QC there are 300 qubits or ~28 therefore one could store 2792 combinations at any one time, which is already way above the 2300 combinations available to a 300 qubit QC..?

• Your laptop can only model ~17 billion bits of information at a time and is constrained to representing that information as bits. If you had 17 billion qubits, you could model 2 to the 17 billion bits of information, with each of the 2 to the 17 billion bit-strings having an associated probability. You can still only extract ~17 billion bits of information from those qubits (lookup Holevo's bound), but the exponential space allows you to do more – provided you have an algorithm that can locate a good solution to your computation from the exponentially large Hilbert space. Apr 13 '21 at 23:26

We can not talk about how quantum computers are much powerful than classical computers without mentioning other quantum phenomena like entanglement and interference. For a good comparison you can read this article.

Regarding you calculations, I think you did not get it right. Two classical bit can be either 00, 01, 10, or 11. Two qubits can have all the four possibilities simultaneously. Which means 2 qubits can carry 4 2-bits of information at the same time. That is 4 times what 2 bits can carry.

In general, $$n$$ qubits can carry $$2^n$$ times what $$n$$ bits can carry. $$300$$ qubits can carry $$2^{300}$$ $$300$$-bits binary strings. $$2^{300}$$ ~ 2e+90. That is more than the atoms in the observable universe.

There are 10E+80 atoms in the universe, so this number of bits would give 2(10E+80), or 2800 combinations. An unholy number that no-one could possibly comprehend.

Number of combinations does not matter, because at any moment a classical bit can be either one or zero. That means at any time 10E+80 atoms can carry 10E+80 bits.

• Which means 2 qubits can carry 4 2-bits of information at the same time. That is 4 times what 2 bits can carry. this is a standard misconception. An $n$-qubit system can store in a retrievable way the same amount of information a system of $n$ bits can. See e.g. physics.stackexchange.com/a/383044/58382
– glS
Apr 12 '21 at 12:22
• @glS, I'm talking here about the amount of information required to describe the qubits state, and can be manipulated by a quantum computer. The word "carry" is used by Scott Aaronson for the same in the article linked in my answer. Apr 12 '21 at 13:43
• he does use the word "carry", but notice how he doesn't say that the $n$ qubits "carry $2^n$ times what the $n$ bits can". He only says that they "carry an enormous amount of information", without specifying what that means exactly. You can say something on the lines of "a quantum computer manipulates $2^n$ numbers for an $n$-qubit system", but that's not the same as saying "$n$ qubits carry $2^n$ bits of information". The latter sentence is wrong in any interpretation by the way, because, if anything, an $n$-qubit system is characterised by $2^n$ complex coefficients, not binary ones
– glS
Apr 12 '21 at 14:01