First Proof That Quantum Computers Are Superior

Scientists develop new quantum circuit

quantum computers
Layout of a Quadrature Quadrature Superconducting Circuit Device from IBM. (Image: IBM Research, https://www.flickr.com/photos/ibm_research_zurich/16662697764/in/album-72157663611181258/)

They are considered the computing promise of the future: quantum computers. That they actually have advantages over conventional computers, a scientist of the Technical University of Munich (TUM) and his colleagues from the University of Waterloo and IBM have now demonstrated for the first time.

For a long time, quantum computers were not much more than an idea. Now corporations, countries and intelligence agencies are investing in the development of quantum technology. Robert König, professor for the theory of complex quantum systems at the TUM, together with David Gosset from the University of Waterloo and Sergey Bravyi from IBM has laid an important foundation in this promising field.

Why Should Quantum Computers Be Faster?

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

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

From the Conjecture to the Proof

The watertight proof of the superiority of the quantum computer is now provided by König and his colleagues. They developed a quantum circuit that can solve a certain “difficult” algebraic problem. The new circuit has a simple structure: it only performs a certain number of operations on each qubit. It is said that it has a constant depth. With their work, the researchers clearly show that this particular problem can not be solved by classical circuits with constant depth. In addition, they 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 proved nor experimentally demonstrated – though there were indications, such as Shor’s quantum algorithm, that efficiently solves the problem of prime factorization. However, that this problem can not be solved efficiently without quantum computers is, however, a complexity theory assumption. Ultimately, it would also be possible in this case that the correct solution method with classic computers has simply not yet found.

A Step on the Way to the Quantum Computer

Robert König sees the new results primarily as a contribution to the theory of complexity: “Our result shows that quantum information processing really brings benefits – without having to rely on unproven complexity-theoretic conjectures,” he says. In addition, however, next steps on the way to the quantum computer will open up. Due to its simple structure, the new quantum circuit is a candidate that could soon enable the experimental implementation of quantum algorithms.

Source : Technical University of Munich (TUM)