Tokyo University of Science Researchers Build Quantum Chip that Solves ‘Travelling Salesman’ Problem for 22 Cities
(ElectronicsWeekly) Tokyo University of Science researchers have built a chip-based quantum annealing processor that can solve the classically thorny ‘travelling 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. Instead, it is a more limited quantum machine that can find minimal solutions for certain complex problems with many possible outcomes – the minimal length of journey required to visit 22 cities, for example.
A spokesman for the university says the paper associated with this has yet to be published so few details can yet be released widely. What Tokyo has said is that it is a 28nm CMOS chip that uses multiple spin cells, created by a group of researchers led by Professor Takayuki Kawahara.
Each state in a problem (for example, each possible route visiting many cities) is represented by the spin cells, each having one of two states, according to the university. Using a circuit which can store the strength of one spin cell state over another, the relationship between these states (the distance between two cities, for example) can be obtained: “Using a system with the same number of spin cells and circuits as the components – or the cities and routes – in the problem, we can identify the state requiring the least energy, or the route covering the least distance, thus solving the travelling salesman problem, or any other type of combinatorial optimisation problem”.