【書き起こし】量子コンピュータが役に立つ問題(量子アルゴリズム)【量子コンピュータ入門5】
(00:00) 量子コンピュータが早く計算できる問題と は良い漁師アルゴリズムが見つかっている 問題です 漁師アルゴリズムとは量子ビットをどの ように制御すればその問題を解くことが できるかを教えてくれるレシピです 今回は量子コンピュータが高速に処理 できるもう第の中から素因数分解と漁師 探索という2つの問題について解説したい と思います 最も重要な漁師アルゴリズムとして所はの アルゴリズムが挙げられます ショアのアルゴリズムとは 素因数分解を高速に行うことができる漁師 アルゴリズムです さて素因数分解ができることがなぜ重要な のでしょうか それは rsa 暗号を破ることができる からです rsa 暗号とはインターネットにおける 通信の安全性を担保している暗号技術です わたしたちが安心してネット上で クレジットカードを使ったりメッセージを
(01:05) 送ることができるのもこのrsa 暗号の おかげです この rsa 暗号は非常に大きな数字を 素因数分解することが難しいという事実を 安全性の根拠にしていますどういうこと でしょうか まず例えとして15を2つの素数の積に 分解してみましょう 答えはさんかける5です簡単ですね それではこちらの数字はどうでしょうか 正解はこのようになります この例からもわかるように 対象とする数が大きくなるほどその数を2 つの素数に分解することが非常に難しく なります 実は非常に大きな数の素因数分解を古典 コンピュータで行うとも膨大な時間が かかるのですそしてスーパーコンピュータ でさえも現実的な時間内に rsa 暗号 を破ることはできません
(02:11) その結果 通信の安全性が担保されているということ です 化し大規模な量子コンピュータは昭和の アルゴリズムを用いることで素因数分解を 高速に実行できるのです しかしこれの意味するところは もし大きな数の素因数分解が高速に実行 可能になればインターネットにおける通信 の安全性が崩れてしまうことになります そこで気になるのが現在の量子 コンピュータが rsa 暗号を破ること ができるののかということです 結論から申し上げますとそれはできません 安心してください 現在の量子コンピュータでは所はの アルゴリズムを実行するにはまだまだ計算 リソースが足りません 次に紹介するのがグローバーの アルゴリズムです このアルゴリズムは整理されていない データベースから特定のデータを探し出す
(03:15) 際に用いられる探索アルゴリズムです 例えば大事なアカウントのパスワードを 忘れたとします パスワードは4桁の数字で 0000から 9999までの1万通りの可能性があり ます 基本的にはパスワードを総当たりで 打ち込んでみて正しいか正しくないかを 判定します最悪の場合 00000から 9999までの1万回の問い合わせで正解 にたどり着くことになります 平均でも1万通りの組み合わせの半分の後 前回は問い合わせることが必要ですしかし グローバーのアルゴリズムを用いて量子 コンピュータでパスワードを探すとなんと 100回程度の問い合わせで済むのです つまり n 会の問い合わせが必要な問題 を ルート n 会で階にたどりつくことが できるわけです
(04:18) 今回は量子コンピュータを使って高速に 処理できる問題の一例をご紹介しました 良い漁師アルゴリズムが量子コンピュータ のパワーの秘訣です つまり量子コンピュータはハードウェアの 研究はもちろんのことを了しアルゴリズム の開発といったソフトウェアの研究も非常 に重要なのです
