Quantum Annealer Solves the Traveling Salesman Problem
Quantum chip solves ‘traveling salesman’ problem for 22 cities
Excerpts and salient points ~
+ According to the university, this is “something that would take about 1,200 years for a high-performance von Neumann CPU”, but the chip “can solve the traveling salesman problem for 22 cities instantly” until now using quantum processing it “has only been able to solve the traveling salesman problem involving a maximum of 16 cities”.
Tokyo University of Science researchers have built a chip-based quantum annealing processor that can solve the classically thorny ‘traveling salesman’ mathematical puzzle, which gets far more complex every time a new city is added, for up to 22 cities.
+ A quantum annealing computer is not a full-blown quantum computer, of the type that could crack encryption for example, which no one has yet made – or if they have, they are keeping quiet about it.
+ “We decided to arrange the cells slightly differently to ensure that all spin cells could be connected,” said Kawahara.
+ To do this, they arranged conventional logic pre-processing circuits in a two-dimensional array, and the spin cells separately in a one-dimensional arrangement, according to the university, which apparently means that the circuits would then read the data, and an aggregate of this data was used to switch the states of the spin cells. This would mean that the number of spin cells required and the time needed for processing were drastically reduced.
+ Our technique thus represents a fully coupled method,” said Prof Kawahara, “and has the potential to solve a traveling salesman problem involving up to 22 cities.”
Content may have been edited for style and clarity.