How prime numbers help improve the quantum computer

Scientists at the Jülich Supercomputing Centre have set a new world record: they simulated a quantum computer with 48 qubits on two different supercomputers. In order to test the limits of their simulated quantum computer, they used a method that requires the highest computing capacities: the prime factorization of large numbers. In their simulated quantum computer, the scientists implemented the so-called Shor’s algorithm so successfully that they could use it for a number of previously unattained size: 65531.

Any natural number can be represented as a product of prime numbers. What are the prime factors of the number 21? Most primary school children know the answer by heart: 3 and 7. For a larger number, say 217, most people will need a little longer and probably also a calculator. The decomposition – or factorization – of a very large number with several hundred digits can take years, even for scientists with supercomputers.

As the prime factor decomposition of large numbers is so incredibly difficult, it is the basis for all common encryption methods to protect credit cards, government secrets and other confidential data. They are considered very secure because of the long computing time required by a conventional computer to crack a code of this type.

This is why it caused a sensation when in 1994, the American mathematician and computer scientist Peter Shor presented his factorization algorithm for quantum computers. Shor’s algorithm allows the efficient decomposition of a large number into two prime numbers faster than classical computers are able to do – much faster.

"The reason for this is not only the extremely fast computing power of a quantum computer," explains Kristel Michielsen from the Jülich Supercomputing Centre. "Namely, it is particularly useful for problems with very special characteristics: problems to which the laws of quantum mechanics can be applied in order to solve them."

In addition to simulations of quantum mechanical systems such as atoms or molecules, this also includes search algorithms, for example for the detection of entries in unsorted databases. The prime factorization of large numbers is another one of the problems for which quantum computers are particularly well suited; just like Shor’s algorithm. Besides its application for encryption systems, it is also one of the most important program codes for testing the functionality and performance of quantum computers.

Efficient simulation

However, a quantum computer itself that can be used in practice is still a dream of the future, even if large companies such as Google, Intel and IBM have been working on its realization for several years. Above all, the particular susceptibility of such computers to errors is still a major problem. But software developers and engineers will not have to start from scratch when the first quantum computers become available.

"The functionality of relatively large quantum computers can already be simulated on conventional digital computers today. However, the computational effort is huge,” explains Michielsen. Each simulated quantum bit – in short: qubit – doubles the amount of memory required. “There are currently few supercomputers in the world that have sufficient memory, processing cores and adequately fast network connections."

The software is just as important. Different to conventional computers, supercomputers have hundreds of thousands or even millions of processors. Many programming codes are not designed to run on so many elements simultaneously, losing efficiency with each additional compute node. The software which Michielsen and her partners have been developing for over ten years, on the other hand, shows practically no loss in performance. Its code reduced the memory requirement for a simulated quantum computer to an eighth.

For their simulation, the scientists used two of the world’s fastest supercomputers: the Chinese Sunway TaihuLight and the Japanese K. This enabled them to simulate the world’s largest universal quantum computer. It has 48 qubits.

Endless possibilities

The qubit is the basic unit of the quantum computer. While the conventional bit on which our current computers are based is either 0 or 1, a qubit can take both values simultaneously. "Physicists speak of an overlay or superposition of the two states," explains Kristel Michielsen. "In fact, as long as it is not read, the qubit is in no fixed state at all. It is both 0 and 1 and any value in between. Only by reading is the infinite number of possibilities reduced to either 0 or 1."

To illustrate this, one can imagine an ordinary table fan with two blades. A conventional bit is a fan that is not running, with both blades facing up and down, for example. A qubit, on the other hand, is a fan that rotates so fast that one can no longer see its wings: they seem to point in all directions simultaneously.

Computing time reduced from years to days

The quantum computer makes use of this superposition of states. It calculates not only with the values 0 and 1, but with an overlay of all possible values. Thus, many calculation paths are run simultaneously. The result of the calculation is a so-called interference pattern – which is similar to the stroboscope effect that makes a table fan look as if it were standing still or slowly turning backwards.

Shor’s algorithm uses these interference patterns to find prime factors; a task which is extremely difficult for very large numbers. With a conventional computer, the effort increases exponentially with the length of the number: put simply, all possible factors are tried out one after the other. On a quantum computer, in contrast, the effort increases only by the square of the number length – thus, the computing time required for very large numbers can be reduced from years to days.

A milestone

Kristel Michielsen and her colleagues have now successfully applied Shor’s algorithm in their quantum computer simulation. They succeeded in dividing the number 65531 into factors 19 and 3449, which is a milestone that also demonstrates the practical use of algorithms for quantum computers. However, their prime number decomposition is still far from revolutionizing encryption technology – because the larger the number, the more qubits you need.

"Our simulation has 48 qubits, which makes it the largest simulated universal quantum computer in the world," explains Michielsen. 65531 is the largest number that can be calculated on such a system using Shor's algorithm. "We assume that this will not change in the next five years or so," says Michielsen. "But we hope that we are wrong."

Regine Panknin