@yuichirominato 2019.01.26更新 276views

【shor】数学苦手なおっさんができるだけ根性で大きな数を素因数分解する旅に出る(その1)


はじめに

こんにちは、数学が苦手なのでできればだれかにこのブログを変わってほしいベンチャーのおっさんです。量子コンピュータには位相推定とshorのアルゴリズムという素因数分解や離散対数問題に対応して解けるというアルゴリズムがあります。

実際には位相推定は昔の人が考えたアルゴリズムですので今のマシンでは(ほとんど)使えません。ですが、教科書にのっているうえに学生に聞かれたら困るので、聞かれる前に覚えてしまいたいですが、数学の専門用語が難しすぎてくじけそうです。将来的に誤り訂正されたらできるかもしれないので、覚えておきましょう。

位相推定や波動関数や中に出てくる量子フーリエ変換は全くの素人というわけではなく少し知識がありますので、いきなり飛ぶところもあるかもしれません。

素因数分解解くなら、、、

素因数分解を解くためのアルゴリズムがshorです。Peter Shorさんによって提唱されたすごいアルゴリズムです。学ぶにはとても面白いのでこれを機に最後まで学んでみたいと思います。多少わからないところがあっても最後まで解ければいいのでがんばります。最近では素因数分解を最小値問題に落とし込んで解くものもあり、こちらがトレンドですが今回の目的とはずれるので興味ある方はこちらのブログを読んで大きな問題を解いて見てください。

shorをする前に、、、

shorのアルゴリズムをみたいですが、以前勉強会でものすごく疲れた記憶があります。本当はものすごいたくさんステップがあるのですが、まずは基本の3ステップ見てみます。

1、前処理
2、位相推定
3、後処理

真ん中の位相推定アルゴリズムが量子コンピュータの出番です。前処理と後処理は既存計算機でやります。

参考資料

なんと!日本国内はあまり資料がありませんが、英語は充実してます。ほとんど全てのステップと式が書いてあり、親切なことにIBMサイトでは回路まで書いてあります。なんかできる気がしてきました!

Shor’s Algorithm

https://quantumexperience.ng.bluemix.net/proxy/tutorial/full-user-guide/004-Quantum_Algorithms/110-Shor’s_algorithm.html

Shor’s Algorithm

https://en.wikipedia.org/wiki/Shor%27s_algorithm

今回はIBMのサイトとwikipediaを参考にして見ます。なんかここまでお膳立てされてればできる気がしてきました。。。

位相推定

僕は知ってました周期性を見つけるための位相推定アルゴリズム(PEA)Phase Estimation Algorithmが大事だということを。ここだけが量子計算になります。ですのでまずここを下ごしらえします。まずはここを見て見たいと思います。参考資料は僕の大好きなwikipediaです。

Quantum Phase Estimation Algorithm

https://en.wikipedia.org/wiki/Quantum_phase_estimation_algorithm

どうやらQuantum Phase Estimation Algorithmは、Quantumの力を使って、PhaseをEstimationするAlgorithmのようです。つまり、、、

量子で位相を推定するということです。機能としては、ユニタリ行列の固有値を求めるようです。自信がないので、もちょいwikipediaを探します。

量子力学における固有値問題

固有値というwikipediaを見つけました。

https://ja.wikipedia.org/wiki/%E5%9B%BA%E6%9C%89%E5%80%A4

そのなかに量子力学における固有値問題を見つけました。

量子力学においては固有値問題が次のような形で現れる。まず、系の状態は、「状態ベクトル」というもの(波動関数ともいう)で表現されると考える。そして、その状態ベクトルは、シュレーディンガー方程式に従って時間的に変化すると考える。このとき、系が時間的に変化しない定常状態(厳密に言うと、時間的に変化するものが状態ベクトルの位相に限定される場合)、シュレーディンガー方程式は、変数分離法によって、以下のようになる:

https://ja.wikipedia.org/wiki/%E5%9B%BA%E6%9C%89%E5%80%A4

なんか量子力学においては、状態ベクトル(つまり量子ビットの状態や答えのこと)はシュレーディンガー方程式にしたがって時間的に変化するということですが、量子コンピュータのように閉じていて外部から隔絶されていると、時間的に変化しない定常状態となり、厳密には位相だけが変化するようです。

正直なんかすごい大事なことが書いてある気がします。

ここで、Hは系のハミルトニアンであり、|x〉 は状態ベクトルである。これは固有値問題そのものである。上の方程式を解くことで固有値 ε が求まる。

ということはこれを解けばいいようです。しかしここでは位相という言葉が出てこなくてどうすればいいかイメージつきませんでした。

