How does a Quantum Computer work?

In the last years a huge hype on quantum computing arose, lately with googles claim of Quantum Supremacy [DOI: 10.1038/s41586-019-1666-5]. Naturally an understanding for this topic is interesting. Here we try to point out the basic concept of Quantum computers and how they can be faster than a classical computer.

Qubits

Whilst classical computers use ‚classical‘ bits, i.e. 0 and 1 or ‚on‘ and ‚off‘ or high (voltage) or low (voltage) and thus only 2 states, a quantum computer get’s the advantage from using quantum bits, so called qubits. Instead of two possible states, they can have a variety of states:

$$\ket{\Psi} = \alpha \ket{0} + \beta \ket{1} \quad\alpha, \beta \in \mathbb{C}, |\alpha|^2+|\beta|^2=1$$

With this equation we immanently see that a qubit is a coherent superposition of the two classical bits and thus can theoretically have infinite different states. Example: Photon with polarisations or atom with ground and excited state.

Quantum Superposition

Using this concept, a quantum computer is able to perform many measurements at once.

The following example will show that:

Classical bits: $\ket{0}, \ket{1}$, qubit: $\frac{1}{\sqrt{2}}\cdot \left(\ket{0}+\ket{1}\right)$,
Operation we want to perform: NOT gate

Classically:

If we invert the $\ket{0}$-bit we will get a $\ket{1}$-bit.
Analogous, when we use a $\ket{1}$ as the initial bit we will get a $\ket{0}$ as a result.

We need to apply the NOT gate two times.

Quantum:

In the case of the quantum state as initial bit, we use $\ket{\Psi}=\frac{1}{\sqrt{2}}\left(\ket{0}+\ket{1}\right)$, the final bit will be $\ket{\Psi’}=\frac{1}{\sqrt{2}}\left(\ket{1}+\ket{0}\right)$.

We applied the NOT gate one time but got the results for both bits, as they are both present in our initial state.

While this doesn’t seem to be a big improvement, one has to realize that most algorithms need a high number of calculation steps. One example is the Deutsch(–Jozsa) algorithm. Without explaining what that is good for we only want to remark that the number of operations shrinks from $2^{N-1}+1$ (classical computer) to 1 (Quantum Computer). This algorithm was the first example where a quantum algorithm was shown to be exponentially faster than the classical algorithm.

But!

One should not be mistaken by the general “A quantum computer can perform calculations faster than a classical computer” or similar terms. Yes, Quantum Computers are able to perform some calculations faster. Way faster, indeed. But not any kind of calculation, your games won’t get 8K graphics when you’re using a quantum computer at home. There is a specific set of Problems that can be solved faster using a quantum computer. Others are faster on a classical computer. The typical example of a problem for Quantum Computers is Shor’s Algorithm, which is the fractionalisation into prime numbers.

A comparison of exponential runtime vs ln(N)^2.

While it takes $\sim e^N$ steps on a classical computer to perform an integer fractionalisation, a quantum computer only takes $\sim\log{N}^3$.

The Problem is that qubits are very sensitive to the environment. Even the interaction with an air molecule or temperatures above single Kelvin destroy the quantum state. Therefore, one has to use error correction to improve the results and thus we need many qubits. IBM already sucessfully performed Shor’s algorithm, but only on the number 15. To be able to use it on 1024 or 2048 bit RSA Keys, many qubits are necessary and thus, this will still take some time to be accomplished.

Little outlook:

Quantum Physics not only lead to problems, it also offers new solutions: While classical cryptography algorithm (in the current form) are useless with a fully operational Quantum Computer, Quantum Cryptography gives us the possibility of secure communication.

lau

Hi, I’m a physics student from Germany with interests in the field of Quantum Technologies, Solid State Physics and Information Technology. Currently doing my master thesis at the Max-Planck-Institute for Solid State Research and the Institute for Functional Matter and Quantum Technologies at the University of Stuttgart.

Leave a Reply