ロサンゼルスに引っ越したので久しぶりのブログを書いてみる

何年ぶりのブログかわからないが、久しぶりにブログを書いてみることにする。 理由は大きく2つある。 1つ目は2021年1月にロサンゼルスに引っ越し、ライフイベント的に記録を残しておこうと思ったからである。 2つ目はUCLAに所属してからの最初の論文をarXivにポストしたので、その紹介をしようということである。

1つ目について。

2020年4月からUCLAのDepartment of Electrical and Computer Engineeringで博士研究員として働いてる。 採用に至ったきっかけはTwitterだった。 Twitterでは海外の研究者や海外の研究関連のアカウントを多くフォローしてるのだが、なんとなくTwitterを眺めていたらUCLAで自分の研究分野に近そうな公募を見つけ、すぐに問い合わせのメールを送った。 早速CVを送ってくれという返信がきたので、CVを慌ててワードで適当に作って送った。 そうすると”じゃ来週zoomで面接ね!”と言われ、かなり戸惑った。 面接の内容は2つ。 1つは自分の研究を紹介するというもの。 もう1つは論文を渡され、それを説明するというもの。 zoomの面接ではUCLAの教授1人、准教授1人、私の3人で、2時間半程度だった。 結果は教授が即決で採用という感じだった。 一様妻に相談をしたが、”どうせ行くんでしょ?”と言われたように記憶している。 この時期、他にも複数応募していたが、その全てが日本国内のものだったし、ずっとアメリカに行きたいと思っていた。 妻が言うように実際には相談というよりは事後承諾という感じで、既に採用を受諾することを決めていた。

そんなこんなで今に至っている。 といっても私にとって大きなことがあった。 同時期に採用された中国人がおり、たまに連絡を取っていた。 しばらくの間、私はVISAが出なかったため日本からリモートワークをしていた。 久しぶりにその中国人にメッセージを送ったのだが、返信がなかった。 ボスに聞いたら、”彼は中国に帰った”と言われた。 半年ほどでクビになっていたのである。 これがアメリカか?と思った。 その時今のプロジェクトをモノにしないと私もクビになるなと思った。 結果的に今年2月には論文をarXivにポストすることができたので少し安心している。 その後、元々2年だった契約が3年に延長されることになった。 ボスに”最初の2年で結果を出して、3年目でポジションを見つけろ。見つかるまでサポートする”と言ってもらえた。 ボスにある程度評価されているようで嬉しい気持ちになった。

将来は北米か日本の大学でのポストを希望しているがどうなるかわからない。 というより、実際には私の実力からすると厳しいだろうということはわかっている。 当然IT系の会社に行く可能性もあるだろう。 とりあえず今の気持ちは”人事を尽くして天命を待つ”と言ったところか。

2つ目について

最近論文をarXivにあげた。 タイトルはAnsatz-independent Variational Quantum Classiferというものである。 リンクはここである。 興味がある方は是非一読してただけると嬉しい。

我々が日々使っているパソコンやスマホ(以下、古典計算機)は0か1を表すbitで情報を表し、演算を行う。 古典計算機が安定的に動くのは、誤り訂正などの技術によってbitを安定的に維持し、操作することができるからである。 さらに言えば、そのbitを一度にたくさん扱うことができるからである。 しかし、”完全”な量子計算機を作ることは難しい。 量子計算機ではqubitと呼ばれる単位が最小の単位になり、超伝導リングやフォトンを使ってそれを実現しようとしている。 どの意味で難しいかというと、qubitを安定的に維持、操作することが難しいのである。 さらにその数を増やすことが難しい。

