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

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

[井上輝一，ITmedia]

使いやすくなったが、良い解を出すアルゴリズムを選べなくなった

　「D-WaveマシンのAPIが、今年初めくらいから使いやすくなった。扱う上で難しい部分が包み隠され、問題を入れれば欲しい形の解がすぐに出てくるようになった。その一方で、最終的なパフォーマンスにつながる『後処理』のアルゴリズムで適切なものをデフォルトでは選べなくなってしまった」といいます。

　量子アニーリングマシンの中では、量子ビットどうしが物理的に結合して相互作用を起こしていますが、物理空間などの制約があることから全ての量子ビットがお互いに結合しているわけではありません。

　しかし、解きたい問題によっては物理的な結合の数以上の結合が必要になる場合があります。「そういう場合には、2つの量子ビットを1つのものとして扱うことで結合数を増やす」（同）。

それぞれの丸が量子ビット、丸同士をつなぐ線が相互作用。左側のひし形が層になった構造が一つの塊で、赤い丸で囲った量子ビットの結合数を増やすために右側の量子ビットと対になっている様子（これをchainという）

　「すると、対になる片方の量子ビットは『0になれ』と周りからいわれてるのに、もう片方の量子ビットは『1になれ』と周りからいわれることがある。1つの量子ビットならアニーリングの過程で最終的にどちらかに定まるが、2つに分けてしまっているせいで答えが定まらない」（同）

　「この後処理をどうするかというアルゴリズムが複数あって、従来のAPIでは簡単に指定できた。後処理アルゴリズムのうち、経験的に性能が良いのが『C』で、悪いのが『A』とすると、これまではCを選べば良かった。しかし、新しいAPIバージョンになってからは自動的にAが選ばれるようになってしまった」

　このため、大関准教授の研究室では新しいAPIの仕様を調べ、手動でCのアルゴリズムを適用しているといいます。APIの変更で、こうした問題が他の箇所でも起きていると大関准教授は話します。

　「使いやすさを重視してライトユーザーを増やそうとしたのかもしれないが、それで『解けないじゃん』といわれるのは大損だと思う。この件については、D-Wave Systemsにも改善の要望を伝えている」

そもそも「巡回セールスマン問題」は量子アニーリング向きではない？

　「巡回セールスマン問題が解けない」という意見に対しては「ハードやソフトの問題を調整すれば解ける」と答えた大関准教授ですが、その一方で「そもそも量子アニーリングは巡回セールスマン問題を解くのに向いていない」と、一見矛盾した見解を示しています。