本記事では、量子計算機の原理について、従来(すなわち現代)の計算機のそれと比較しながら、直感的な説明を試みる。
より理論的な説明については、それに特化した文献を参照されたい。
(正直、前提知識無しでは死ぬほど理解に苦しむことが懸念される。)
また、量子計算機が実現した場合、何が起こるのかについても簡単に説明する。(正直、かなりやばいことになる。)
なお、本気時は現時点では完全なるただの読み物であり、これを読んでいただいたからといって明日からすぐに何かの役に立てるということはない。
が、だからといって実現の見込みのない夢の世界の机上論を披露するつもりもなく、目と鼻の先の近い将来に起こるかもしれないものすごい出来事について、議論することが本気時の目的である。
#目次
1.従来の計算機と量子計算機の比較
1-1.従来の計算機の特徴とその限界
1-2.量子計算機の原理
2.量子計算機の応用
2-1.「素因数分解の困難性」の解決
2-2.RSA 暗号の破壊
2-3.世界の終わり
#1.従来の計算機と量子計算機の比較
まずは、われわれが今使っている従来の計算機と量子計算機の特徴をそれぞれ整理し、両者の違いを見ていくことにしよう。
##1.1 従来の計算機の特徴とその限界
「従来の計算機は処理を直列的に行い、並列的には行えない」という言葉を聞いたことのある読者は多いことだろう。
どういうことかをかいつまむと、「従来の計算機が 1 度に表現できるのはごくわずかな個数の極めて小さい整数に限られる」ということである。
64bit 型計算機を例に、上で言っていることの具体例をいくつか挙げよう。
注意:
わざわざ解説するようなことではないかもしれないが、64bit 型計算機とは、CPUのサイズが 64bit(2 進法で 64 桁)の計算機である。
各 bit には 0 または 1 のいずれか一方が記憶される。
64bit をはみ出した数値計算を行う際には、メモリ・ポインタ、果てはハードディスクの領域が用いられ、処理速度が激減する。
例1.1.
64bit の範囲で表現できる整数は、わずか
0、 1、 2、 · · · 、 2^{64} − 1 = 18446744073709551615
ぽっちである。つまり、高々 20 桁を超える数値計算を行おうとするだけで、メモリの読み書き及びポインタの利用が必須となるのである。
例 1.2.
64bit 型計算機が CPU のみで計算可能な処理は非常にしょぼい。例えば、 1 から 18 までの和
1+ 2+ 3+ 4+ 5+ 6+ 7+ 8+ 9+ 10+ 11+ 12+ 13+ 14+ 15+ 16+ 17+ 18
を計算するだけでも手一杯である。
その理由は下記の通りで、上の計算を 2 進数で表現してみれば明らかである。
1 + 10 + 11 + 100 + 101 + 110 + 111 + 1000 + 1001 + 1010 + 1011 + 1100 + 1101 + 1110 + 1111 + 10000 + 10001 + 10010
演算子 + を取り除いて羅列すると、
1101110010111011110001001101010111100110111101111100001000110010
となり、これは 64 桁になる。
実際には、演算子 + を表現するにも bit を消費するため、これすら不可能であろう。
例 1.3.
64bit 型計算機では、(アルゴリズムを工夫しない限り)100 桁の整数の約数を求めるのに、人間 1 人の一生分の時間くらいは優に消費する。
筆者が試したところでいくと、18 桁の整数の約数を求めるのに 1 週間かかった。
これは、64bit 型計算機ではなく大型計算機を用いたところで大して変わるものではない。詳しくは 2.1.2 節を参照のこと。
結局何が言いたかったかというと、従来の計算機では処理速度に限界があるということである。
そして、その限界は良くも悪くも世の中に大きく影響を与えている。
それをわざわざこんな具体例までくどくど挙げながら強調した理由は、当然、量子計算機には事実上処理速度に限界がないからである。
##1.2 量子計算機の原理
前節では
• 従来の計算機は処理速度に限界があること
• その理由は「1bit に同時に保管できるのが 0 か 1 のどちらか 1 つだけであるから」
だということをそれぞれ説明した。
と、いうことは、なんと量子計算機は「1bit の中に 0 と 1 を同時に保管できる」のである。これは信じられないほどすごいことであり、次の命題を示唆している。
命題 1.4.
d bit の量子計算機は、
0 ～ 2^{d} −1
までの全ての整数を同時に表現可能である。
例 1.5.
例 1.1 で見たように、従来の 64bit 型計算機では
2^{d} −1
というたった 1 つの大して大きくもない整数を表現するだけで、
64bit という CPU 記憶域を全部消費してしまう。
それに対して、64bit 型量子計算機では、同じ 64bit を使って
0 ～ 2^{d} −1
までの全ての整数を同時に表現可能である。
この事実が処理速度をどれほど速めるかについては、言うまでもないであろう。
例 1.6.
量子計算機は、
0 ～ 2^{d} −1
までの全ての整数を同時に表現するのにわずか d bit しか消費しない。
「わずか d bit」と表現した理由は、これを従来の計算機で行おうとした場合と比較して著しく小さい bit 数だからである。
ちなみに、同じ全ての整数を従来の計算機で同時に表現するためには、およそ
d * 2^{d}
bit 必要である。d = 64 で考えてみるとより両者の差を実感しやすいであろう。
さて、ここまでで量子計算機が従来の計算機と比較して想像を絶するほど信じられないすごさを誇ることを述べてきたわけであるが、これは文字通りにわかには信じがたいことである。
というのも、「1 でありなおかつ 0 でもある」などというのは論理学に大きく反するからである。一般には下記のように書ける。
公理 1.7.
a は常に a であり、 a でないということはない。
つまり、a が a であると同時に b でもあるならば、必ず a = b である。
わけのわからないことに感じる読者もいるかもしれないが、われわれはこの事実を生まれたときから暗黙の了解の下、生きている。
例 1.8.
• 1 + 1 が 2 であって 2 でないなどということはない
• 自分が人間であって人間でないなどということはない
• 今目の前を人が通り過ぎていったが、同時に、今目の前を誰も通り過ぎなかったなどということはない
では、この常識外な量子計算機(つまり1であり0でもあるなどというへんてこりんな状態)はいったいどのようにして実現されるのであろうか。
もちろん、現時点で量子計算機はまだ実現されていないためその答をここに書くことはできないが、その代わりに、研究者の間で立てられている最も有力な仮説を直感的に書いてみることにする。
仮説 1.9（量子計算機のbit構造）
量子計算機における 1bit は、アンモニア分子 1 つから成るとされている。
アンモニア分子とは、窒素原子 N が 1 つと水素原子 H が 3つくっついた状態のものであり、化学の記法で NH3 と表される。
が、こういう難しい話は理解を困難にするだけなので、「へぇそうなんだ」程度で十分である(筆者も、化学はさっぱりだし理解度もその程度である)。
量子計算機の 1bit は「1つの黒い頂点と3つの白い頂点からなる正四面体である」と考えてほしい(筆者の中では窒素が黒、水素が白のイメージ)。
正四面体がわからない読者は、「正四面体」でググれば写真だの説明だの出てくるので、ぜひやってみてほしい。
さて、量子計算機の内部は、上のような正四面体から成るbit 列で構成されている。
このとき、各正四面体は自由に向きが変わるものとする。
そして、
・黒い頂点が他の３つの白い頂点のどれよりも上にあるときを 1
・黒い頂点が他の３つの白い頂点のどれよりも下にあるときを 0
と定義する。
この定義が意味を持つかどうかは量子計算機が実現してみないとわからないが、現代の研究段階ではそのようにしているようである。
さて、ここが最も重要なポイントであるが、正四面体をくるくる回してみればわかるように「黒い頂点が一番上でもないし一番下でもない」という状態を作ることが可能である。
この状態をどうやら「1 でもあり 0 でもある」と考えるようなのである。
つまり、アンモニア分子でこのように bit 列を作成することが本当にできてしまえば、晴れて量子計算機が完成するというわけである。
何だか狐につままれたような話であるが、実現していない研究の過程というのは、えてしてこんなものであるため、どうか落胆せず最後まで読み進めていただけると幸いである。
次章では、ぶっ壊れた性能を持つであろうこの謎めいた量子計算機とやらが実現した場合、それが与える世の中への影響について主に述べていくことにする。
#2 量子計算機の応用
前章では、「量子計算機は従来の計算機と比べて爆発的レベルですごい」ということをひたすら述べてきた。
もし量子計算機が実現すれば、今までできなかったものすごくいろいろなことができるようになる。それは大変めでたいことであるのだが、それと同時に脅威でもある。
つまり、できないからこそ世の中のバランスが保たれているということもあるのである。
本章では、
• 従来の計算機では(今のところ)解けないが、量子計算機ではいとも簡単に解けてしまう問題の代表である「素因数分解の困難性」
• 素因数分解が困難でなくなるとたちどころに敗れてしまうという、全世界で使われている RSA という暗号システム
• 全世界で使われている RSA 暗号が破壊されるということは、すなわちそれは世界の終を意味する
という流れで進めていく。
##2.1 「素因数分解の困難性」の解決
###2.1.1 素因数分解とは
素因数分解とは、基本的には 2 以上の整数に対して施される操作であり、一般的に下記のように定義される。
定義 2.1.
2 以上の整数 n に対して、その全ての「素数である約数(素因数)」を計算することを、n を素因数分解するという。
例 2.2.
(1) 6 の素因数分解は 2 ∗ 3 である。
(2) 1001 の素因数分解は 7 ∗ 11 ∗ 13 である。
(3) 9991 の素因数分解は 97 ∗ 103 である。
(4) 10001 の素因数分解は 10001 である。
筆者が計算を誤っているかもしれないので、各自確認されることを推奨する。
###2.1.2 素因数分解の困難性
6 や 1001 のような小さな整数であれば、その素因数分解を求めることは暗算でもできてしまうが、9991 の素因数分解は暗算では簡単ではないはずである(少なくとも筆者にとっては)。
この事実は(従来の)計算機をもってしても言えることであり、桁数が大きくなると素因数分解は難しくなる。
例 2.3.
素因数分解に関する具体的な世の中の現状を簡単ではあるがまとめておこう。
(1)何の工夫もせず単純な試し割り法(2で割ってみて3で割ってみて5で割ってみて...というもの)で素因数分解をする場合、大型計算機を使ったとしてもせいぜい20 桁程度の整数を分解するのがやっとである。それを超えると、現実時間(われわれが待っていられるだけの時間)では完了しなくなる。
(2)個人用 PC でも実装が容易な Pollard の ρ 法や楕円曲線法と呼ばれるアルゴリズムを用いれば、50桁から80桁程度の整数を現実時間内に素因数分解することができる(これは筆者もこの手で試した)。
(3)大型計算機向けの2次のふるい法や数体ふるい法と呼ばれるアルゴリズムを用いれば、100桁から200桁程度の整数を現実時間内に素因数分解することができる。
(4)300桁を超える整数については、(従来の計算機を用いる限り)現実時間内で素因数分解するためのアルゴリズムは現状存在しない。
(1) 及び (2) については手書きで簡単に実装して試すことができるので、興味のある読者はぜひやってみてほしい。
###2.1.3 離散対数問題と素因数分解の関係(オプション)
本節は高校 3 年程度の数学の知識(合同式)を仮定するため、数学アレルギーの読者は読み飛ばしていただいてもストーリー全体には差し支えない。ただし、大変興味深い内容となっている。
世の中にはもう 1 つ、離散対数問題と呼ばれる、素因数分解に並ぶインパクトを持つ未解決の問題がある。内容は下記の通り。
問題 2.4 (離散対数問題)
a、 b を整数、 m を 2以上の整数とするとき、合同式
a^{x} ≡ b (mod m)
を解くことは一般には難しい。
この離散対数問題を「素因数分解と並ぶ」とまで言ってわざわざここに記したのには意味がある。というのも、離散対数問題が解けてしまえば素因数分解の困難性もたちまち解決してしまうのである。下記に、離散対数問題が解けたものと仮定した場合に素因数分解がどのように実現されるのかを簡単に記すことにする。
アルゴリズム 2.5.
(1) N を大きな整数(300桁くらい)とする。今、N の真の約数(1 でも N でもない約数)を求めたいものとする。
(2) N と互いに素な(つまり N と 1 以外に共通の約数を持たない)整数 a を適当に選ぶ。このような a を見つけるのは非常に容易である。なぜなら、 N と a が互いに素でない時点で、 N の真の約数が見つかったことになるから(ユークリッドの互除方等で a、 N の最大公約数を容易に計算できる)。
(3) 合同式
a^{r} ≡ 1 (mod N)
を満たすような最小の正の整数 r (すなわち法 N における a の位数)を求める。
これは離散対数問題(問題 2.4)そのものであるため、本来は難しい。
しかし、今は離散対数問題の解決が仮定されているため、これは容易である。
(4) もし r が奇数ならば、操作を中断し、(2) に戻る。今、 r は偶数である。
(5) もし
a^{r/2} ≡ −1 (mod N)
ならば、操作を中断し、(2) に戻る。当然
a^{r/2} not ≡ 1 (mod N)
であるため、今
a^{r/2} not ≡ ±1 (mod N)
である。
(6) 2 つの整数
a^{r/2} + 1 と N
の最大公約数が、求める N の真の約数である。
このように、離散対数問題(問題 2.4)が解けてしまうと、素因数分解の困難性も解決してしまう。そして、それは量子計算機の計算力をもってすれば現実となる。
###2.1.4 量子計算機による解決
2.1.2 節において、「大きな整数の素因数分解は、従来の計算機を用いる限り現状では難しい」ということを述べた。
しかし、量子計算機が実現したとなると、話は別である。
今、N を 300桁の大きな整数とし、この真の約数を求めたいとする。
思い出してほしいのが、量子計算機は 0 から N − 1 までの全ての整数を、高々 300bit の中で同時に扱えるということである(命題 1.4 を参照)。
つまり、たった 300bit あるだけで、N を 2 から N − 1 までの全ての整数で割ってみることなどいとも簡単ということになる。
どれくらい簡単であるかのちょっとした具体例を示そう。
例 2.6.
64bit 型量子計算機で 300桁の整数 N の素因数を計算する手間は、従来の64bit型計算機で print 分を使って N を画面に表示する手間とほぼ同じである。
つまり、一瞬でできるということだ。
結論をまとめると、量子計算機が実現すると素因数分解が容易にできるようになってしまうのである。
注意 2.7.
2.1.3 節を読んだ読者には、離散対数問題(問題 2.4)もまた量子計算機を用いることで容易に解決してしまうことが理解されることだろう。
つまり結局は、量子計算機の実現によって、離散対数問題と素因数分解の困難性はもろとも解決してしまうのであった。
時節以降ではいよいよ、量子計算機の実現、すなわち「素因数分解の困難性」の解決によって、何が起こってしまうのかについて概説する。
##2.2 RSA 暗号の破壊
###2.2.1 世の中における RSA 暗号の重要性
ご存知の通り、世の中には個人や組織の安全を守るための暗号方式が数多く存在する。
しかし、世の中のほぼ全てのセキュリティシステムにおいて「絶対に安全である」として利用されているのが、RSA 暗号方式と呼ばれるものである。
例 2.8.
皆さんおなじみの SSL/TLS 通信で使われているのももちろん RSA 暗号である。
「RSA は本当に安全なの?」と疑う読者もいよう。そのような方は、
• 自身の銀行口座がある日突然空になってないか始終気にするべきである。
• 親しい友人と LINE 等で内密なやり取りをすることなど恐ろしくてできないと感じるべきである。
• のんきに QIITA を閲覧したり投稿したりしている場合ではないことに気づくべきである。
少々オーバーな表現だったかもしれないが、これで「皆が暗黙のうちに RSA が絶対に安全であると納得させられている」という事実をお伝えできたことであろう。
このように、RSA 暗号は世界中で非常に重要な役目を担っており、もし破壊でもされようものならそれはそれは大パニックとなる。
さて、時節に進む前に、驚異的な一言をお伝えしなければならない。(なぜなら、時節はオプションであるため。)
RSA 暗号の安全性は、「素因数分解の困難性」に依存する。
###2.2.2 RSA 暗号の原理と安全性(オプション)
本節は高校 3 年程度の数学の知識(合同式)を仮定するため、数学アレルギーの読者は読み飛ばしていただいてもストーリー全体には差し支えない。ただし、大変興味深い内容となっている。
本節の目的は、RSA 暗号の仕組みを概説するとともに、
• 素因数分解が困難なためひとまず RSA 暗号は安全であると了解されている
•「素因数分解の困難性」が解決すれば RSA 暗号もたちまち破られてしまう
という事実関係を理解することである。
十分大きな整数 N に対して、その素因数分解を N = pq (p、 q は素数)とする。このp 及び q を求めることは非常に困難であるとする。
そのような N を利用して、以下では文字列 T を暗号化する方法、そして複号する方法を概説する。
コンピュータの世界では、文字列は全て整数であると考えて良いので、文字列 T は正の整数であるとする。
このとき、 T は N と互いに素であるとして良い。なぜなら、そうでなかった時点で N の素因数分解がユークリッドの互除法から容易に得られてしまい、N の仮定に矛盾するからである。
さて、ここで
de ≡ 1 (mod φ(N))
となるような整数 d、 e を用意する( φ(N) はオイラー関数)。このとき、 e はどこぞの馬の骨に知られようと関係ないが、 d は決して誰にも知られてはならない。
今、 T を暗号化する。
C ≡ T^{e}(mod N)
となるような正の整数 C を T の e による暗号文という。
そして、e を公開鍵(または暗号鍵)という。
つまり、 N 及び e があれば誰でも文字列 T を暗号化できるというわけである。
実際、N 及び e は誰に知られても構わない。
なぜなら、N、 e、 C から T を高速で計算する方法は現状存在しないからである。
しかし、もし d が手元にあれば、以下の式より C を複号することができる。
C^{d} ≡ T(mod N)
理由を詳しく見てみよう。
C^{d} ≡ (T^{e})^{d}(mod N)
= T^{de}
= T^{1+lφ(N)} (l は整数)
= T((T^{φ(N)})^{l})
≡ T·1^{l} (mod N)
= T
d を秘密鍵(または複号鍵)という。この d は誰にも知られてはならない。
さて、 N の素因数分解の困難性を仮定したのは、 d を知られないためである。
もしも N の素因数 p が計算されてしまったら、当然 q も求まってしまう。
p、 q が求まれば、
φ(N) = (p − 1)(q − 1)
として φ(N) が計算される。
φ(N) が計算されれば、 e を用いて d がユークリッドの互除法より簡単に求められる(詳しくはユークリッドの互除法の教科書を参照のこと)。
以上の構成より、 p、 q、 φ(N)、 d のいずれか 1 つでも知られてしまったら Tが読まれてしまうというわけである。
このように、RSA 暗号は素因数分解が困難だからひとまずは安全であり、素因数分解が簡単にできるようになることは RSA 暗号も簡単に破れることに他ならないのである。
###2.2.3 量子計算機による RSA 暗号の破壊
2.2.1 節の最後に、「RSA 暗号は素因数分解が難しいことに頼っている」という事実を予告した。
その後、2.2.2 節においてその根拠を説明した。
つまり、素因数分解が簡単にできるようになれば、RSA 暗号は破れるのだ。
そして、2.1.4 節で述べた通り、量子計算機の実現によって素因数分解は簡単にできるようになるのだ。
RSA!敗れたり!!
##2.3 世界の終わり
量子計算機の実現はもはや目前まで来ていると言います。
それを喜んでいる場合ではありません。
今までの RSA と同等の安全性を誇る、素因数分解の困難性に頼らない暗号方式が切実に必要なのです。
それが量子計算機の実現より早く発見されなかったなら...何が起こるかは散々説明しましたね。
技術のある方、研究がお好きな方、お願いします。
一刻も早く新しい暗号方式を発明してください。
私も全力でそれに取り組んでいるところです。
これは緊急を要します。
世界の終を防ぐため、自身の生活を守るため、どうかよろしくお願いいたします。