First proof of the benefit of the quantum computer

For many years, quantum computers were more than just an idea. Today, companies, governments and intelligence agencies are investing in the development of quantum technology. Robert König, Professor of Complex Quantum Systems Theory at TUM, in collaboration with David Gosset of the Institute for Quantum Computing at the University of Waterloo and Sergey Bravyi of IBM, has placed the cornerstone of this promising field.

Conventional computers obey the laws of classical physics. They rely on the zero and one binary numbers. These numbers are stored and used for mathematical operations. In conventional memory units, each bit – the smallest unit of information – is represented by a load that determines whether the bit is set to one or zero.

In a quantum computer, however, a bit can be both zero and one. Indeed, the laws of quantum physics allow electrons to occupy several states at once. Quantum bits, or qubits, therefore exist in several overlapping states. This so-called superposition allows quantum computers to perform multiple value operations at once, whereas a single conventional computer must perform these operations sequentially. The promise of quantum computing lies in the ability to solve some problems much faster.

From conjecture to proof

König and his colleagues have now conclusively demonstrated the benefit of quantum computers. To this end, they developed a quantum circuit capable of solving a specific difficult algebraic problem. The new circuit has a simple structure: it only performs a fixed number of operations on each qubit. Such a circuit is considered to have a constant depth. In their work, the researchers proved that the problem to be solved could not be solved with conventional circuits at constant depth. They also answer the question of why the quantum algorithm beats any comparable classical circuit: The quantum algorithm exploits the non-locality of quantum physics.

Prior to this work, the benefit of quantum computers had not been proven or demonstrated experimentally – despite evidence to this effect. The Shor quantum algorithm is one example. It effectively solves the problem of factorization in prime factors. However, this is only a hypothesis of the theory of complexity that this problem can not be solved effectively without quantum computers. It is also conceivable that the right approach was simply not found for conventional computers.

Robert König considers the new results mainly as a contribution to the theory of complexity. "Our results show that the processing of quantum information really offers advantages, without having to rely on unproven conjectures of the theory of complexity," he said. Beyond that, the work provides new milestones on the road of quantum computers. Due to its simple structure, the new quantum circuit is a candidate for the short-term experimental realization of quantum algorithms.

Explore further:
Superconducting metamaterials trap quantum light

More information:
"Quantum advantage with shallow circuits" Science (2018). science.sciencemag.org/cgi/doi… 1126 / science.aar3106