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

　「自分の講演では、量子アニーリングで巡回セールスマン問題をやってはダメと伝えている。理由は、組合せ最適化問題の中でも難しい問題で、ガチガチの制約条件を守らないといけないから」

　「巡回セールスマン問題は1人が順に都市を回っていく問題だが、量子アニーリングは磁石のスピンが隣のスピンにどんな影響を与えるのか（イジングモデル）という物理現象を扱うもの。巡回セールスマン問題には、物体どうしの相互作用を考慮する要素はないので、イジングモデルに当てはめることはできても、解くのが得意とはいえない」

　大関准教授は、8都市の問題を例に挙げ、縦軸に都市、横軸に時間を取った表をホワイトボードに書きます。

　「例えば時刻1に都市3に行くとする。もう時刻1には他の都市に行けない。時刻2以降では都市3を選べなくなる。このように2重の制約条件がある」と説明。その上で、「現状の量子アニーリングはノイズなどの問題で必ず最適解を返せるわけではないため、本来は0となるべき量子ビットが1になることもある。同時刻に複数の都市で1が出てしまう、もしくは同じ都市に複数回1が出てしまうような結果が返ってくると、解として使えず、後処理で修正しようがない」と、大関准教授は量子アニーリングで巡回セールスマン問題を解く際の問題点を指摘します。

難しいものは難しい

　制約条件の問題以外に、大関准教授は「問題自体の難しさ」についても指摘します。

　「巡回セールスマン問題は計算量理論で『NP困難』といわれる、解くのが難しい問題。そのため、『量子アニーリングで巡回セールスマン問題を速く・精度良く解けるか』という問いに対しては、『量子アニーリングだろうが量子コンピュータだろうが、難しいものは難しい』が答えになる」

　「物理プロセスとして、衝突など『2つのものの間に生じる相互作用』を考えられるのが量子アニーリングの良いところなのに、巡回セールスマン問題にはそういう要素がない。2重の制約の問題もある。けれど多くの人は組合せ最適化問題として巡回セールスマン問題を例にしがちで、量子アニーリングの成功体験が得られないままになってしまっている」──大関准教授は、組合せ最適化問題の例に巡回セールスマン問題ばかりが挙げられていることも、量子アニーリングの性能に対する誤解につながっていると話します。

　それでは、量子アニーリングではどんな問題を解いてみるのがいいのでしょうか？

量子アニーリングでは何を解いたらいいのか

　大関准教授は、「うちの研究室では、独フォルクスワーゲンがD-Wave Systemsとともに行ったタクシーの渋滞解消問題をまずは解かせ、量子アニーリングの感覚をつかませている」といいます。

この記事の著者

関連記事

• 

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

• 

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

• 

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

• 

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

• 

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