kono@ie.u-ryukyu.ac.jp (Shinji KONO) writes:

> 河野真治 @ 琉球大学情報工学です。
> 
> In article <86d54h1ttz.fsf@bsd2.4bn.ne.jp>, Yoshitaka Ikeda <ikeda@4bn.ne.jp> writes
> > ニュースを読む限りでは、16qubit(Quantum Bitなのでqubitなのです
> > cubitだと長さの単位になっちゃう。)の量子コンピュータの開発、
> > ということですね。
> 
> 16だと単純サーチに負けるんだけど、64だと現状で勝てる状況に
> ないので、意味があると思う。そこまでいけば...

素因数分解は、単純なサーチじゃないので、もっとでかいビット数がいけます。
現状だと512ビットで1ヶ月くらい。(古典計算機で)

そのへん、定量的な話がこの辺に出てます。
2年以上前だからちょっとふるいけど。

> > たぶん、共通鍵暗号の法はステップ数が公開鍵暗号より大きくなるはずなので、
> > もうちょっと強度はあると思う。
> 
> それは瞬時に解きたい場合ですね。64qubit あると、その計算力を
> 使ったcrack手法は、いくつかありそうですね。

実はここら辺よくわかってないです。
素因数分解をするためのアルゴリズムはShorが示してますが
共通鍵暗号をとこうというときの適正なアルゴリズムはわかっていません。

> もっとも、16qubit でも雑音にむちゃくちゃ弱そう。何千回に一辺
> しか正解が出ないとかだったら、いやだなぁ。

やはり、最低64qubitはないとお話にならないと思う。
そろそろ、64ビットでもなんとか古典計算機で探索可能になりつつあるし。

-- 
I LOVE SNOOPY!  でつ
Yoshitaka Ikeda mailto:ikeda@4bn.ne.jp
My Honeypot: honey@4bn.ne.jp  <-don't send this address