They are seen as the computing promise of the future: Quantum computers. A scientist from the Technical University of Munich (TUM) and his colleagues from the University of Waterloo and IBM have now proven for the first time that they do indeed have advantages over conventional computers. They have developed a quantum circuit that can solve a problem that cannot be solved with an equivalent classical circuit.

For a long time, quantum computers were little more than an idea. Now corporations, countries and secret services are investing in the development of quantum technology. In this promising field, Robert König, Professor for the Theory of Complex Quantum Systems at TUM, together with David Gosset from the University of Waterloo and Sergey Bravyi from IBM, has now laid an important foundation.

Why should quantum computers be faster?

Conventional computers follow classical physics. They work with binary numbers, with 1 and with 0. The numbers are stored and used for arithmetic operations. On conventional data storage devices, each bit, i.e. the smallest unit of information, is represented by a microscopic dot on a microchip. Electrical charge can be deposited on this dot, which determines whether the bit is set to 1 or 0.

In a quantum computer, however, a bit can be 1 or 0 at the same time. This is because, according to the rules of quantum physics, an electron can be in several places at the same time. Quantum bits, known as qubits, are therefore in a superposition state. This so-called superposition principle enables quantum computers to process many numbers simultaneously, whereas a single conventional computer typically performs one arithmetic operation after another. The promise of the quantum computer is therefore that it can solve some tasks much faster.

From assumption to proof

König and his colleagues have now provided watertight proof of the superiority of the quantum computer. They have developed a quantum circuit that can solve a certain "difficult" algebraic problem. The new circuit has a simple structure: It performs only a certain number of operations on each qubit. It is said to have a constant depth. With their work, the researchers clearly show that this particular problem cannot be solved by classical circuits with constant depth. They also answer the question of why the quantum algorithm is superior to all comparable classical circuits: the quantum algorithm benefits from the non-locality of quantum physics.

Previously, the superiority of quantum computers could neither be proven nor demonstrated experimentally - although there were indications, such as Shor's quantum algorithm, which efficiently solves the problem of prime factorization. However, the fact that this problem cannot be solved efficiently without a quantum computer is an assumption based on complexity theory. Ultimately, in this case it is also possible that the correct solution method with classical computers has simply not yet been found.

A step on the way to the quantum computer

Robert König sees the new results primarily as a contribution to complexity theory: "Our result proves that quantum information processing actually brings advantages - without having to rely on unproven complexity theory assumptions," he says. In addition, the next steps on the path to the quantum computer are also opening up. Due to its simple structure, the new quantum circuit is a candidate that could soon enable the experimental implementation of quantum algorithms.