2
票
Accepted
量子コンピュータによってソートは速くなりますか?
比較ソートに限定した場合、長さ n の配列に対する量子アルゴリズムの時間計算量は Ω(n log n) になる[1]ので、漸近的には古典アルゴリズムの場合と変わりません。
「比較ソート以外の場合はどうなのか?」「他に制限を課した場合はどうなるのか?」についてはよく知りません。英語版 Wikipedia の "Quantum sort" ...
- 2.3万
2
票
量子コンピュータが通信系(とくに ssl, aka https) に与える影響は?
今までの暗号化方式ではセキュアではなくなると思います。
WiFiでいうWEPは危険なのでWPA2を使いましょう、と同じ問題ではないでしょうか(WPA2にも脆弱性があったようですが…)。
最近NICTが新しい暗号方式を発表していましたので、こういった量子コンピュータでも解読されないような暗号化方式が主流になっていくのだと思います。
https://www.nict.go.jp/press/2018/...
- 2,124
2
票
量子コンピュータが通信系(とくに ssl, aka https) に与える影響は?
そもそも量子コンピュータが実用化(個人が所有できる程度)される技術水準になれば、量子通信も完成しているはずです。このため、量子コンピュータによって暗号化が破られたとしても、量子通信によって通信の完全性/機密性が保たれると思います。部分的な通信データはタップされると思いますけどね。
- 21
Only top scored, non community-wiki answers of a minimum length are eligible