The traveling salesman problem is considered a prime example of a combinatorial optimization problem. Now a team has shown that a certain class of such problems can actually be solved better and much faster with quantum computers than with conventional methods.
The traveling salesman problem is considered a prime example of a combinatorial optimization problem. Now a team has shown that a certain class of such problems can actually be solved better and much faster with quantum computers than with conventional methods.
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 , their Sycamore computer has taken on -- and solved -- a problem considered intractable for ...Icy Impacts: Planetary Scientists Use Physics and Images of Impact Craters to Gauge the Thickness of Ice on Europa
Deutschland Neuesten Nachrichten, Deutschland Schlagzeilen
Similar News:Sie können auch ähnliche Nachrichten wie diese lesen, die wir aus anderen Nachrichtenquellen gesammelt haben.
Bladder Disorders News -- ScienceDailyOveractive bladder, urinary incontinence, cystitis and other bladder disorders.
Weiterlesen »
Making quantum bits fly | ScienceDailyPhysicists are developing a method that could enable the stable exchange of information in quantum computers. In the leading role: photons that make quantum bits 'fly'.
Weiterlesen »
Patience pays off | ScienceDailyResearchers decode the neuronal basis of decision-making processes and can thus predict actions.
Weiterlesen »
Illegal Drugs News -- ScienceDailyRead the latest medical research on illegal drugs and controlled substances. Find out about the effect on the body, addiction risks, possible medicinal uses and more.
Weiterlesen »
Vitamin B News -- ScienceDailyRead about the latest research on B vitamins, including newly discovered benefits of Vitamin B3, B12, folic acid and related vitamins.
Weiterlesen »
Giving particle detectors a boost | ScienceDailyResearchers have tested the performance of a new device that boosts particle signals.
Weiterlesen »