断熱量子コンピューティングによる巡回セールスマン問題の解法
幹夫 中原, 将光 坂東, 宗 田中
Abstract
巡回セールスマン問題とは,N 都市と各都市の間の距離が与えられたとき,セールスマンがN都市すべてを1 回づつ訪問し,かつその全距離を最小にする経路を探す問題である.古典的にはすべての可能性を列挙して,その中で最小距離の経路を求めればよいが,それにはN! 程度のステップが必要となる.これはNP 困難とよばれるクラスに属する問題で,N が大きくなると実用的ではない.最近,量子コンピュータを用いて,この問題を解く方法が提案され,注目されている.これは断熱的量子コンピューティングと言われる手法であり,実用的な量子コンピュータが存在すれば,N に関して多項式時間で問題が解けると期待される.実際には古典コンピュータを用いて,シミュレーティッド・アニーリングや量子アニーリングとよばれる手法で問題を解くのであるが,本論文では,教育面に重点を置いて,4 都市の問題を表現するシュレーディンガー方程式を直接解き,解法の原理的デモンストレーションを行う.