はじめに
量子コンピュータの発展が本格的なものとなってきました。これまでは夢の計算機と思われていた量子コンピュータが実際にできつつあり、セキュリティ上の懸念も出てきました。そのセキュリティ上の懸念とは今のコンピュータでは現実的に計算が困難であるということに立脚した暗号の仕組みが、量子コンピュータの登場によって破られてしまうということです。
最近では論文も精度を上げてきていて、2048ビットのRSA暗号と呼ばれるものが８時間で破られるというレポートも出ています。
"How a quantum computer could break 2048-bit RSA encryption in 8 hours"
使う実機は量子ゲート
量子コンピュータには様々な方式や形式があります。その中でも今回の暗号に関わるのは、量子ゲート方式と呼ばれるマシンです。
さらに量子ゲート方式の中でも汎用量子計算と呼ばれるエラーを許容しない、真のデジタル計算が必要となりますが、現状の量子コンピュータではそのデジタル化回路が搭載されておらず、アナログ計算機のような挙動をするため、まだ暗号を解くことができません。
デジタル化の機能をつけるためには誤り訂正と呼ばれる機能をつける必要があり、「量子ビット数を増やす」のと「量子ビットのエラー」を抑えるという両方の性能指標を上げる必要がありまあす。
そのため近年ではすぐに解かれる心配はありませんが、着々とハードウェアの開発が進んでおり現実的な対策が求められ始めています。
影響範囲は大きい
文章の保護をするための暗号化や、インターネット上での認証をするための暗号、最近では暗号化資産や仮想通貨呼ばれる暗号のコモディティ化によって様々なところに影響が出現します。暗号解読が進むとそのようなシステムに立脚したセキュリティが根底から覆されることになるため、きちんとした対策を取る必要があります。
一方で対策は容易ではありません。最近では通信などにも使われていますのでIoT機器やインフラ機器など社会に浸透したインフラとなってしまうと交換自体が10年20年スパンで行われるために容易な更新ができなくなり、混乱を招くことになります。
30年後を見据えた対策が今から必要とされているという分野になっています。
対策は新暗号
特に国の重要機密事項を守るためには新暗号と呼ばれるものが必要となります。量子コンピュータの原理を理解し、量子コンピュータの性能を超えるような暗号が必要とされており、さまざまな形でそれらが実現されようとしています。
国の重要機密などを保護するための暗号は最も優先度の高いものですので、すでに世界中では2023年での対策を進めて急ピッチで物事が進んでいます。
「新暗号技術23年メド採用 量子コンピューターでも難解」 / 日本経済新聞
https://www.nikkei.com/article/DGXMZO46921640T00C19A7EE8000/
また新暗号には数種類候補があるので、それらの検証や実装が日々進められています。
また、最近ではカナダのベンチャー企業のISARAがブラックベリー対応として新しい暗号を提供するなど世界中での危機意識と対策が取られています。
早速概要を見てみます。
量子コンピュータで暗号を解く方法は見つかっており、有名で名前がついています。それがshorのアルゴリズムです。shorのアルゴリズムはこちらのスライドにまとまっているのでそれを元に概要をまとめてみます。
あまりshorのアルゴリズムを体系的に理解し、具体的な量子回路まで落としてきちんと論じている資料が少ないので、世界中でも珍しいものとなっていると思います。きちんとpythonで量子回路までを作っています。
「Shorのアルゴリズム」
https://speakerdeck.com/gyudon/shorfalsearugorizumu
素因数分解
２以上の全ての自然数は素数とその積でできている。
例) 15 = 3*5
自然数Nが大きい数の場合にそれを素数の積に戻すのは困難と言われています。効率的なアルゴリズムが存在するかどうかがわからないので、現在はそれをよりどころとして自然数Nを利用して暗号のシステムが作られています。
量子コンピュータではこの自然数Nを素数の積に戻す「素因数分解」と呼ばれる作業が効率的にできることがわかっています。
位数発見問題
量子コンピュータの上で動くshorのアルゴリズムはこの「素因数分解」を「位数発見問題」というものに置き換えて解くことができます。
Nで割った余りを求める計算をモジュロ演算と呼び、この演算を利用することで暗号の周期性を見つけることができて、その周期性を「位数」と呼んでいます。この位数が見つかれば暗号の周期性がわかるために素因数分解ができるというわけです。
位数
x^a mod N = 1 となるaが存在しそれが周期と一致することがわかっています。つまり、どんな問題でも周期を求められ、周期を求めれば素因数分解ができます。
ですので、x^r mod N = 1 となるrが求まるとNを素因数分解できることがわかっています。ということで、量子コンピュータを使ってrの値を効率的に求めます。
手順
早速手順を見てみましょう。
１、前処理。明らかにわかる答えは省く。（現在のコンピュータ）
２、位数発見。位数発見アルゴリズムで位数rを探す。（量子コンピュータ）
３、rから素数を計算する。（現在のコンピュータ）
となります。１の処理は偶数をのぞいたり、簡単な掛け算でできていることがわかるものを計算機で計算して除外します。２の手順から見てみます。
位数発見の手順
位数発見の手順は量子状態と呼ばれる量子コンピュータで作れる波の状態を作り、その波の角度に対応する値を調べることで求めることができます。
では、量子状態をすぐに作って角度を測定すればいいのですが、その量子状態を作るためにはあらかじめ角度がわからないといけないという本末転倒なことになっています。そこで、角度がわからなくても量子状態が作れるように少し量子状態を変化させます。それがモジュロ演算です。
より具体的に手順を見てみます。
量子位数発見アルゴリズム
具体的なアルゴリズムの手順は下記の通りです。
１、量子ビットを準備
２、x^j mod Nの回路を作り、実行する。
３、逆量子フーリエ変換を行い、上記の回路の答えを小数点の位相の形で取り出す。
４、得られた位相はs/rという形になっているので連分数を使ってrを求める。
量子ビットを準備する
量子ビットは「入力用の回路」と「出力用の回路」と、「補助用の回路」の三種類用意します。量子ビット数を節約する回路と、量子ビット数を使って時間を節約する回路がありますので好みに合わせて設計します。解くべき問題によって量子ビット数は決まっています。
量子回路を作り実行する
次にモジュロ演算回路と呼ばれる回路を作ります。こちらは汎用計算と呼ばれる通常の量子コンピュータ用のゲート操作を使った通常の計算回路です。
こちらの論文が参考になります。こちらの論文に作りかたが書いてあるのでこの通り作れば動きます。多少苦労はしますが。
Quantum Networks for Elementary Arithmetic Operations
V. Vedral, A. Barenco, A. Ekert
(Submitted on 16 Nov 1995)
https://arxiv.org/abs/quant-ph/9511018
10進数を2進数に直した後、特定の回路を組み合わせて回路を作ります。
これらを組み合わせると最終的に量子計算だけでx^a mod Nの回路を作ることができます。
量子フーリエ変換
実は今回の量子回路で作った結果は量子状態と呼ばれる通常人間は直接観測をすることができない状態として存在します。それらを位数という角度の決まった値で取り出すために、その量子状態の波の状態を小数点の具体的な数値として取り出す操作が必要となります。それが量子フーリエ変換です。
既存計算機の高速フーリエ変換とにていますが、再帰計算が高速化されていたりします。それも簡単にこちらにまとめてあります。量子状態がきちんと取り出せるのがすごいです。
この量子フーリエ変換された結果を測定という操作を通じて01のバイナリ値で取り出し、それぞれが小数点の値に対応しています。
連分数
そして最後の作業です。取り出された数値はs/rという分数の形となっています。今回欲しいのはrのほうですので、小数点を分数に直すために連分数という形を使います。
小数点の1のくらいを順番にみていくことで分数の形に逆算することができます。これに関しては資料を見てみてください。
https://speakerdeck.com/gyudon/shorfalsearugorizumu?slide=21
また、具体的な解き方やコードが書いてあります。
「0.1388888888888889を分数で表すと何になるか?」
https://qiita.com/gyu-don/items/af1d96b97c076548714a
うまく連分数で分数の形状で取り出せたら分母が求めたいrになります。
まとめ
このように丁寧にみていくとそんなに難しいものでないと思います。逆によく見つけたなという気はしますが。。。数学的なことを理解して行こうと思うととても大変ですが、概要を掴むためにより簡単に理解して評価できるような仕組みや取り組みは必要と思いました。
今回は勉強会の題材として取り上げましたが、量子状態の作り方、取り出した結果から位数rを求める連分数の部分などは世界的にみても資料が足りていないのでなかなか学習が進まないという課題に答えるような資料になっていましたので世界に貢献できてよかったのではないかと思います。
ソフトウェアとしてはshorのアルゴリズムは世界中で実現されているので、あとはハードウェアの実現度合いなどを注意深くみていく必要があると思います。最近ではきちんとした研究でハードを真面目に取り組んでいるので、より量子コンピュータの発展が早まるのではないかなと感じています。
"Full-Stack, Real-System Quantum Computer Studies:
Architectural Comparisons and Design Insights"
https://arxiv.org/pdf/1905.11349.pdf
もはや夢のコンピュータではなくなった量子コンピュータがどこまでいくのかこれから楽しみです。以上です。