Quantum Computer Solves Traveling Salesman Problem Efficiently


Mikio Nakahara, Kindai University


2017.03.18 14:00-15:00


Middle Lecture Room, Math Building


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.