近年、GoogleIBMの研究チームが量子計算機の開発を目指し努力している。 彼らはまず多少ノイズがある中規模の量子計算機(以下NISQ。NISQはnoisy intermediate-scale quantum deviceからきている)を作ろうとしている。 中規模とは大体50qubitかそれ以上というように思う。 しかしNISQをどう扱うかといのはまた難しい問題である。 というのも完全な量子計算機に対しては様々な理論的な研究が既に存在しているのだが、NISQの有効性やNISQをどう扱えばよいかは難しい問題なのである。 そこで近年NISQで動かせるアルゴリズムが様々提案されている。 その中に量子機械学習アルゴリズムというものがあり、注目を集めている。 今世の中で流行っている量子計算と機械学習を組み合わせたものなので、注目を集めるのは必然かもしれない。 しかし、量子機械学習アルゴリズムが提案され注目を集めているのはいいのだが、どの程度有効かということもまた謎であった。 特に量子機械学習アルゴリズムでは情報をどのようにqubitにエンコードするか?、どのような量子回路を採用すればいいか?という問題があり、その有効性を評価することが難しかった。

我々の研究では量子回路によらない形で量子機械学習アルゴリズムの性能を評価する手法を提案した。 言い換えると、エンコードを決めたとき、量子機械学習アルゴリズムが発揮する最大の性能を評価することができるアルゴリズムである。 研究において、”最大の性能を評価すること”は極めて重要なことである。 なぜならば、達成可能な最大値がわかっているということはエンジニアリング的な目標になるからである。 物理の歴史を振り返ると熱機関のエネルギー効率を計算したことが偉大な結果であったことを思い出せばわかっていただけると思う。

ここまで読んでいただいた方には感謝します。 そんな方、いないと思いますが・・・。

とりあえず今日のところはこの辺で終わりにします。 次はいつブログを書くだろうか・・・。

変分ベイズ法の量子力学的拡張について

2017年が終わるということで、久しぶりにブログを書く。

最近の自身の結果について語ろうと思う。現在査読中ではあるが、原稿は以下にある。

https://arxiv.org/abs/1712.04709

端的にいうと、「変分ベイズ法を量子力学的に拡張した」というものである。

上の説明を受けると、まず「変分ベイズ法」とはなんだろうとおもう方がいるだろうとおもう。詳しくは説明しないが、今流行りの機械学習の学習アルゴリズムの一つである。より詳しく説明すると、パラメータを含むモデルを仮定し、それと生成モデルで定義されるKullback Leibler divergenceを最小化することで、仮定したモデルのパラメータの分布を推定するアルゴリズムである。さらに、平均場近似という仮定をおき、繰り返し計算によって推定を行う。これは、平均場近似なしでは一般に計算不可能だからである。数式なしにこれ以上説明することは不可能なように思えるので、しっかりと理解したい人は、上記の論文の説明を読むか、専門的な本を読んで欲しい。

変分ベイズ法は広く利用されており、有効なアルゴリズムである。一方で、初期値に依存して最終的な解が異なってしまう。要は、局所最適解によく落ちてしまう。これは平均場近似の一般的な性質でもある。

我々は、この問題を量子力学的にアルゴリズムを拡張することで解決することを目指した。完全に解決したとは言わないが、かなり良いアルゴリズムが提案できていると考えている。

しかし、数学的なメカニズムについてはほぼわかっておらず、現在研究を進めている。興味があれば、一読をお願いします。

本研究と近いタイトルの先行研究がある。しかし、数学的に間違っている。しかも、なぜ取れたのか、理解不能だが、それで博士号が出ている・・・。この間違いについては、本論文では理論を綺麗に書くために意図的に言及しなかった。論文の続報で言及する可能性が高い。ただし、共著者との議論によっては永久にお蔵入りするだろう。あるいはレフェリーに言われれば、Appendixに追加するかもしれない。何れにしても、かなり長いTeXノートは既にあるので、聞かれればいつでも答えることはできるように準備している。

