どうも、いつも割り切れない気持ちで生活している吟遊詩人です。
前回に引き続いて、量子コンピュータの解説、やっていきますよ。
今回は因数分解についてお話します。
量子コンピュータによって私たちの生活はどう変わるの？
素因数分解は難しい？
前回の記事の最後の方に” 因数分解はまず間違いなく最高に難しい問題です。 ”と書きました。因数分解は”最高に難しい問題”なのでしょうか？
というか、そもそも”難しい問題”とはどういうことでしょうか？
ある問題を解く困難さを扱う数学は、計算複雑性理論と呼ばれる分野です。
計算複雑性理論では、ある対象とする問題の複雑性を複雑性クラスに分類して、その困難さを考えていきます。
まあ、いろいろな複雑性クラスがあるのですが、簡単な方のクラスとして”P”が、難しいほうのクラスとして”NP”が存在します。
計算量理論におけるPとは多項式時間（polynomial time）で解ける判定問題の集合である。
Wiki：P
NPは、複雑性クラスのひとつで、Non-deterministic Polynomial time（非決定性多項式時間）の略である（「Non-P」ないしは「Not-P」ではない）。
Wiki：NP
多項式時間で解けるかどうかということが重要になってくるわけです。
例えば足し算なんかは、X+Yという２つの足し算に１秒かかるとして、X+Y＋Zになると２秒かかる……という風に、一つ数が増えるごとに時間が１秒ずつ増えていくとします。
そうするとｎ個の入力変数に対して、計算時間はn-1秒であり、これはnの1乗なので、nの多項式時間と言えるわけです。
逆に多項式時間で解けないNP問題の例としては、巡回セールスマン問題などがあります。
巡回セールスマン問題（じゅんかいセールスマンもんだい、英: traveling salesman problem、TSP）は、都市の集合と各2都市間の移動コスト（たとえば距離）が与えられたとき、全ての都市をちょうど一度ずつ巡り出発地に戻る巡回路のうちで総移動コストが最小のものを求める（セールスマンが所定の複数の都市を1回だけ巡回する場合の最短経路を求める）組合せ最適化問題である。
wiki: 巡回セールスマン問題
この問題では、まずXとYという都市が与えられたら、｜X-Y｜という2都市間の距離を計算します。 XとY とZという3都市が与えられたら、 ｜X-Y｜と ｜X-Z｜と ｜Z-Y｜ とそれぞれの都市の距離を出した後、 ｜X-Y｜ ＋ ｜Z-Y｜ か ｜X-Z｜ ＋｜Z-Y｜ のどちらのルートが短いか判断する必要があります。
2都市 の場合計算しなければいけない都市間の距離は１だったのに対し、3都市の場合 計算しなければいけない 都市間の距離が３となっています。
結局与えられた都市の数nに対してｎC２の組み合わせで計算量が増えていくため、計算量が指数的に増えていき、多項式時間では解けない、難しい問題となります。
で、素因数分解ですが、基本的にある数nが与えられた場合、nよりも小さい素数（正確には√nより小さい素数）で総当り的に割り算をしていく必要があります。
これは 多項式時間で 解くことはできない問題です。
まあ、もう少し効率的な解法（アルゴリズム）もあるわけですが、どれも 多項式時間で 解けないため、素因数分解はNPに属する問題と考えられています。
（まあ、効率的なアルゴリズムを見つけられていないだけかもしれませんが。）
そういった意味では、”因数分解はまず間違いなく最高に難しい問題です。 ”と言えます。
（余談：計算複雑性理論ではPはNPじゃないよね予想という問題があり、ミレニアム懸賞問題の一つなので、解くことができれば100万ドルもらえます。）
量子コンピュータは素因数分解が得意？
素因数分解が難しいというのは何となく理解してもらえたと思いますが、量子コンピュータでどのようにこの複雑な問題を解くことができるか見ていきましょう。
25という数の素因数分解を例にとりましょう。25は2進数では11001です。
11001 を素因数分解する場合、通常のコンピュータでは0010（２）、0011（3）、0101（５）、……と小さい素数から順に割り算をしていきます。そして、
11001 ÷ 0010 ＝割り切れない
11001 ÷ 0011 ＝割り切れない
11001 ÷ 0101 ＝ 0101
と3回の計算を行った後、25＝5×5という素因数分解の答えにたどり着くわけです。
では次に量子コンピュータの場合を見てみましょう。前回のお話で 量子コンピュータ は0と１の重ね合わせである量子ビットを使えると言いましたが、ここでは量子ビットをφと書くことにします。4ビットの量子ビットを φ φ φ φ とします。
25を素因数分解します。
11001 ÷ φ φ φ φ ＝ 0101
です。また、ふたを開けて確認したら φ φ φ φ ＝ ０１０１でした。
（ ＾ω＾）・・・・・・
ありのまま今起こった事を話すぜ、おれは量子ビットで素因数分解をしていたと思ったら いつのまにか計算がおわっていて、しかも量子ビットの状態が決まっていた
な… 何を言っているのかわからねーと思うが おれも何をされたのかわからなかった… 頭がどうにかなりそうだった…催眠 術だとか超スピードだとかそんなチャチなもんじゃあ断じてねえ もっと恐ろしいものの片鱗を味わったぜ……
スパコンで1万年かかる計算を3分20秒で 終了させることができる量子コンピュータの強強な能力、お判りいただけたでしょうか。
量子コンピュータが私たちの生活を脅かす脅威になる？
「量子コンピュータが素因数分解が得意なことはわかったけど、私別に素因数分解とか興味ないし、タピオカミルクティーしか興味ないし、別にいいわ」
という方、甘甘のあんまみーやと言わざるを得ません。
素因数分解を高速に解くことができるということは、我々の生活を支えている技術を根本的に破壊する危険性があるのです。
また話が長くなったのでRSA暗号の話はまた次回にします。
今回のまとめ
- 素因数分解は（多分）メッチャ難しいよ
- 量子コンピュータは素因数分解をメッチャ解くよ
- 素因数分解がメッチャ解かれると、世界がメッチャやばいよ
- 量子コンピュータは素因数分解界のザ・ワールドや～
以上です。
そーめんブログ 