Where quantum computers can score

- EN - DE
Image: IBM quantum computer
Image: IBM quantum computer

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. These qubits are realized by strongly cooled atoms, ions or superconducting circuits, and it is still physically very complex to build a quantum computer with many qubits. However, mathematical methods can already be used to research what fault-tolerant quantum computers could achieve in the future. "There are many myths about this, and sometimes also a degree of hot air and hype. But we have rigorously tackled the question using mathematical methods and delivered solid results on the subject. Above all, we have clarified in what sense there can be any advantages at all," says Jens Eisert, who heads a joint research group at Freie Universität Berlin and Helmholtz-Zentrum Berlin.

The well-known problem of the traveling salesman serves as a prime example: A traveler has to visit a number of cities and then return to his hometown. What is the shortest route? Although this problem is easy to understand, it becomes increasingly complex as the number of cities increases and the computing time explodes. The travelling salesman problem represents a group of optimization problems that are of enormous economic importance, whether they involve rail networks, logistics or the optimization of resources. Good approximate solutions can be found using approximation methods.

The team led by Jens Eisert and his colleague Jean-Pierre Seifert now worked purely analytically to model how a quantum computer with qubits could solve this class of problems. A classic thought experiment with pen and paper and a lot of specialist knowledge. "We simply assume, regardless of the physical realization, that there are enough qubits and look at the possibilities of performing computing operations with them," explains Vincent Ulitzsch, a doctoral student at the Technical University of Berlin. In doing so, they recognized similarities to a well-known problem in cryptography, i.e. the encryption of data. "We then discovered that we can handle a subclass of these optimization problems with the Shor algorithm," says Ulitzsch. This means that the computing time no longer "explodes" with the number of cities (exponentially, 2 ), but only increases polynomially, i.e. with Nx, where x is a constant. The solution calculated in this way is also qualitatively much better than the approximate solution using the conventional algorithm.

"We have shown that quantum computers have a fundamental advantage over classical computers for certain instances of the problem when it comes to a specific but very important and practically relevant class of combinatorial optimization problems," says Eisert.

(Link to the study: https://www.science.org/doi/10­.1126/scia­dv.adj5170 )