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

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

[井上輝一，ITmedia]

　量子コンピュータの方式の一種とされる「量子アニーリング」は、考えられる組み合わせの中から最適なものを選び取る「組合せ最適化問題」の計算が得意とされていますが、ITmedia NEWSの取材の中ではこんな異論がありました。

　「巡回セールスマン問題が解けない」──。

　巡回セールスマン問題は、1人のセールスマンが複数の都市を回るときの最短距離を求める問題で、組合せ最適化問題の代表的な例としてしばしば挙げられます。

　しかし、量子コンピュータのベンチャー企業であるMDRの湊雄一郎社長は、量子アニーリングについて「実際に解きたい問題を式に変換しにくい上、巡回セールスマン問題が解けない」と以前に指摘していました。「4都市の問題でも解けるか怪しい」とも。

　「代表的な組合せ最適化問題が解けない」となると、量子アニーリングの実用性について疑問符が付くことになりかねません。

　この意見に対し、東北大学で量子アニーリングの研究や産業応用を進める大関真之准教授は「われわれの感覚では『解ける』。だが、解けないと感じた理由も分かる」と複雑な反応を示します。どういうことでしょうか。

（前回の記事：量子コンピュータの「ある計算でスパコン超え」　4年前の「PCより1億倍速い量子コンピュータ」との違いは？）

　大関准教授は、論点として「量子アニーリングマシンのハードウェアやソフトウェアの変更に伴う問題」と、「巡回セールスマン問題自身の特性」の2つを挙げます。

大関真之准教授。「われわれの感覚では『解ける』。だが、解けないと感じた理由も分かる」と複雑な反応を示す

ハードとソフトにしばしば起こる「改悪」

　大関准教授は、カナダD-Wave Systemsが作る量子アニーリングマシンのハードウェアとソフトウェアが抱えている問題をこう説明します。

　「われわれの感覚では『巡回セールスマン問題は解ける』。なぜなら、われわれが使い始めてから2017年後半ごろまではD-Waveマシンのチップの性能が良くて、きちんとした解を出していたから。しかしD-Wave Systemsは、チップのメンテナンスなどの理由でマシンを複数台運用しており、利用できるマシンの型番が時折変わることがある」（大関准教授）

カナダD-Wave Systemsの量子アニーリングマシンに搭載される量子アニーリングチップ（D-Wave Systemsの説明動画より）

　「あるとき、学生から『全然良い解が出てこない、一体何が変わったのか』と相談された。そんなことないだろうと思ったものの、どうやらチップが変わったことによる性能の違いらしいことが分かった。これまで4回ほどチップが変わった。その度に計算結果の傾向も変わった。だから、触った時期によっては『パフォーマンスが良くない』という感想を持たれるのは仕方がないこと」（同）

　ハードウェアの性能にブレがあり、型番によってはあまり良い答えが出なかった可能性があると話す大関准教授。「現在なら『D-Wave 2000Qの5』という型番が、ノイズが減って良い性能だ」といいますが、「しかし今度はソフトウェアにアップデートがあり、使い勝手が変わってしまった」と、ソフトウェア側の問題を指摘します。