量子コンピュータができること、できないことをできるだけ分かりやすく聞いてみた――量子情報勉強会 宇津木健さん

かまぷとゆうこのデベロッパーズ☆ラジオ #2 量子情報勉強会 宇津木健さん

NP困難、NP完全って何？

ゆうこ　GoogleやIBMなど、いろんなベンダーさんが、量子コンピュータ、量子アニーリングに注目しているニュースを見ますよね。

かまぷ　あれ、Googleさんは、量子コンピュータベンチャーのD-Waveに投資してるんですよね？

宇津木　そうそう。D-Waveは、量子アニーリングを実際に装置として最初に作った企業で、そこが発端となってこの研究がどんどん進んでいるんです。それに目をつけたGoogleが投資したりとか、それを元に新しいコンピュータを作ろうとしてるとか、今はそういう状況になっているらしいです。

かまぷ　今回の収録にあたって色々調べてて、D-Waveのホワイトペーパー（「Programming with D-Wave:Map Coloring Problem」）を見てみたんですけど、全然わかんないですね。

宇津木　Map Coloring Problemって、これあれですよ。地図の塗り分けの問題。いかに効率よく塗れるかなっていう問題をD-Waveのマシンで解いたらどうなるっていう話ですかね、これ。

かまぷ　この2013年の記事「D-Waveの量子コンピュータは本物か」も見たんですけど、結構辛口で、ここデブ☆ラジで紹介するのは良くないかも知れない。でもD-Wave社を批判するにしても、この方、D-wave社は論文で批判をひとつづつ回答しているという点は評価するって書いてあったり……。

宇津木　2013年は、まさに出始めだったんです。みんながそれ「本当に量子計算されてるのか」って議論してた状態で。で、現在は、一応一定の水準で量子計算されているようだという状態らしくて。でもそれが、今の普通のコンピュータと比べてどのぐらい性能がいいかとか、得意な問題、不得意な問題があるので、そのあたりを解明して、本当に我々が便利に使えるようにするにはどうすればいいかという研究をしている段階です。

かまぷ　こういうのを読むにも、基礎知識がないから、読んでも止まっちゃうんですよ。例えばこの「NP完全」と「NP困難」って、NPって果たしてなんの略ですか？

宇津木　そうですよね。急に出てきますもんね。だから敷居が高い。NP完全とNP困難ってよく出てくるんですけど、NPの略は、まずPの略がpolynomial（ポリノミアル）。

かまぷ　カタカナで聞いてもわかんない。

宇津木　これは何かっていうと、多項式。x²＋x＋1とかね、なんかいろんな項がある。

かまぷ　それを超わかりやすく言うとなんですか？

宇津木　これを超わかりやすく言うと、これxの上に4とか、数字がついてるじゃないですか。xの右肩に数字が付いてるやつ（xⁿ）を多項式っていうんですよ。って覚えて下さい。

かまぷ　あ、なんかやったかも。

宇津木　でしょ？ で、これが逆になることもあって、4の上にxがつくこともあるんですよ。それが多項式じゃないっていうこと。

ゆうこ　4のx乗（4^x）ってことですよね。

宇津木　そうそう、xの4乗（x⁴）と4のx乗（4^x）の違いが、ここでは重要になってきます。大丈夫ですか？

かまぷ　とりあえずハイって言っときます。で、Nは？

宇津木　Non-deterministic（ノンデターミニスティック）かな。なんの言葉かっていうと、計算量を評価する時の言葉になっていて。

かまぷ　計算量を評価。ふうん。

宇津木　なにか問題があります。さっきの巡回セールスマン問題とか、いろんな問題が世の中にはありますと。でこの問題は、どのぐらい計算するのが大変ですかって定義してあげると、あ、じゃあこいつは解けるけどこいつは解けないとか、それがわかる。それをクラス分けしてるんですね。

　これ以上難しい問題はもうお手上げだとか。ここまでだったら頑張ればいけるとか。で、その解けるか解けないかの境界線を規定してるのがこのNPとか、Pとかっていうクラスに分けていて。で、NP完全のクラスの問題はけっこう難しいんですよ。そしてNP困難っていうクラスは、さらに難しいんですよ。だからNP困難の問題ですって言われたら、「うわ解けねえじゃん」って思って下さい。

計算量クラスのイメージ（1）（宇津木さん作成）

計算量クラスのイメージ（2）（宇津木さん作成）

かまぷ　フフフ。女心みたいな感じ？

宇津木　そう、女心みたいな感じ。女心は、ものすごい組み合わせを計算しないとどれが正解の気持ちかわかんないから。だから全通り考えればいいんだけど、それ無理だから。

かまぷ　なんか今すごく冷めた空気が流れてますけど、大丈夫？

宇津木　大丈夫。ていう感じで、NP完全とかNP困難て言われたらすごく難しい、普通のコンピュータじゃ解けない問題だよっていうのがこれの意味するところ。

　もう少し細かく言うと、その入力の数に応じてどのぐらい計算時間が増えるかというのも表していて。1個入れて計算時間が1秒だった、2個入れて2秒、3個入れて3秒、なら、10個入れたら多分10秒だし、100個入れたら100秒だろうと。それなら計算できるんじゃない？ 思うとしますね。

　でも1個入れたら1秒、2個入れたら5秒、3個入れたら100秒、4個入れたら1000秒だったとするじゃないですか。そしたらこれ、100個も入れたらものすごい時間になっちゃう。この、計算する時間がめちゃくちゃ増えてしまうものを、NP完全やNP困難って呼んでます。

で、普通は業務で多分そういう計算あまりしないと思うんですね。特にSEの方とかは。だけど、人工知能の研究だとデータがめちゃくちゃあるし、それに対して出さなきゃいけない答えがすごく抽象的だったりする。

ゆうこ　じゃあ量子コンピュータが今後普及してくると、いろんなデータからまだ見ぬ世界が開けてきそうですね。