ITとか鳥とか

技術のこととか。飼鳥(オカメインコ)のこととか。気になったこととか。基本的には備忘録。

「量子アニーリング」で「巡回セールスマン問題」は解けないのか?

はじめに

量子コンピュータの方式のひとつである「量子アニーリング」。(あるいはアルゴリズムの一種ともいわれる) この方式は組合せ最適化問題に特化しており、計算能力の優位性を説明する際には「巡回セールスマン問題」が引き合いに出されることがよくあります。 しかし、量子アニーリングでは巡回セールスマン問題は解けない」という指摘があります。 これは事実なのでしょうか? 関連記事がいくつか出されていますので、その中身を確認しつつポイントを整理しておきたいと思います。

対象者

量子アニーリングによる組合せ最適化問題が気にな方(≠専門家)

巡回セールスマン問題とは?

問題の設定はとてもシンプルで、「複数の都市を最も効率よく巡回するためのルートはどれ?」というものです。 下図のように全ての点を一筆書きで辿った場合に、線の長さが最も短くなるパターンはどれか、ということになります。

f:id:sik_bug:20191221223114p:plain 画像引用 wikipedia Talk:Travelling salesman problem

このような類の問題は「組合せ最適化問題」と言われます。他の例として「ナップサック問題」があります。これは「ナップサックに詰め込んだものの価値が最も高くなる組み合わせは?」という問題設定になります。

シンプルなようですが、実際は非常に大きな計算が必要になります。 例えば巡回セールスマン問題の場合、都市の数をnとすると巡回ルートはn!通りが考えられます。

  • 10都市の場合、$3,628,800$ 通り
  • 20都市の場合、$2.4×10^{18}$ 通り

※参考:京都大学 永持研究室「簡単そうで難しい組合せ最適化 簡単そうで難しい組合せ最適化」

10都市だけでも大きな組合せ数ですが、そこから都市数が倍になっただけで組合せ数が爆発的に増えています。 60都市になると、宇宙の原子の数($10^{80}$)にもなるため、現実的に計算は不可能です。

量子アニーリングでは巡回セールスマン問題が解けない?

古典コンピュータとの比較で巡回セールスマン問題が引き合いに出されるということは、量子コンピュータの得意な問題領域として考えられているわけですが、これが解けないというのは、いったいどういうことでしょうか・・??

順番に見ていきます。

MDR社 湊氏によれば

上記サイトを要約すると以下のとおり。

  • 実際に解きたい問題は量子アニーリング方式(イジングモデル)に落とし込みにくく、実務的ではない。
  • 海外の量子コンピューティング関連企業も同様の結論に至っている。
  • 4都市の問題でも解けるかどうか怪しい。

実際に現場で起こったことを経験的に捉えられたものだと思います。 量子コンピュータを使いこなすスキルのない私にとっては「そうなのか・・・」と思わざるを得ません。

これに対し大関准教授が反応し、解説をしています。

東北大学 大関真之准教授によれば

AI+ 『本当に量子アニーリングは「巡回セールスマン問題」が解けないのか? 東北大・大関准教授の視点』

2つの論点で解説されていますので、順番に要約していきます。

量子アニーリングマシンのハードウェアやソフトウェアの変更に伴う問題

ハードウェアの問題

  • 2017年後半ごろまではD-Waveマシンのチップ性能が良く、きちんとした解を出していた。
  • D-Waveは、チップのメンテナンスなどを理由に、マシンを複数台運用している。
  • 時期により利用できるマシンの型番が変わる(チップが変わる)ことにより、性能の違いが出ている。
  • 実際、変更のたびに計算結果の傾向が変わった。
  • 結果、触った時期によっては『パフォーマンスが良くない』という感想を持たれるのは仕方がない。

ソフトウェアの問題

  • D-WaveマシンのAPIが、2019年の初めくらいから使いやすくなった。
  • これは、APIを扱う上で難しい部分が隠ぺいされるようになったためである。
  • この変更に伴い、最終的なパフォーマンスにつながる「後処理」のアルゴリズムも隠蔽されてしまった。
  • それまで「後処理」のアルゴリズムは複数から選択できたが、隠蔽によりデフォルト値固定になってしまったた。
  • 経験的に性能を改善するための「後処理」の処理選択が出来なくなった。

②巡回セールスマン問題自身の特性

  • 巡回セールスマン問題は量子アニーリング向きではない。
  • 組合せ最適化問題の中でも難しい問題で、制約条件が厳しいためである。
  • 現状の量子アニーリングはノイズなどの問題で必ず最適解を返せるわけではない。
  • 同じ都市を2回以上まわるような解が出てしまうと、後処理で修正しようがない。
  • 組合せ最適化問題の例に巡回セールスマン問題ばかりが挙げられていることが、量子アニーリングの性能に対する誤解につながっている。

結局のところ

そもそも量子アニーリングマシンはヒューリスティックな解が得られるものであり、理論的な保証はありません。 上記「ハードウェアの問題」はこのような特性上、マシン(チップ)ごとの性能を均質化することが難しいのだと思います。

湊氏が実際にどのようなことを試し、どのような結果を得たうえでの発言なのかはわかりませんが、「必ずしもいい解が得られるわけではない」というのは双方主張の共通項であり、事実なのだろうと思います。

また、上記「ソフトウェアの問題」は「だったら、すぐに前のバージョンに戻せばいいじゃないか」と思われるかもしれませんが、ビジネス戦略上そうもいかない部分もあると思います。 なぜなら、ソフトウェアの抽象化は量子コンピュータのユーザーを増やすために非常に重要な取組みであるからです。

量子コンピュータは専門性が高いため、アプリ・レイヤで「いかに難しい処理を隠蔽するか」が大きなポイントになります。 D-Wave社はこれにチャレンジしているのだと思います。 しかし、大関准教授が指摘しているように、結果的にいい解が得られなければ意味がありませんので、なかなか困った問題になっているわけです。

おわりに

AIの黎明期には「AIを使っても、必ずしも最適な解が得られるわけではない」ということがよく言われていました。 今となっては常識となりましたが、新しいテクノロジーの普及段階では、大なり小なり誤解がつきものであり、これを解消していく取組みも先駆者の重要なタスクになるのだと思います。

まだまだ課題の多い量子コンピュータですが、さらなる発展を期待しつつ引き続きウォッチしていきたいと思います。