The travelling salesman problem is considered a prime example of combinatorial optimization problems. Now a Berlin team led by theoretical physicist Jens Eisert from Freie Universität Berlin has shown that a certain class of such problems can actually be solved better and much faster using quantum computers than with conventional methods. The study was recently published under the title "An in-principle super-polynomial quantum advantage for approximating combinatorial optimization problems via computational learning theory" in the journal Science Advances.
Quantum computers calculate with so-called qubits, which are not either zero or one, as in conventional logic circuits, but assume all values in between in a precise sense. ...
