Quantum Computing Introduction for Beginners

In the following, we explain quantum computing in simple terms, so everyone can understand this amazing topic. The field is so interesting since quantum computers can solve specific tasks much faster than traditional computers. To clarify, when we talk about quantum computers we do not mean computers by the brand Quantum. Rather, we talk about computers that make use of quantum physics. But before we get into details how this works, let’s take one step back and quickly look at traditional computers.

From Traditional Computers to Quantum Computers

Moore's Law - Microprocessor Transistor Counts

Computers as you know them have become faster and faster over time. This goes hand in hand with an increase of transistors in these computers. Gordon Moore made a prediction that the number of transistors will double each say, two years. This doubling has indeed been found over the years, see the figure. But with computer components becoming smaller and smaller, one would eventually reach transistors that are only one atom large. Already before we hit this natural limit, quantum effects will start to play a role.

If quantum effects would disturb the functioning of traditional computers, can we instead build computers that embrace these quantum effects? That is what quantum computing is all about: Making use of quantum physics to build conceptually different computers.

Difference between Traditional and Quantum Computers

Computers as you know them operate on bits, i.e. quantities that can have values 0 and 1. Quantum computers operate on quantum bits, also called qubits. A qubit can have value 0 (which physicists like to write in a notation that looks like \mid 0\rangle), or value 1, or a superposition thereof. That a superposition of 0 and 1 is allowed is new. But does this alone make quantum computers potentially faster than classical computers? The answer is no. On a classical computer you can use a couple of bits or bytes (1 byte = 8 bits) to represent a floating point number, e.g. 0.2. This floating point number can also be seen as a superposition of 0 and 1. It is 0.2 = 0.8*0+0.2*1.

While you need more than 1 bit on a classical computer to represent the number 0.2, you so far only win a constant factor. What really makes the difference is how many qubits behave together. They can show a property called entanglement, which is at the heart of quantum computing. We’ll explain it in the following in as simple terms as possible.

Entanglement of Quantum Bits

We want to consider two quantum bits. But before we do, let us think about the classical analogy. There, we could have two floating point numbers in a list, e.g. {0.2, 0.7}. The 0.2 “lives” on the first entry of the list, and the 0.7 “lives” on the second entry of the list. We can denote this place by a subindex, and write the list as a product of two states:
(0.2)_0\otimes(0.7)_1=(0.8\cdot 0_0+0.2\cdot 1_0)\otimes (0.3\cdot 0_1+0.7\cdot 1_1)

If this looks complicated, never mind. We are nearly there. The point is that if you multiply out this product there would be “amplitudes” for four different states, namely
0_0\otimes 0_1, 1_0\otimes 0_1, 0_0\otimes 1_1, 1_0\otimes 1_1.

Can you get a combination consisting only of
0_0\otimes 0_1 +1_0\otimes 1_1?
(up to a common prefactor)? You cannot with a traditional computer and two floats. But you can get the analogous for two quantum bits. Such a state would be called entangled state. Why? If you know the qubit is in this state, and you would measure the first qubit and find that it is in state 0, you immediately know the second qubit is in state 0 as well. If you measure the first qubit and find a 1, you know that the second qubit is in state 1 as well. Something like this is just not possible with classical float numbers.

Why can quantum computers be faster?

Could you somehow allow for states like this on a classical computer? Of course, but you would need four floats if you want to allow for all states that are possible with two qubits. And if you have 100 qubits, you would need 2^{100} floats — that’s really a lot. Quantum computers can operate on all the exponential number of amplitudes at the same time. This is the reason, why quantum computers could in principle be exponentially faster than traditional computers. Unfortunatelly, only if one finds a proper quantum algorithm for the specific task at hand. And this is not so easy, since one is bound by the laws of quantum physics.

What quantum algorithms exist?

Now that we have roughly understood why quantum computers can be so fast, let’s consider what they can be good for. The best known quantum algorithm is Peter Shor’s factoring algorithm. If you have a very large number n, that is the product of two large primes p and q, can you find p and q if you know n? There is no classical algorithm known that solves this task in polynomial time. Shor’s quantum algorithm can do just that.

Is Quantum Computation Dangerous?

Unfortunatelly, we would have to say yes. There exists a cryptographic scheme called RSA that is used by many banks and other facilities worldwide. This scheme is based on a fact that it is not possible to factorize a large number n into its primes with computers as we know them. But exactly that would become possible with Shor’s algorithm, if a sufficiently large quantum computer would exist. Thus, there is a problem with the invention of quantum computers. On the other hand, if one was able to build a sufficient number of quantum bits, one could do quantum cryptography with them. Anyway, one should discuss the invention of quantum computers from an ethical point of view. Especially, as long as there are no really great new algortithms that for example would solve traditionally (NP) hard problems in polynomial time.

How Far Is Research on Quantum Computers?

Researchers succeeded to build prototypes of quantum computers with a few quantum bits and demonstrated that basic quantum algorithms really would work. Building larger quantum computers belongs to active research that also may bring risks of misuse (see above). A different kind of quantum computation, called adiabatic quantum computing, is used in quantum computers as fabricated by D-Wave systems in Canada.

What Is Needed To Build a Quantum Computer?

Since we want to have qubits that can have two states (or a superposition of them), we need a two-state system for each qubit. There are many proposals for such two-state systems. It could be two states of an ion in a trap, or two states of electrical charge on the island of a superconducting ring. Possibilities are nearly endless, but can become more complicated than we want this article to become. There is more, however, than just having two-state systems. There must be the possibility of coupling between different qubits, so that one can build so-called two-qubit quantum gates. This goes beyond the scope of this article.

Quantum Computing Summary

You should have learned that quantum computers can be exponentially faster than classical computers. This is made possible by operating on an exponential number of quantum amplitudes on the same time. Unfortunately, only very specific algorithms exist so far. The prime example of a quantum algorithm is Shor’s factoring algorithm. It allows to factorize large numbers quickly, which would break the cryptographic RSA scheme used by banks. On the other hand, with controllable quantum bits, quantum cryptography would become available. It is a cryptography scheme that in some meaning is provable secure.