量子コンピュータとは何か？
昨日の「量子暗号はビジネスになるか？」という記事に対して、heroさんからコメントいただきました。
量子暗号の開発目的は、現状でのセキュリティ向上ではないと思います。
量子論を利用したものに、量子コンピュータと言う代物があります。今のコンピュータとは計算の原理が異なるコンピュータで、もしそれが実現すると、現在使われている公開鍵暗号などを簡単に解析することができるそうです。現状の暗号が意味を成さなくなるため、量子コンピュータでも解析できないような暗号が必要になって、量子暗号が研究され始めたと聞きました。
将来、量子コンピュータが広まっていくと予測をたてたならば、実現した時に備えて量子暗号を開発することがビジネスチャンスになるのではないでしょうか。
（一部）同意です。
本当に近い将来、暗号に使おうと思って研究しているのだとしたら「センス悪すぎ」かと思いますが、かなりの長期を見越した基礎研究なんでしょう。
もしかすると、遠距離間をつなぐ通信の安全確保というのは「シロウト向けのわかりやすい説明」で、量子コンピュータ内の回路（総延長はそれなりの距離になると思いますので）の設計などを考える場合にも役立つのかも知れないですね。（単なる想像。）
暗号の強度の構造
この量子コンピュータの登場で「公開鍵暗号」の安全性が危機にさらされるということですが、どういうことでしょうか。
そもそも、現在の公開鍵暗号が安全なのは、下記の図でいう「NP」という集合に属する問題だから、ということになってます。（・・・はずです。）
出所：計算基礎論 理学博士 足立暁生著（オーム社）P121
NPとは、「非決定性チューリング機械でサイズnの多項式時間で計算できる問題のクラス」ということ。
これに対して上記のPとは「決定性チューリング機械でサイズnの多項式時間で計算できる問題のクラス」。
「決定性チューリング機械」というのは、現在のコンピュータの方式と理解していいかと思います。つまり、NPに属する暗号とは、現在のコンピュータのプログラムで解くと、暗号の鍵長nの多項式時間では解けない（n乗とかの時間がかかる）可能性がある暗号ということです。
このNという集合とNPという集合は、図では完全には一致しない集合のように描かれていますが、現在わかっているのは、PがNPに含まれることだけで、もしかしたらP≠NPじゃないのかどうかは数学的に証明されていません。つまり、うまいアルゴリズムを見つけ出せば、公開鍵暗号も量子コンピュータを使わずとも瞬時に解ける、という可能性が絶対無いことは証明されてません。
この「P＝NPかどうか」という問題は、未だに解決されていない数学の超難問とされてますが、数学者の多くは、おそらくP≠NPだろう、と予想しているようです。
量子コンピュータとはどんなコンピュータか？
問題は量子コンピュータの出現がなぜ公開鍵暗号を危機にさらすか、ということ。
量子コンピュータが単に「演算速度が速い」コンピュータなら、あまり恐れる必要はありません。NP問題では、鍵の長さが増えると鍵の長さnに比例してではなく、n乗などのオーダーで必要とされる演算速度が増えるというのが特徴ですから、例えば量子コンピュータが今のコンピュータより１兆倍早いスピードのものだとしても、（仮に2のn乗のオーダーの時間がかかるとすると、）240≒1兆ですから、たった40bitほど鍵の長さを伸ばすだけで解けなくなるということにもなります。
しかし、いろいろwebを検索して読んでみると、量子コンピュータは今のコンピュータのしくみ（決定性チューリング機械）とは全く違う仕組みのコンピュータのようです。
つまり、P=NPと数学的に証明されるのとは全く関係無しに、NP問題が短時間で解けてしまう、ということのようです。
こちらで、NEC基礎・環境研究所の蔡 兆申主席研究員が、
量子コンピュータが完成した暁には、「素因数分解」や膨大な事象の組み合わせを考えなければならない「NP完全問題」のように、基本的にしらみつぶしに計算しなくてはいけないような、現在のコンピュータが苦手とする計算を瞬く間に解くことができるようになると言われています。
（中略）
ただ、量子コンピュータならどんな計算でも高速になるか、というとそれには少し誤解があります。パソコンで言うCPUの速度が上がるという意味で高速化を実現するわけではないからです。例えば、量子コンピュータで、1+1を計算させたとしましょう。こういった単純計算をした場合は、計算結果が出てくるまでの速度は、今のコンピュータと大差ないと予想しています。すなわち、量子コンピュータは、私たちが計算機として日常使うコンピュータとしては、そのありがたみが感じられないものかもしれません。しかしながら、量子コンピュータが得意とする問題でかつスーパーコンピュータでも膨大な時間を要するような計算をしたい専門家にとっては、夢を可能にするコンピュータだといえます。
と分かりやすく説明してらっしゃるように、どうも通常の演算スピードがそれほど上がるわけではなさそうです。
現在の暗号体系は崩壊するか？
実用化はまだまだ先のようですが、仮にこれができた場合には、どういう問題が発生するのでしょうか。
まず、現在、インターネット上の電子商取引などで口座番号やカード番号などの個人情報をインプットするときに使っているSSLや、メールやファイルの暗号化に使うPGPなどの暗号は、素因数分解の困難性がNP問題であることを利用しているので、もし量子コンピュータが実用化されると解読される危険はあります。
ただし、上述のように、量子コンピュータはNP問題のような特定の問題については現在のコンピュータより桁違いに早く解答を出しますが、すべての問題を早く解けるマシンではない。つまり、対称鍵暗号（総当たり的な攻撃が必要な暗号）の解読もできるというわけではない模様です。実際、量子暗号においても、対称鍵の鍵配送だけを量子暗号でやって、暗号文本文は、その対称鍵で暗号化して送信することを想定した解説などもあります。（つまり、対称鍵暗号は使い続ける想定。）
つまり、量子コンピュータが登場しても、鍵配送問題さえ解決すれば、既存の暗号体系がすべて瓦解するということはなさそうです。
例えば、B to Bの通信なら、両方のサーバーに時々刻々変わる対称鍵（共通鍵）を発生させる装置を据え付けるとか、B to Cでも、例えば第三者の認証機関やデファクトの共通ソフトのようなものをかませて時々刻々変化する共通鍵を使う、というようなことは可能ではないかという気もします。
そういう方法を開発して、今のインターネットの通信網自体を使い続ける方が、新たに光ファイバーから引き直すよりは、はるかに安くつくはずです。また、いくら光ファイバーの上で安全でも、無線や銅線上でも使える暗号でないと、ECなどのB to Cの領域ではマーケットが狭くなりすぎて意味無いでしょう。
それから、中妻穣太さんからもトラックバックいただきました。
「ぬおー、ツッコミたいが時間が…」
ということで、時間がないそうです。
残念ですねぇ。まさに、中妻さんとかがツッコんで来るだろうなあと思って書いたエントリーだったんですが・・・（￣ー￣）ニヤリ
（ではまた。）
参考URL：
NEC研究所、Innovative Engine「量子コンピュータ」（July.16, 2004）
http://www.labs.nec.co.jp/innovative/E3/top.html
nanoelectronics.jp 「量子コンピュータ」
http://www.nanoelectronics.jp/kaitai/quantumcom/3.htm
