Scientists prove the advantages of quantum computers

Scientists from the Technical University of Munich (TUM), the University of Waterloo and IBM have demonstrated for the first time that quantum computers — for many years not much more than an idea — do indeed offer advantages over conventional computers.

Conventional computers obey the laws of classical physics — they rely on the binary numbers 0 and 1, which are stored and used for mathematical operations. In conventional memory units, each bit — the smallest unit of information — is represented by a microscopic dot on a microchip. Each of these dots can hold a charge that determines whether the bit is set to 1 or 0.

In a quantum computer, however, a bit can be both 0 and 1 at the same time. This is because the laws of quantum physics allow electrons to be in multiple places at one time. Quantum bits, or qubits, thus exist in multiple overlapping states.

This so-called superposition allows quantum computers to perform operations on many values in one fell swoop, whereas a single conventional computer typically must execute these operations sequentially. The promise of quantum computing thus lies in the ability to solve certain problems significantly faster.

Now, TUM’s Professor Robert König and his colleagues have conclusively demonstrated the advantage of quantum computers, developing a quantum circuit that can solve 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 referred to as having a constant depth.

In their work, published in the journal Science, the researchers prove that the problem at hand cannot be solved using classical constant-depth circuits. They furthermore 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 advantage of quantum computers had neither been proven nor experimentally demonstrated, though evidence had pointed in this direction. One example is Shor’s quantum algorithm, which efficiently solves the problem of prime factorisation. However, it is merely a complexity-theoretic conjecture that this problem cannot be efficiently solved without quantum computers. It is also conceivable that the right approach has simply not yet been found for classical computers.

“Our result shows that quantum information processing really does provide benefits — without having to rely on unproven complexity-theoretic conjectures,” Prof König said. The new quantum circuit is also a candidate for near-term experimental realisation of quantum algorithms, thanks to its simple structure, further helping to pave the road to quantum computers.

Image credit: ©stock.adobe.com/au/zapp2photo