12/12/05 17:13:50.29 F/QyiuJg0
>>619
>量子コンピュータって実物はそんなに速くないらしいな
量子コンピュータが高速であるとされる理由は、計算速度が速いからではなく、その超並列性にある。
あえて正確ではないが直観的な説明をすると、通常のコンピュータでは整数の足し算をするのに、
入力が0+0なら出力0、0+1なら1、1+0なら1、1+1なら10と個別に4通りの計算をしなければならないが、
量子論的な重ね合わせ（0でもあり1でもある状態）を扱える量子コンピュータはこの4通りの計算を
同時に実行することができる。
1桁なら差は小さいが、これが2桁になると、通常のコンピュータで16通りの計算が必要なところも、
量子コンピュータならば先程の計算を2回実行するだけで済んでしまう。これが超並列性だ。
要するに、計算の規模（上の例では桁数）が大きくなるに従って、通常のコンピュータでは計算時間が
倍々で増える（指数時間）のに対し、量子コンピュータでは比例かべき乗でしか増えない（多項式時間）。
量子コンピュータのこの特質から、公開鍵暗号は無力化される。なぜなら、公開鍵暗号とは計算時間が
倍々で増える性質を使うものだから。どういうことかと言うと、技術者が頑張って前の1000倍の性能の
（通常の）コンピュータを作って暗号を破っても、鍵の10桁増やせば暗号の安全は保たれるということ。
しかし、量子コンピュータは、例えば鍵の元々の長さが1024桁なら、10/1024だけ長い時間待てばいい
（或いは、演算器を10増やしてもいい）。鍵の桁数をいくら増やしても、増えた分だけ長く計算すれば
（或いは、演算器の個数を増やせば）、それで前と同様に暗号を破れてしまうわけだ。