欢迎光临!
您现在所在的位置:首页 >> 通知公告 & 学术信息
学术信息
SEMINARS
Quantum computer solves traveling salesman problem efficiently
时间  Datetime
2017-03-18 14:00 — 15:00
地点  Venue
Room 1106, Math Building
报告人  Speaker
Mikio Nakahara (中原幹夫)
单位  Affiliation
Kindai University
邀请人  Host
Eiichi Bannai
报告摘要  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.


http://math.sjtu.edu.cn/conference/Bannai/2016/talk.php?20170318A