Quantum computing

Definition and delimitation

Computer science deals with the algorithmic solution of problems, such as searching in an unsorted list or decomposing an integer into its prime factors. Problems are assigned a so-called runtime complexity. This is the number of calculation steps that an optimal algorithm requires to solve this problem, depending on the length of the input. For some problems, the runtime complexity is known, such as searching an unsorted list, but for others it is not, such as prime factorisation.

Once an optimal algorithm has been found for a problem, there is as yet no way to further speed up the computation of the solution, with the exception of scaling the hardware. But due to the foreseeable end of Moore’s Law, i.e. the doubling of transistors on a microchip every two years, hardware scaling will also no longer be possible to this extent in the future.

This is where quantum computing comes in. The theory is that with the help of quantum mechanical computation, some problems can be solved with a lower runtime complexity than with a classical computer. However, this theoretical quantum superiority has so far only been proven for a few problems, such as searching an unsorted list using Grover’s algorithm ^[1]. Theoretical quantum superiority is currently assumed for other problems, such as prime factorisation with Shor’s algorithm ^[2].

The quantum computer uses several quantum mechanical phenomena for its calculations, such as superposition and entanglement.

While a classical bit can be either in state 0 or in state 1, a quantum bit (in short: qubit) can be in a superposition of these two states. It is then, for example, 25 % in state 1 and 75 % in state 0. Only when measured does the qubit collapse to one of the two states, with exactly the probability that it was in that state. So when measuring the qubit above, you would measure state 1 with a probability of 25% and state 0 with a probability of 75%. So if you apply the same algorithm to the same input, you can get different results. The calculation with a quantum computer is therefore probabilistic.

Entanglement is a property of quantum objects: Several objects combine with each other in such a way that they can no longer be considered as independent objects, but only as a common object. This exponentialises the state space. For while a single qubit can be in a superposition of two states, a quantum register consisting of two qubits (entangled) can now be in a superposition of 4 states, a 3-qubit register then of 8 and so on. A quantum register with N qubits can therefore be in a superposition of ^2N states.

With the help of gates, the weights of the individual states (also called amplitudes), i.e. the 25 % and the 75 % from the above example, can be changed. The trick is that the amplitudes of all ^2N states can be changed simultaneously by a single gate. This theoretically allows an exponential speed-up compared to a classical calculation. The aim of a quantum algorithm is now always to increase the amplitude of the sought state by a suitable sequence of gates (without knowing this state, of course), so that the probability of collapse to this state is increased during the measurement.

History

The beginnings of quantum computing date back to the early 1980s. During this time, pioneers such as the American physicist Paul Benioff ^[3] and the Russian mathematician Yuri Manin developed the first concepts for quantum computing ^[4]. Richard Feynman also recognised the potential and necessity of quantum computing for the simulation of physical processes. Legendary in particular is his famous phrase: “If you want to build a simulation of nature, it had better be quantum mechanical, and, ei der Daus, suddenly that’s a wonderful problem because it doesn’t look simple at all.” ^[5]

The first groundbreaking quantum algorithms were developed in the mid-1990s. Starting with Peter Shor, who presented an algorithm for prime factorisation, for which there is still no efficient classical algorithm. Since the difficulty of prime factorisation is the essential cornerstone for the security of RSA encryption, a sufficiently large quantum computer would have serious consequences for its security. However, the quantum computers currently available are far too small and too error-prone to threaten RSA. Two years after Shor, Lov Grover developed the Grover algorithm for quadratically accelerated searches in unsorted databases.

This was followed by a long period without any major new developments until the last few years, when numerous large tech companies, such as Google, Microsoft, IBM or Amazon, got involved in the development of quantum computers. In 2019, the time had come: the proof of so-called quantum superiority ^[6]. The proof that a quantum computer can solve a certain task faster than any classical computer. Sycamore, Google’s quantum computer, was able to solve a specific task that the current best classical supercomputer was estimated to take over 10,000 years to complete.

Application and examples

Quantum computing, despite its many successes, is still in the developmental stage. The problem for which Google has demonstrated quantum superiority is very specific and has little practical relevance. For practically relevant problems, such as prime factorisation, the quantum computers currently available are still too small and error-prone.

Once the hardware problems of quantum computing have been solved, however, a multitude of application areas opens up, for example the development of new drugs ^[7]where the quantum computer is used in the simulation of molecules. Other areas of application include the support of machine learning ^[8] and the accelerated solution of optimisation problems ^{[9, 10]}.

Criticism and problems

There is already a wealth of quantum algorithms, but so far there is a lack of sufficiently good quantum computers. The main problems are poor scalability (small number of qubits), the error-proneness of the qubits (relaxation) and the short coherence time, i.e. the loss of superposition.

It has also only been proven for a few quantum algorithms that they have a lower runtime complexity than their classical equivalents.

Research

Research is currently being conducted on several approaches to how qubits are physically realised. The three most important of these are ion traps, photons and superconductors.

In ion traps, a single atom serves as a qubit. If the atom does not have the same number of electrons as protons, it is electrically charged (an ion) and can therefore be spatially fixed with electric fields. In addition, atoms have several so-called energy levels, i.e. discrete energetic states. If one adds exactly the energy difference to an atom located in the first energy level, for example by means of a laser, it jumps from the first energy level to the second. In this type of quantum computing, the two energy levels serve as the two possible states of the qubit.

In a photon quantum computer, the qubits are realised by photons. Here, the fundamental property of quantum objects is used that they can be considered both as particles and as waves. As orthogonal states for the qubits, perpendicularly superimposed polarisations of the photons (i.e. the waves) are now used.

In superconductor technology, on the other hand, the qubits are represented by electric currents in resistance-free (i.e. superconducting) chips. Sycamore, Google’s quantum computer, uses this type of quantum computing ^[6].

Each of these technologies has its advantages and disadvantages. Which technology will prevail in the end cannot be predicted today. In addition to the hardware, research is also being done on new quantum algorithms, as well as on new “post-quantum” encryption methods ^[11] in case RSA becomes insecure at some point.

---