**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

**Abstract**:

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