量子アニーリング 2

 ずいぶん前に、量子アニーリングについてのエントリを書いた。ほとんど誰も読んでいないとは思うが、自身で読み返してみると、説明としてどうなのか?と思う部分がある。そこで、「量子アニーリング2」として、エントリを書いてみようと思う。

 

 まず、歴史的なことである。量子アニーリングが、初めて最適化アルゴリズムとして提案されたのは、Apploni et al. [1]のように思う。その後、Finnila et al. [2]やKadowaki, Nishimori [3]に続くようである。これらの論文で提案されているアルゴリズムのコンセプトは同等であると思うが、交換関係として、位置・運動量の交換関係 を使うか、SU(2)の交換関係を使うかの違いはある。

 

 続いて、量子アニーリングの実装についてである。以前の記事では、鈴木トロッター展開をする計算方法に触れた。例えば、[4]などにかかれている。これは、スピン系の量子アニーリングモンテカルロ的に実装する方法であり、スピンの数に対してスケールしやすく、汎用性のある実装方法である。しかし、量子アニーリングの実装は、この限りではない。実際、[3]では、シュレディンガー方程式を直接解く。モンテカルロを用いないことは1つの利点だと思うが、スピンの数に対して、スケールしないという問題がある。上記は何れも、離散変数の最適化、組み合わせ最適化が念頭にあることを付け加える。

 

 連続変数の最適化は、ファインマン経路積分を適用するなどすれば計算可能であるが、深くは触れない。(後で加筆するかもしれない。)

 

 量子アニーリングダイナミクスについては、日本語の[5]の解説記事が勉強になった。とてもおもしろいので、興味がある人は読んでみてはいかかでしょうか?

 

[1] B. Apolloni, C. Carvalho, and D. de Falco, “Quantum
stochastic optimization,” Stochastic Processes and their Applications,
vol. 33, no. 2, pp. 233–244, 1989. [Online]. Available:

http://www.sciencedirect.com/science/article/pii/0304414989900409

[2] A. Finnila, M. Gomez, C. Sebenik, C. Stenson, and
J. Doll, “Quantum annealing: A new method for minimizing
multidimensional functions,” Chemical Physics Letters, vol.
219, no. 56, pp. 343–348, 1994. [Online]. Available:

http://www.sciencedirect.com/science/article/pii/0009261494001170

[3] T. Kadowaki and H. Nishimori, “Quantum annealing in the transverse
ising model,” Phys. Rev. E, vol. 58, pp. 5355–5363, Nov 1998.
[Online]. Available: http://journals.aps.org/pre/abstract/10.1103/PhysRevE.58.5355

[4] R. Martonak, G. E. Santoro, and E. Tosatti, “Quantum annealing by
the path-integral monte carlo method: The two-dimensional random
ising model,” Phys. Rev. B, vol. 66, p. 094203, Sep 2002. [Online].
Available: http://journals.aps.org/prb/abstract/10.1103/PhysRevB.66.094203

[5] 鈴木正, "組み合わせ最適化問題と量子アニーリング : 量子断熱発展の理論と性能評価",

https://www.google.co.jp/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&cad=rja&uact=8&ved=0ahUKEwjwuc_U1-fLAhXDxqYKHTf3DIcQFggjMAE&url=http%3A%2F%2Frepository.kulib.kyoto-u.ac.jp%2Fdspace%2Fbitstream%2F2433%2F142655%2F1%2FKJ00004982313.pdf&usg=AFQjCNEu7IqJFIHfOpZCg2bnuIF2vPojbQ&sig2=58UD1Krug27wSbkcEWp4FQ

量子アニーリング

 組み合わせ最適化問題を数値的に解く手法として、シミュレーテッド・アニーリング(SA)と呼ばれる手法が古くから知られており、広く使われている。(量子アニーリングとの比較で古典アニーリング(CA)と呼ばれることもある。)

 一方で量子アニーリングと呼ばれる手法がイジング模型という統計力学の模型を解く手法として、1998年にKadowaki、Nishimori[1]によって提案された。この手法では、古典的模型である”イジング模型”を量子的模型である”横磁場イジング模型”に変更することでエネルギー最適化問題を解く。SAとQAの大きな違いの一つに評価関数の局所解から局所解への遷移確率が異なるということがあげられる[2]。これについては後で簡単に触れるが、特に評価関数が複雑な場合はQAは有効な手法になり得る。さらに、QAの適用範囲は広い。例えば、有限次元のグラフとして定義される最適化問題の評価関数はイジング模型のハミルトニアンのようにみなせるので、QAは適用可能である。

 

 上記の理由から多くの適用先があると考え、QAに関する論文[1, 2, 3, 4, 5, 6, 7, 8, 11, 12]を10本程度読んだ。(ただ何を読んだか忘れてしまったので、随時更新する。)論文以外にネットですぐ見つかるものとして解説記事[9]を読んだ。

 

 QAの概要に入る前に簡単にSAの概要を述べる。SAで解くイジング模型は以下のように定義される。

