>>107
>> んじゃ、量子コンピュータ向けの暗号理論って意味ないの?
> 意味ないです (と言い切ってしまおう)。

他の人に誤解されるかもしれないから「共通鍵暗号については意味ないです」って言ってちょ。
(もちろん、後の文を読めば >>107 さんが共通鍵暗号のことを言ってるのは明らかなんだけど。)

で、量子コンピュータができても共通鍵暗号は破れないって意見には同意。
量子コンピュータは素因数分解や離散対数問題は解けても
NP完全問題は解けないって意見が支配的だしね。
だから、ナップサック問題(これもNP完全問題)を利用した公開鍵暗号に
再び注目が集まっているわけで。(量子公開鍵暗号ってやつね)

>>109
あまり詳しくないんだけど、Shorのアルゴリズムって計算途中の情報を格納する
必要があるから、全部で3N qubitぐらい必要じゃなかったっけ?
どっちにしろ、Nの定数倍ってのは間違いないけど。