6/21 マルレク・サブゼミ 「3時間で学ぶ Shorのアルゴリズム入門」について

6/3 マルレク「暗号技術の現在」のフォロー・アップのセミナーとして、6月21日次のセミナーを開催します。

　日時；　2019年6月21日 19:00~22:00
　場所：　五番町グランドビル 7F / KADOKAWA セミナールーム
　テーマ：「3時間で学ぶ Shorのアルゴリズム入門」
　申し込みページ：https://shor.peatix.com/view

講演概要

6/3のマルレク「暗号技術の現在」では、暗号技術が現在の「公開キー暗号/RSA暗号」から「ポスト量子暗号」に大きく変わろうとしているという話をしました。こうした変化を引き起こした最大の原因は、25年前に発見された「Shorの素因数分解アルゴリズム」です。

RSA暗号は、大きな素数p,q 二つの積である大きな数Nが、たとえNを知っていても、現在のコンピュータでは、その素因数p,qを求めることがとても難しいという事実をその基礎にしています。公開キー暗号は、コンピュータでも分解できないこのNを、事実上、皆の前に公開するという暗号方式です。Shorは「量子コンピュータを使えば」、Nの素因数分解が極めて高速に可能になることを発見しました。それは、「公開キー暗号/RSA暗号」が、簡単に破られるということを意味しています。

ではなぜ、こうした発見が25年間も「暗号技術に対する脅威」とは見なさなかったのでしょうか？　その理由は簡単なものです。それは、「量子コンピュータ」が、すぐにも実現する技術とは見なされなかったからです。現時点でも、大きなNに対して、Shorのアルゴリズムでその素因数を求められる量子コンピュータは存在しません。

ただ、20年後40年後は、どうなっているでしょう？　

近年になって、量子コンピュータの「実現可能性」について、大きな認識の変化があります。基本的には、いままでよりかつてなく多くの人が「いつか、確実な時期はわからないが、量子コンピュータは実現するだろう」と考えるようになってきました。Shorのアルゴリズムに対する関心が、新たに高まっているのは、そうした背景があります。NSAやNISTが、「ポスト量子暗号」への動きを本格化しているのは、当然のことだと思います。

1. 量子コンピュータではなぜ高速な計算ができるのか？

　量子コンピュータでは、n個の入力に対して、その全ての状態の2^n個の「重ね合わせ」について同時並行的に計算ができます。普通のコンピュータと比較して「指数関数的」な高速化が可能となります。

2. 量子コンピュータの出力は、どう取り出せるのか？

　ところが、話はそう簡単ではありません。出力結果を取り出すということは、結果を観測することですが、観測したとたんに、量子の状態は、2^n個の重ね合わせの状態から、n個の状態のいずれかに変わってしまいます。これでは、せっかくの「重ね合わせ」による高速化の結果が台無しです。実は、入力についても、任意の量子状態を、あらかじめ準備するのは難しいのです。

3. 量子の状態と「位相」

　実は、例えば、二つの量子の状態 ( |0 + |1> )/√2 と( |0 − |1> )/√2 とは、明らかに異なる状態なのですが、観測によっては区別できません。|1>にかかっている +1, − 1 という係数を「位相」というのですが、異なっていても二乗して 1になるような位相を持つ量子の状態は、観測によっては区別できないのです。

4. Shorのアルゴリズムと「位相」の評価

　Shorのアルゴリズムというのは、量子コンピュータの超並列計算の能力を使って、バリバリと指数関数的な数の割り算をするアルゴリズムではないのです。その中心部分は、この「位相」の評価のアルゴリズムです。少し難しいのですが、セミナーではその概略を説明します。

5. 「位相」の観測から、関数の「周期」を求める。

6. 「周期」から、素因数を求める。

最後は、だいぶ省略しましたが、基本的な流れは、こういう感じです。

アルゴリズム、量子回路の細部は理解できなくとも、大まかなアルゴリズムの概略が説明できればと思います。それは、量子の世界の不思議な性質を知るいい機会になると思います。

多くの方の参加を期待しています。