H=-{\sum}_{ij} J_{ij} {\sigma}^z_i {\sigma}^z_j

一般にはHハミルトニアンと呼ばれるエネルギー演算子である。ただ古典的模型では演算子である必要はないので、物理量としてのエネルギーである。最適化の文脈では評価関数である。定義を見てみると、右辺の初めに{\sum}_{ij}とあるが、これは隣接したサイトに関しての合計である。{\sigma}^z_iはサイトiにおけるz軸方向のスピンである。本来スピンはパウリ行列で表現されるが、古典的なイジング模型を考える場合、{\sigma}^z_i=\pm 1で表現できる。

 SAは上記のイジング模型におけるエネルギーを下げるための乱数アルゴリズムである。初期値として各サイトのスピンをランダムに設定する。1回のステップで各サイトのスピンを反転させ、その前後でエネルギーを計算し、ある確率でスピンの反転を受容あるいは拒絶する。スピン反転させる前のエネルギーをE_1とし、スピン反転後のエネルギーをE_2とすると、そのステップでのスピン反転を受容する確率を

p=\frac{1}{1+\exp(-\frac{E_2-E_1}{k_b T})}

と定義する。ここでk_bはボルツマン定数、Tは温度を表す。初め温度Tを高温に設定し、スピン反転を繰り返すたびに温度を下げていく。あらかじめ温度やエネルギーのばらつきに閾値を設けて、計算を終了する。これはざっくりと説明すると以下の2点を行っている。

(1)初めは温度を高温に設定し、エネルギーが上昇する(評価関数が悪くなる)スピン反転を受容する確率を高くすることで、局所解に陥りにくくする。

(2)徐々に低温にすることで局所解を探すという戦略に切り替える。

 このアルゴリズムでは局所解から局所解へ飛び移る確率が

p \approx \exp(-\frac{\Delta }{k_b T})

と計算される[2, 12]。ここで\Delta とはポテンシャル障壁の高さである。

 

 本題のQAの概要である。QAは古典的イジング模型(z軸スピンのみ)にx軸方向(y軸方向でもよい)に磁場をかけ、アニーリングの過程でその磁場を徐々に弱くし、最終的には0にする。ハミルトニアンが以下のように変更し、\Gammaを最終的に0にする。

H=-{\sum}_{ij} J_{ij} {\sigma}^z_i {\sigma}^z_j+\Gamma {\sum}_i {\sigma}^x_i

{\sigma}^{x}_iを含む項が付け加わっていることが分かる。{\sigma}^{x}_iはサイトiにおけるx軸方向のスピンであり、\Gammaは地場の強さである。この時点ではじめの古典的模型は量子的模型になっている。先に触れたが、物理の用語でいうところの”横磁場イジング模型”である。スピン{\sigma}^{z(x)}_iは以下のようにパウリ行列で表現される。

{\sigma}^z_i = \begin{pmatrix} 1 \ \ \ \ \ \ 0 \\ 0 \ \ -1 \end{pmatrix}, \ \ {\sigma}^x_i = \begin{pmatrix} 0 \ \ 1 \\ 1 \ \ 0 \end{pmatrix}

