Quantum Computers aren’t fast Computers

To understand why quantum computers aren’t just computers which run faster through some kind of „quantum magic“, we need to talk about their history and dip our toe in complexity classes. Don’t worry, it’s not that boring.

Quantum mechanics is weird. In fact, it is not even really mechanics. It is a mathematical concept developed in the 1920s to explain a series of strange phenomena, which itself introduced even more strange phenomena. Quantum mechanics is so weird that one of its most prominent founders, Albert Einstein, became the most prominent critic of his own theory. The amazing thing about quantum mechanics is that – even whilst being wildly unintuitive – it has lead us to stunning theories predicting our physical world with great accuracy. That’s why it is still around.

As it turns out, the weirdness of quantum mechanics can be used to our advantage. In 1982, Richard Feynman proposed that, in order to simulate quantum mechanics on a computer, the computer itself may as well make use of them. Fast forward a few years and some ridiculously smart people (David Deutsch, Lou Grover, Peter Shor and many more) figured out the first algorithms that could be run on a quantum computer and solve problems more efficiently than the best known classical counterpart.

You might have noticed the usage of the word efficiently in the last paragraph. This hints at a key concept in computer science. In a nutshell, a computation is efficient if the time it takes to complete it doesn’t blow up exponentially if we scale the problem. A great example for a problem which can’t be solved efficiently by a traditional computer (or you) is the question of how to factorise an integer with prime numbers. It’s pretty intuitive for smaller numbers, say 5 x 7 = 35. How about 2 x 2 x 3 x 5 x 7 = 420? Math tells us that there is some decomposition for any integer, but we don’t know how it looks like. This problem is (believed to be) so difficult to solve, that we built a considerable chunk of internet security on it. The number of computing steps it takes a classical computer to solve scales very fast with the number of digits. In more technical terms, we don’t know about any algorithm that can find prime factors in polynomial time, and it is thus believed to be in the class NP. You can think of NP problems as taking unreasonable long to solve with a classical computer, while P problems are solvable on a human timescale.

The reason why quantum computers are so exciting is that their magic ingredients allow them to execute Shor’s algorithm, which can find a prime factor decomposition in significantly less steps than a classical computer! In other words, while solving the prime factor problem is inefficient (i.e. NP) on a classical computer, it is efficient on a quantum computer (i.e. BQP, but I will not go down the rabbit hole of quantum complexity classes today). How does the quantum computer do that?

Quantum computers can run special algorithms since they make use of certain quantum mechanical phenomena. For example, while a classical computer stores and manipulates information encoded as zeros and ones, a quantum computer doesn’t have to decide right away. During a computation, that is before we ask the quantum computer for a result, it can store information in superposition of the two states. This means that the information is neither a zero nor a one, but both at the same time. In a nutshell, this allows the quantum computer to perform a computation on many different values simultaneously. This is called quantum parallelism and is at the core of many quantum algorithms and cannot be simulated efficiently (ah, there it is again) on a classical computer! There are even more things in the quantum information box of tricks, and together they enable all sorts of problem solving goodness.

Why did I choose this title then? Well, there are two things I want to point out. First of all, current quantum computers suck. It takes a giant room, huge machinery and lots of personnel to operate them, much like in the early days of classical computers. But even if they get more powerful in the future, they will not replace the device you are reading this on. They will probably one day have a similar purpose as your GPU; serving as a co-processor for certain applications.

Secondly, and more importantly: it is still just a computing device. Computers don’t solve problems, algorithms do.
Yes, quantum computers are exciting, especially for natural scientists and their insane computing needs. But in order for them to be actually useful, we need to come up with algorithms that are even worth running on quantum computers. In reality, there is only a handful of them right now.