されど、巡回セールスマン問題（量子アニーリングの場合）

　TSP（巡回セールスマン問題）に対しては、従来コンピュータを利用した優れた解法が研究し尽くされたようです。しかし、これは、量子アニーリングの例題として有用なのでメモしておきます。ディープラーニングでのポピュラーな例題MNIST（手書き数字認識問題）に匹敵するくらいかも知れません。

■従来コンピュータを用いたTSP解法の状況
　よく目にする記事「30都市でも、現在のスーパーコンでは8億年かかるが、量子コンピュータなら一瞬」というのは、妥当性に欠けます。８億年というのは、特に工夫せずに総当たりの探索を行った場合でしょう。また、量子コンピュータで解ける、と言っても（量子トンネル効果で局所解を回避するとはいえ）一般には最適解が得られるとは限りません。

　現状のTSP解法の集大成は、Waterloo大学のProf. William CookによるConcorde TSPにあります。多様なアルゴリズムの構成で作られたソフトにより、実問題の85,900都市（VLSI応用）が解かれていますし、この名前のアプリも一般公開されています。これを使って、旧型のiPadでも、500都市が15秒で解けました。ですから、当面はTSPに関しては、量子コンピュータの出番は無さそうです。しかし、冒頭に述べた通り、良い例題として以下に検討します。

■量子アニーリングを用いたTSPの解法
　量子アニーリングによる解法の要点は以下に示す通りです。解法と言っても、「解法アルゴリズム」は与えません。コスト関数と制約条件を与えるのみです。ここに最大の特徴があるでしょう。（さらに詳細が必要な場合は、以下に示したURLを参照下さい。）

　これだけで十分良い解が得られることもありますが、コスト関数に加える制約条件の強さを（係数を掛けて）調整する必要がある場合もあります。さらに、コスト関数の縮小、回転対称性の除去、反転対称性の除去などの高度な修正を要する場合もあるようです。

■例題：東京都中央区の公園56ヶ所を回るTSP
　この公園56ヶ所の例題を、あるTSPソルバーで解き、実際にそのルートを全部歩いた報告があります。詳細は、図１に示したURLをご覧下さい。「最短経路だ！巡回セールスマン問題の研究ってすごいなあ」を実感するためとのことです。素晴らしい行動力！「楓川久安橋公園」を出発して、公園56ヶ所を約6.9時間かけて完歩したとのことです！計算上の所要時間と実際の歩行時間の比較などもなされています。

　これと同じ条件設定で、上述の量子アニーリングで解いた結果を図２に示します。最適解（最短）かどうかは分かりませんが、図１の結果とほぼ一致したルートが得られました。実際には、上述のコスト関数と制約条件を、Fixstars Amplify SDKの関数などを使って表現しました。ただし、公園間の距離は、実際の道路経由ではなく、直線距離で代用しています。

　ここでは、量子アニーリングを用いた基本的な利用を示しました。高度なチューニングは含めていませんが、もっと大規模な実用問題では、それらも検討することになるでしょう。本記事はそのきっかけにはなると思います。