グローバーのアルゴリズムは探索回数を√Nにするが、256ビットあるため、それは128ビットに過ぎない。よって問題はない。
最近、ブロックチェーンの文脈で、これをやたらと強調する内容が出てきました。
これは、解が1つの場合です。
ところがマイニングの仕組みは古典のASICでも採掘できるようにdiffパラメタを利用して探索空間を圧縮することで解の個数を大幅に増加させているので、古典のASICでも10分に1回、正解を引ける仕組みになっております。
1ゼタのハッシュレートなら、その圧縮は70ビット前後なので、解の個数は256 – 70 = 186、すなわち「2の186乗前後」もあります。逆に、これだけの解があるため古典でも当たりを引けるのです。確率論から、それは自明です。
よって、探索空間の70ビット。ここにグローバーのアルゴリズムは作用するため、√2^256ではなく、√2^70となります。このため量子セキュリティ的に崩壊している解釈となります。
