巡回セールスマン問題（じゅんかいセールスマンもんだい、英: traveling salesman problem、TSP）は、都市の集合と各2都市間の移動コスト（たとえば距離）が与えられたとき、全ての都市をちょうど一度ずつ巡り出発地に戻る巡回路のうちで総移動コストが最小のものを求める（セールスマンが所定の複数の都市を1回だけ巡回する場合の最短経路を求める）組合せ最適化問題である。
巡回セールスマン問題は、量子コンビユーター解説のイントロ、
もう、私はここでギブアップ、
高校に入ってすぐ因数分解で躓いた嫌な思い出が蘇った。
都市の数が増えるとスパコンでも計算するのが大変だが量子コンピューターなら一瞬で解けるらしい。
この近くに気象衛星センターがあり、そこでは500人ぐらいのエンジニアが気象衛星・ひまわりのデータをスパコンを使って解析していた。
“気象庁は、弱小官庁だから仕方がないがもっと高性能のスパコンが欲しい”と言っていた。
お天気のような気まぐれな予測には量子コンピューターが役立つのだろうか。
怖いのは、量子コンピューターが実現すると現在使われている暗号技術が無力化されてしまうこと。
だから米中がその開発に血道を上げている。
戦前の日本の暗号技術は幼稚だった。
だから山本五十六はあっさり撃墜された。
一方、ナチスドイツは、エニグマ(左の写真)というローター式の暗号機を開発、連合軍を苦しめ続けた。
それでもイギリスの天才数学者・アランチューリングがエニグマの解読に成功、ナチス撃退のきっかけを作った。
しかし、戦後チューリングは同性愛者として断罪されて自殺に追い込まれてしまう。
それから半世紀を経てチューリングこそ現在のコンビユーターを発明した人物として再評価されるようになった。
もし、イギリス政府が彼を死に追いやらなかったらイギリスは大きく変わっていたはず。
映画・イミテーションゲームはなかなか面白い。
《エニグマ暗号機vsアランチューリング》
《イミテーションゲーム予告編》