このときイジング模型のときのように{\sigma}^{z(x)}_i=\pm 1とは表現できない。{\sigma}^{z(x)}_iが交換しないことが量子的模型として本質的である。

 しかしこのような模型をどのように解けばいいのかという問題が生じる。それに対する解が以下である。量子的模型は鈴木トロッター展開を行うことで古典的模型にマップすることができる。重要なことはトロッター展開によって最初に定義された模型は1次元高い模型になることである。今回の場合、3次元の横磁場イジング模型(量子的模型)が4次元のイジング模型(古典的模型)にマップされる。実際にトロッター展開を行うと、新しい次元(トロッター次元、トロッター方向などと言う)はもともとの模型を並べて、同じスピン間に

J=-\frac{PT}{2}\log \tanh \frac{\Gamma}{PT}

というカップリングを導入することで定義される。ここでPはトロッター方向のレプリカの数、Tはシステムの温度である。計算は参考文献[10]に詳細が示されている。わかりやすい論文なので参照していただきたい。結果として先の”横磁場イジング模型”は

H=-{\sum}_{ij} J'_{ij} {\sigma}^z_i {\sigma}^z_j

のように表現することができる。J'は上記の新しい次元を考慮してJを取り直している。後はこれをSAと同じ要領で解くだけである。

 実際には、以下のように\tautを導入してパラメータを取り直す。

H=-\frac{t}{\tau}{\sum}_{ij} J_{ij} {\sigma}^z_i {\sigma}^z_j+(1-\frac{t}{\tau})\Gamma {\sum}_i {\sigma}^x_i

\tauがアニーリングパラメータで、0からスタートして、tで終了する。単純に温度は初めから低温に固定する。そのため断熱的であると表現される。当然であるが、温度もアニーリングパラメータとして問題ない。この場合はアニーリングパラメータが複数になるので、アルゴリズムに修正が必要である。

 このアルゴリズムでは局所解から局所解へ飛び移る確率が

p \approx \exp(-\frac{\sqrt{\Delta}w }{k_b T})

と計算される[2, 12]。ここで\Delta とはポテンシャル障壁の高さであり、wはポテンシャル障壁の壁の厚さである。この手法は相対的にポテンシャル障壁の高さが高く、その壁の厚さが薄いときに局所解に止まりにくいということであり、評価関数が複雑であるときに局所解に止まりにくいということを意味している。これはまさにトンネル効果であり、モデルを量子化したことによる恩恵である。この点は非常に重要であり、QAの優位性を述べている。

 

 ここで一点SAとQAに共通する重要なことを付け加える。SAとQAにおいて最適化されるのは実際にはハミルトニアンあるいはエネルギーではない。自由エネルギーである。自由エネルギーは以下のように定義される。

F=H-TS

ここでSエントロピーである。これは両者に通じて温度を下げなければいけないもう一つの理由を示している。温度が高いとエントロピーが大きい状態が計算結果として得られてしまうが、温度を下げればエネルギーと自由エネルギーは近づくからである。

 

 次に数値計算についてである。厳密にはトロッター方向に無限にレプリカを並べなければいけないが、数値計算上は不可能である。実際、数値計算上はある程度の細かさで十分である。

 論文を読むとレプリカの数は20あるいは30程度とるのが良いとある。また、PTはコンスタントになるように計算することが多いようである(これは必然性はない)。私はレプリカの数を10程度としてSAで実装した。それなりの結果が得られたようである。一つのアイデアとして遺伝的アルゴリズム(GA)など他の手法を組み合わせるのは面白いのではないかと考える。

 当然のことであるが、レプリカの数だけ一回のモンテカルロステップでQAのほうが時間がかかる。それを考慮してモンテカルロステップを減らしてもQAの方がSAよりいい結果が出ることがあり、実時間で短くできるはずということである。ただ、論文ではモンテカルロステップについて述べているものが多く、実時間で比較しないで意味があるのだろうかという疑問を感じた。

 

 SAとQAの優劣についてである。問題によっては良くなる場合もあるし、悪くなる場合もあると論文には書かれている。ただ残念ながら私はどのようなケースで良くなり、悪くなるかということに関して知見はない。

 

 このアルゴリズムで重要な概念として、鈴木トロッター展開、経路積分展開、分配関数があり、量子力学統計力学の知識が多く盛り込まれている。これについては物理の参考書あるいは論文を参照していただきたい。

 

 QAと多スタート局所探索法など他の最適化手法との比較は面白いと感じている。古典的手法と量子的手法の比較ができると考えるからである。実際、鈴木トロッター展開をした後は古典的手法にマップされているので、他の手法と簡単に比較できる。 

 最後に簡単なコードを書いてみた。下記にサンプルコードをあげた。稚拙なコードであるがご了承願いたい。コードは書き直す予定である。

