KumaのLTまとめ "数値積分を1000倍高速にした話" (第18回 日曜数学会 )
こんにちは。Kumaです。
第18回の日曜数学会で発表した
「数値積分を1000倍高速にした話」
について、内容の振り返りとQ/Aで返しきれなかったものをまとめます。
Title
Agenda
なぜ計算時間がかかるか？
まとめ
reference
量子コンピュータを用いた数値積分
https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=&ved=2ahUKEwiB--zd46TqAhUCO3AKHTdZAiAQFjAAegQIAxAB&url=http%3A%2F%2Fwww.unisys.co.jp%2Ftec_info%2Ftr90%2F9003.pdf&usg=AOvVaw3zBnW66V3Ea2Crs80fExGf
Qunatum Native Dojo
Welcome to Quantum Native Dojo! — Quantum Native Dojo ドキュメント
Q&A
ニコ生コメントへの回答です
- q#使ってます？
普段はMatlab使いなので、Matlabで書いています。
ライブラリなど無いので、自作しています。行列計算ができれば出来ます。（指数的にメモリを食いますが）
最近はpythonでIBMのqiskitも使い始めました。
- どこまでの積分精度を必要としましたか？
相対誤差で1e-4程度でしょうか。これ以上追い求めても通信路の設計には不要だったので。
- モンテカルロ以外の方法は？
もし被積分関数が特定の構造を持てば、圧倒的に早い方法があります。
ガウス求積法が最もポピュラーです。
ガウス求積法は、通信では相互情報量の計算に使っています。どういうことかというと・・・
通信路で最も基本的なモデルとして、加法的白色ガウス通信路(AWGN)があります。
こいつの”尤度”はp(y|x) = exp(-(x-y)^2)の形をしています。
相互情報量の計算は、この”尤度”を含む積分になります。
さて、ガウス求積法によればexp(-x^2)を被積分関数に含むものは
高速に実行可能です。（わずか数点の直交多項式のy座標を求めれば良い）
ゆえに、相互情報量の計算はガウス求積法が適応可能でモンテカルロよりずっと早く計算できます。
（実装して確認しています。というか実務でバリバリ使っています）
もちろん、次元があまりに高いAWGNではモンテカルロのほうが早いかもしれません。
量子アルゴリズムが二次加速であるという事実は次元に依存しません。
つまり何次元でも量子アルゴリズムのほうが”早い”です。
- 準乱数法*6は試しましたか？
試していませんが、もっと高速化したいので興味は持っています。
*1:実は光ファイバー中の分極現象は、通信路容量の上限を支配します。通信路容量を上げたければ、 信号入力パワーを大きくし、雑音に負けないようにすればよいです。しかしファイバー中では、分極現象が信号入力パワーが大きいほど強く発生します。 この分極たちは余計な電磁波を放射し、信号入力である電磁波にとっては雑音にしかなりません。結局、通信路容量の上限は分極の強さだけで決まります。
*2:まぁ冷却器も広い意味で量子コンピュータの一部といえますが、しかし計算の心臓部ではありません。
*3:かなり雑な説明をしています。コンセプトは合っているが、計算式としては嘘です。Referenceを参照のこと。
*4:振幅増幅はGroverアルゴリズムの一般化といえるものです。ここではQunatum Native Dojo からGroverアルゴリズムの説明を引っ張ります
*5:振幅増幅を用いて、確率を低計算量で推定できる方法は以下のようなものです。まず確率pの小数点第1位がわかったとします。 次に小数点第2位を推定します。このとき、誤差が1/10にならないといけないわけですから、ふつうにやれば10^2倍の測定回数が必要です。 確率pの小数点第1位はわかっているので、これをもとの確率pから差し引き、これを推定する問題と考えます。この問題にたいして再び前スライドのような”都合の良い”量子状態を構成します。 そして確率増幅アルゴリズムにより|00>の確率pを10倍します。 p-> 10*p 。この状況で小数点第1位を求めます。求まった値は、元の確率pでいうところの小数点第二位です。 しかし必要な測定回数は、はじめに小数点第1位を求めたときとおなじになっています。 この手続を繰り返すことで、計算量を増加させずに任意の小数点第n桁が得られます。この方法で、必要な測定回数の総和を計算すると、なんと二次ではなく一次で済んでいます。 計算の詳細はReferenceを見て下さい。
