Where quantum computers can score

The travelling salesman's problem is a classic in mathematics. A traveller is to visit N cities by the shortest route and return to the starting point. As the number N increases, the number of possible routes explodes. This problem can then be solved using approximation methods. Quantum computers could provide significantly better solutions more quickly.

The travelling salesman's problem is a classic in mathematics. A traveller is to visit N cities by the shortest route and return to the starting point. As the number N increases, the number of possible routes explodes. This problem can then be solved using approximation methods. Quantum computers could provide significantly better solutions more quickly. © HZB

The present work (arrow) shows that a certain part of the combinatorial problems can be solved much better with quantum computers, possibly even exactly.

The present work (arrow) shows that a certain part of the combinatorial problems can be solved much better with quantum computers, possibly even exactly. © HZB/Eisert

The travelling salesman problem is considered a prime example of a combinatorial optimisation problem. Now a Berlin team led by theoretical physicist Prof. Dr. Jens Eisert of Freie Universität Berlin and HZB has shown that a certain class of such problems can actually be solved better and much faster with quantum computers than with conventional methods.

Quantum computers use so-called qubits, which are not either zero or one as in conventional logic circuits, but can take on any value in between. These qubits are realised by highly 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 explore what fault-tolerant quantum computers could achieve in the future. "There are a lot of myths about it, and sometimes a certain amount of hot air and hype. But we have approached the issue rigorously, 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 Prof. Dr. Jens Eisert, who heads a joint research group at Freie Universität Berlin and Helmholtz-Zentrum Berlin.

The well-known problem of the travelling salesman serves as a prime example: A traveller has to visit a number of cities and then return to his home town. Which is the shortest route? Although this problem is easy to understand, it becomes increasingly complex as the number of cities increases and computation time explodes. The travelling salesman problem stands for a group of optimisation problems that are of enormous economic importance, whether they involve railway networks, logistics or resource optimisation. Good enough solutions can be found using approximation methods.

The team led by Jens Eisert and his colleague Jean-Pierre Seifert has now used purely analytical methods to evaluate how a quantum computer with qubits could solve this class of problems. A classic thought experiment with pen and paper and a lot of expertise. "We simply assume, regardless of the physical realisation, that there are enough qubits and look at the possibilities of performing computing operations with them," explains Vincent Ulitzsch, a PhD student at the Technical University of Berlin. In doing so, they unveiled similarities to a well-known problem in cryptography, i.e. the encryption of data. "We realised that we could use the Shor algorithm to solve a subclass of these optimisation problems," says Ulitzsch. This means that the computing time no longer "explodes" with the number of cities (exponential, 2N), but only increases polynomially, i.e. with Nx, where x is a constant. The solution obtained in this way is also qualitatively much better than the approximate solution using the conventional algorithm.

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

arö


You might also be interested in

  • BESSY II: How pulsed charging enhances the service time of batteries
    Science Highlight
    08.04.2024
    BESSY II: How pulsed charging enhances the service time of batteries
    An improved charging protocol might help lithium-ion batteries to last much longer. Charging with a high-frequency pulsed current reduces ageing effects, an international team demonstrated. The study was led by Philipp Adelhelm (HZB and Humboldt University) in collaboration with teams from the Technical University of Berlin and Aalborg University in Denmark. Experiments at the X-ray source BESSY II were particularly revealing.
  • Fuel Cells: Oxidation processes of phosphoric acid revealed by tender X-rays
    Science Highlight
    03.04.2024
    Fuel Cells: Oxidation processes of phosphoric acid revealed by tender X-rays
    The interactions between phosphoric acid and the platinum catalyst in high-temperature PEM fuel cells are more complex than previously assumed. Experiments at BESSY II with tender X-rays have decoded the multiple oxidation processes at the platinum-electrolyte interface. The results indicate that variations in humidity can influence some of these processes in order to increase the lifetime and efficiency of fuel cells. 
  • Neutron experiment at BER II reveals new spin phase in quantum materials
    Science Highlight
    18.03.2024
    Neutron experiment at BER II reveals new spin phase in quantum materials
    New states of order can arise in quantum magnetic materials under magnetic fields. An international team has now gained new insights into these special states of matter through experiments at the Berlin neutron source BER II and its High-Field Magnet. BER II served science until the end of 2019 and has since been shut down. Results from data at BER II are still being published.