本当に量子アニーリングは「巡回セールスマン問題」が解けないのか？ 東北大・大関准教授の視点（4/4 ページ）

量子アニーリングで、組合せ最適化問題の代表といわれる「巡回セールスマン問題」が解けない？　そんな声に対し、大関准教授は「われわれの感覚では『解ける』。だが、解けないと感じた理由も分かる」と複雑な反応を示します。どういうことでしょうか。

[井上輝一，ITmedia]

　フォルクスワーゲンが行ったのは、中国の北京国際空港と北京の中心街を結ぶ幹線道路のタクシー渋滞を、量子アニーリングを用いて解消する試みで、2017年に論文を発表。ヒートマップで、渋滞を緩和した様子を視覚的に示しました。

左が最適化前、右が最適化後。トラフィックが分散しているのが分かる（フォルクスワーゲンとD-Wave Systemsの資料より）

　「この問題では、それぞれのタクシーが3つのルートから1つを選ぶと考えて、1台に3つのビットを割り当てる。例えば0,0,1なら右のルートを選択するといった具合。ここで、別の場所から来たもう1台のタクシーBが1,0,0で左のルートを選んだとする。すると、先ほどのタクシーAと同じ道を走ってしまうため、渋滞が発生すると考える」

　「こういう場合には、Aの3番目の量子ビットとBの1番目の量子ビットが同時に1にならないような相互作用を設定し、『同じ道を通るのは避けなさい』と決めておく。このように複数のタクシーの相互作用を関数に取り入れて、量子アニーリングで解いて見せたのがフォルクスワーゲンの例だった」

　交通渋滞は、クルマどうしの衝突（物理プロセス）と考えられるから、量子アニーリングに向いていると大関准教授はいいます。さらに、大関准教授は巡回セールスマン問題と比べたメリットを示します。

　「フォルクスワーゲンの例で、量子アニーリングマシンが計算をしくじり、あるタクシーのルートが0,1,1になってしまったとする。巡回セールスマン問題だったらこのような例は後処理しようがなかったが、タクシーだったらとりあえず真ん中か右かのルートに行ってしまえばいい。出てきた解をとりあえず使えるという意味でも、交通渋滞の問題は量子アニーリングに向いている」

　大関准教授は、「交通渋滞の問題ではなくても、巡回セールスマン問題ほどは条件が厳しくなく、それでいてタクシーのような複数の要素が絡む問題であれば量子アニーリングで解いてみる価値がある。そういう問題を解いてみてほしい」と語りました。