ということで調べましたがあんまりわかりやすいの見つかりません。ていうか、位相で探してたら自分のブログがたくさん出てきてしまいました。別にSEO対策してません。仕方ないので「波動関数 位相」で調べて見ます。

結局百科事典を比較することとなりました。

https://kotobank.jp/word/%E6%B3%A2%E5%8B%95%E9%96%A2%E6%95%B0-115386

救ってくれたのは世界大百科事典でした。実は世界大百科事典は量子化学ブログのパウリの排他原理の時にも助けてくれました。すごい詳しいです。

世界大百科事典によると、、、

波動関数がψ(x,t)=exp(-iEt/ħ)φ(x)の形のものを定常状態と呼び,方程式は固有値問題。

!!定常状態の波動関数の式をゲットできました。色々調べたらこっちにも乗ってました。

https://ja.wikipedia.org/wiki/%E5%9B%BA%E6%9C%89%E7%8A%B6%E6%85%8B

多分上の式は結構見るのであってるはずです。

位相

そもそも位相を調べるのを忘れてました。人間は辞書じゃない主観によって生きている生き物なので間違えて覚えてるかもしれません。きちんと調べます。

https://ja.wikipedia.org/wiki/%E4%BD%8D%E7%9B%B8

位相(いそう、英語: phase)は、波動などの周期的な現象において、ひとつの周期中の位置を示す無次元量で、通常は角度(単位は「」または「ラジアン」)で表される。

つまり、波動などの周期的な現象において1つの位置を示す角度です。

まぁ、つまり角度を求めるのです。ここからへんは前少し勉強したことあるので知ってました。つまり位相推定アルゴリズムは、

周期性の中にあるある答えを探すアルゴリズムで、その答えは角度で示されるということです。

固有値と位相

多分あってると思いますが、この固有値が$e^{i\theta}$の形で表されるので、固有値を求める=この$\theta$を求めることに対応していると思います。とにかく固有値に対応する位相を求めれば固有値が求まります。

位相推定アルゴリズム再び

以前簡単な位相推定を紹介しました。全体構成を再度確認して見ます。位相推定の全体構成は、

1、重ね合わせパート
2、オラクルパート
3、逆量子フーリエ変換パート

です。最初に2グループに分けて上のグループを全て重ね合わせます。次に下のグループに量子状態を用意します。次にオラクルで位相キックバック(多分そういう名前?)という形で上の回路に量子状態を写します。最後に量子状態をビットに変換するために量子フーリエ変換を使います。

位相推定は結構頑張りどころみたいですが、今回はshorのアルゴリズムに関連する位相推定を頑張って考えて見たいと思います。まず最初は逆量子フーリエ変換です。

量子フーリエ変換と逆量子フーリエ変換

これはちょっと前にやりましたので覚えてます。

量子フーリエ変換を使うことによって時系列の波を周波数帯に分解できますが、量子フーリエ変換は既存の高速フーリエ変換が役に立ちます。実際には01ビットの配列から位相を含んだ量子状態に変換できると考えられるでしょう。

実際に逆から使うことによって量子状態から01のビット配列を取ることができます。この01のビットの配列は実際には位相の小数点成分を表すという素晴らしい機能があります。

また、量子回路は可逆回路として設計されており、量子フーリエ変換を組み立てると逆量子フーリエ変換は回路を逆にすることで実現できるという大変便利な仕組みがあります。その辺りも確認していきたいと思います。

$$QFT:\mid x \rangle \mapsto \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1} \omega_n^{xk}\mid k\rangle \\ \omega_n = e^{\frac{2\pi i}{N}}$$

これはフーリエ変換の一般式ですが、左側には変換される前のxというビットがあります。右側は変換されるとなんか複雑な量子状態となりました。

逆から使うと逆量子フーリエ変換ですが、

$$iQFT: \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1} \omega_n^{xk}\mid k\rangle\mapsto \mid x \rangle \\ \omega_n = e^{\frac{2\pi i}{N}}$$

こんな感じでしょうか、量子状態をルールに沿って並べてあれば、ビットに戻せます。

位相推定ではこのような状態に持っていくために、意識的に位相をこのような形に並べることで最終的に量子状態を取り出せるみたいです。

一旦まとめ

素因数分解の旅は遠そうですが、なんか色々資料が揃っているので大丈夫そうです。頑張ります。少しずつ進めていきたいと思います。つづく。

Recommended


CONTACT

info@mdrft.com

ブログトップへ Wikiへ移動

量子コンピュータ一般

量子ゲートアルゴリズム

量子アニーリング一般

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

BlueqatSDKの使い方