SAのコード:https://github.com/hmiyahara512/simulated-annealing_for_3d-ising-model

QAのコード:https://github.com/hmiyahara512/quantum-annealing_for_3d-ising-model

 

[1] T. Kadowaki and H. Nishimori, "Quantum annealing in the transverse Ising model"

Phys. Rev. E 58, 5355 (1998)

[2] A. Das, B.K. Chakrabarti, and R.B. Stinchcombe, "Quantum annealing in a kinetically constrained system", Phys. Rev. E 72 art. 026701 (2005)

[3] G. E. Santoro, R. Martonak, E. Tosatti, and R. Car, "Theory of Quantum Annealing of an Ising Spin Glass" DOI: 10.1126/science.1068774

[4] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, "Quantum Adiabatic Evolution Algorithms versus Simulated Annealing" http://arxiv.org/abs/quant-ph/0201031

[5] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, Joshua Lapan, Andrew Lundgren, Daniel Preda, "A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem" DOI: 10.1126/science.1057726

[6] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, "A Numerical Study of the Performance of a Quantum Adiabatic Evolution Algorithm for Satisfiability" http://arxiv.org/abs/quant-ph/0007071

[7] Roman Martonak (1), Giuseppe E. Santoro (2,3), Erio Tosatti (2,3) ((1) Dept. of Chemistry and Applied Biosciences, ETH Zuerich, Lugano, CH, (2) SISSA and INFM-Democritos, Trieste, Italy, (3) ICTP, Trieste, Italy) "Quantum annealing of the Traveling Salesman Problem" DOI: 10.1103/PhysRevE.70.057701

[8] S. Morita and H. Nishimori, "Mathematical foundation of quantum annealing", J.Math. Phys. 49, 125210 (2008)

[9] http://www-adsys.sys.i.kyoto-u.ac.jp/mohzeki/QA.pdf

[10] M. Suzuki, "Relationship between d-Dimensional Quantal Spin Systems and (d+1)-Dimensional Ising System : Equivalence, Critical Exponents and Systematic Approximants of the Partition Function and Spin Correlations" http://ci.nii.ac.jp/lognavi?name=nels&lang=en&type=pdf&id=ART0001548127

[11] Arnab Das and Bikas K. Chakrabarti
"Quantum annealing and analog quantum computation" http://journals.aps.org/rmp/abstract/10.1103/RevModPhys.80.1061

[12] V.N. Smelyanskiy, E.G. Rieffel, S.I. Knysh, C.P. Williams, M.W. Johnson, M.C. Thom, and K.L.P.W. G. Macready (2012), “A Near-Term Quantum Computing Approach for Hard Computational Problems in Space Exploration”

 

*解釈あるいはコードに間違いがあれば、ご一報をお願いします。

*8月12日に内容と出典の誤りを修正しました。随時修正します。一発目から長いエントリを書いたことを後悔してます。

モンテカルロステップやエネルギーの計算に不適切な部分があります。時間があれば修正するかもしれません。(許容範囲かなと思います。)

ブログ始めました。

ブログを始めようと思います。

 

本ブログの方針は以下の2点です。

1)数学、物理、プログラム、OSSなど個人的に面白いと思うものについて書こうと思います。日常や政治・経済についてのブログは書くつもりはありません。

2)まず書いてみてアップしようと思います。不適切な文章や内容の誤り、コードの誤りは随時修正します。

 

よろしくお願いします。