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

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

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

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

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

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

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

この記事の著者

関連記事

• 

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

• 

  「海外は量子アニーリングに見切り」──ハードもソフトも開発する量子ベンチャー「MDR」に聞いた「量子コンピュータの今」

• 

  SSL通信も量子コンピュータの前では無意味に？　今から備えるべき「耐量子コンピュータ暗号」とは

• 

  「量子理論の副産物に過ぎなかった」──東芝の「量子コンピュータより速いアルゴリズム」誕生秘話

• 

  東大、光量子コンピュータに進展　大規模な「量子もつれ」を生成、常温・省スペースの量子計算へ