Scientists claim to prove the true benefits of quantum computing for the first time

IBM and Technical University of Munich team demonstrate how Shor's algorithm, which can't be cracked by conventional computers, can be solved quickly with quantum computing

Scientists have demonstrated what they believe to be the first true advantage of quantum computers.

Robert König, professor for the theory of complex quantum systems at the Technical University of Munich (TUM), teamed with David Gosset from the Institute for Quantum Computing at the University of Waterloo and Sergey Bravyi from IBM, and developed a quantum circuit that they said can solve a specific "difficult" algebraic problem.

The new circuit has a simple structure in that 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, the researchers claim the quantum computer lives up to the promise of it being able to solve certain problems significantly faster.

They claim to have proved this by showing how a "difficult" algebraic problem cannot be solved using classical constant-depth circuits. They also answered the question of why the quantum algorithm beats any comparable classical circuit: that the quantum algorithm exploits the non-locality of quantum physics.

Before this experiment, the scientists said the advantage of quantum computers had neither been proven nor experimentally demonstrated.

One example is Shor's quantum algorithm, which efficiently solves the problem of prime factorisation. However, the scientist say that it is "merely a complexity-theoretic conjecture that this problem cannot be efficiently solved without quantum computers".

They also added that it is "conceivable that the right approach has simply not yet been found for classical computers".

However, König said that the experiments prove there really is a need for quantum information processing.

"Our result shows that quantum information processing really does provide benefits, without having to rely on unproven complexity-theoretic conjectures," he said.

"Beyond this, the work provides new milestones on the road to quantum computers. Because of its simple structure, the new quantum circuit is a candidate for a near-term experimental realisation of quantum algorithms."