Combinatorics Seminar 2017

Speaker: Mikio Nakahara (中原幹夫), Kindai University

Date: Sat, Mar 18, 2017

Time: 14:00 - 15:00

Venue: Room 1106

Title: Quantum computer solves traveling salesman problem efficiently


Recently, quantum algorithms to solve mathematical problems are proposed. In my talk, a quantum algorithm to solve the traveling salesman problem is introduced and demonstrated numerically. The idea of quantum computing is introduced first for those who are not familiar with this subject. Then a quantum algorithm to find the smallest eigenvalue of a large matrix representing a randomly coupled spins is outlined. Finally, the travelling salesman problem is mapped to a spin system whose smallest eigenvalue gives the solution to the problem. It is shown that the number of steps required to solve the problem is polynomial in the number of cities to be visited. Some numerical demonstrations using a classical computer will be shown.

Slides: View slides