@yuichirominato 2019.01.21更新 265views

【暗号】D-Waveマシンで制約充足問題を用いた乗算回路での素因数分解をみる。


はじめに

RSA暗号では素因数分解を解くことで、暗号が解読されてしまうという。これまでいくつかの方法で素因数分解をみてきたが、今回は制約充足問題(CSP)を用いた乗算回路を用いた素因数分解を見てみたい。

これまで素因数分解を解く方法として、位相推定(shor)

最小値問題に落とし込む方法

VQEをつかって二進数の乗算とグレブナー基底を使う方法

などを紹介してきた。今回はD-Waveが公式に紹介する方法で行ってみたい。

ちなみに今回はD-Waveとのパートナーによって、D-Wave社の様々な取り組みを和訳することを快諾してくれたことに大変感謝いたします。今回はD-Wave Leapにおける基本チュートリアルを和訳して進めます。

乗算回路の逆算による素因数分解

整数の因数分解は掛け合わせた数字を見つけるプロセスです。たとえば、15は3と5の掛け算です。 多くの素因数分解は非常に時間がかかるという性質を使って、最も広く使用されている公開鍵暗号化システムであるRSAの基礎となっています。 D-Waveの量子コンピュータは、まったく異なる方法で数を因数分解します。乗算回路を制約充足問題に変えることで、量子コンピュータが固定の出力から入力を計算することを可能にします。つまりこれは、掛け算を逆に計算できるということを意味します!では始めてみましょう。

ここでは、D-Waveのマシンを使った掛け算の因数分解を行いますが、制約充足問題に掛け算を落とす回路を作ることで、掛け算を逆から行うことができるという性質を利用します。

掛け算を行う数字を選びます。

今回は12を因数分解するデモを行います。今回は小さな数字から始めますが、実際にはより複雑で大きな問題にも同様のテクニックが使えます。

既存計算機の方法

古典的なコンピューターは非常に大きな数を因数分解するのに非効率的です。 数が少ない場合は、順番に要素を順番に除算していくというアプローチは簡単です。ただし、数が増えるにつれて、この一連の単純な操作はすぐに非常に時間がかかります。

既存計算機では12/2=6,12/3=4,12/4=3,12/5=2.4,12/6=2,12/7=1.714のように1つずつ順番に数を割っていくことで数を探します。

論理回路を用いた乗算

因数分解は古典的には難しい場合がありますが、結果を確認するのは簡単です。 これは、2つの要素が有効かどうかを確認するために使用できる単純な乗算回路です。 係数は左側に入力され、それらのバイナリ値は回路内のゲートを通って流れ、右側に積が得られます。 この乗算回路を制約充足問題に変換することによって、既知の出力値から一組の入力値を計算することができます。これは因数分解と同等です。

制約充足問題と乗算回路

乗算回路は、相互接続された論理ゲートで形成されたより一般的な論理回路の一例です。 右側の色で示されているAND、半加算器、および全加算器ゲートは、入力と出力に対する制約を指定します。 制約充足の観点から問題を定式化すると、関係から方向性が排除され、回路を逆に実行することが可能になります。 特に、このデモで使用されているプログラミング手法は、すべてのブール論理および幅広いクラスの制約充足問題に適用できます。

量子コンピュータに落とし込む

制約充足問題は、一度に1論理ゲートずつ量子コンピュータにプログラムすることができます。 ここに示すように、ANDゲートは2つのバイナリ入力と1つの出力の間の制約問題です。

両方のバイナリ入力が1の場合にのみ1を出力します。 二項制約は、一組の量子ビット(量子ビット)および結合器(コネクタ)にマッピングすることができ、それによって、制約入力および出力に関連するそれらの量子ビットは、高い確率で、制約と一致する値を見つけます。 ANDゲートの場合、入力に関連付けられたキュビットがすべて1の値に落ち着いている場合に限り、出力に関連付けられたキュビットは1の値を求めます。それ以外の場合は、0の値を求めます。 量子コンピュータは、論理回路のすべての制約を満たす入力値と出力値を同時に探します。

新しい回路を作る

回路内のすべてのゲートに変換を適用すると、量子ビットと結合へのマッピングが作成されます。下に示す量子ビットのネットワークでは、全加算器(元の回路から)が黄色の五角形に、半加算器が青い四角形に、そしてANDゲートがピンク色の三角形に変換されます。)。 量子コンピュータ内で回路内の相互接続に一致する「ワイヤ」を作成することは可能ですが、ワイヤの数と長さを最小にすると問題マッピングがより効率的になります。 相互接続された入力と出力のセットは、情報を複数のワイヤに分散させるのではなく、1つのキュビットに縮小されます。

量子コンピュータで実行

乗算回路の出力上の二進数は、因数分解したい数に固定することができます。 これを量子コンピュータで実際に計算しました。計算時間は諸々含んで0.016秒で実行ができ、解が2種類でました。

最後に

これで、量子コンピュータが、幅広い種類の問題を解決するための新しいアプローチを可能にする方法を見てきました。 乗算回路を変数のネットワークとそれらの間の関係に変換する方法を示しました。 この方法で表現された問題は方向性を持たないので、(このデモで行ったように)入力を見つけるために出力を設定したり、出力を見つけるために入力を設定したり、あるいはその間の何かができます。 D-Wave量子コンピュータで解決できる制約充足問題はどこにでもあります:スケジューリング、組み合わせ回路の故障診断、ポートフォリオの最適化、トラフィックルーティングなど。

ということでざっくりみてきました。この方法では論理回路を組んで行けば、アニーリングによって入力値を出力値から逆算できます。

Recommended


CONTACT

info@mdrft.com

ブログトップへ Wikiへ移動

量子コンピュータ一般

量子ゲートアルゴリズム

量子アニーリング一般

量子アニーリングアルゴリズム

BlueqatSDKの使い方