量子コンピュータのプログラミング

発表資料

その1

その2

量子ゲート方式の量子コンピュータの話はここではしない。

量子アニーリングマシンでのプログラミングにフォーカスする。

量子アニーリングについても説明しない。

こちらがとても良くまとまっているので参照: 量子アニーリング（西森秀稔） cache

D-waveなどから商用の量子アニーリングマシンが販売されるようになり、今後そのマシンの上で実際のニーズを解決することができるプログラマが必要になる。

量子アニーリング方式の量子コンピュータで問題を解くプロセス:

二値変数の間の関係を宣言的に記述する(イジングモデル)

この時ハミルトニアンが小さいほど、得たい特徴が大きいように設計する

量子コンピュータによってそのイジングモデルのハミルトニアンを最小化する解が高確率で得られる

プログラミングという言葉で大部分のプログラマが想像するもの、および実際に大部分のプログラマが業務として書いているプログラムは「命令列を順番に実行する計算機」によって実行される。これを想定して使われてきたCやJavaやPythonなどの言語でのプログラミングをイメージするのではかえって混乱を招く。

近いパラダイムのものをいくつか挙げる

SATソルバ

二値変数の間の関係をCNF(Conjunctive normal form, 連言標準形, 乗法標準形)の形で記述する

その関係を充足する(=満たされない論理式の個数がゼロである)解をSATソルバが発見する

「満たされない論理式の個数を最小化する」と考えてもよい

(厳密には、非充足な時に非充足な論理式の個数が最小な解を返すかどうかはソルバによる)

詳しい説明はここではしない see SAT/SMTソルバの仕組み

Alloy

SATソルバのCNF作成を容易にするための高級言語

Alloy上では「整数」「1つ以上存在する」などの高級な概念として表現されているものがCNFに変換された後SATソルバて解かれる

ChainerなどのDeep Learningフレームワークの内部構造(計算グラフ)

実数値変数の間の関係を、微分可能な関数で記述する

関係はDAG(Directed acyclic graph、有向非巡回グラフ)構造である必要がある。

最小化したい「コスト関数」をこれらの変数と学習データの組み合わせから得られる微分可能な関数で表現する

Deep Learningフレームワークが自動微分をし、コスト関数の勾配を計算する

各変数を勾配方向に更新する(厳密に言えばもっと工夫がある。see 勾配降下法の最適化アルゴリズム)

これによってコスト関数を最小化する変数の値が得られる

Prolog

宣言的なプログラミング言語と言えばよく言及される古典中の古典

変数の間の関係を一階述語論理で表現し、条件を満たす解をバックトラックによって求める

バックトラックで解くことを想定し、それを制御するための「カット命令」を使うため、ここで考えている「量子コンピュータ上でのプログラミング」とは実はあんまりフィットしない

イジングモデルとは

量子コンピュータのプログラムを書くことはイジングモデルを作ることだと分かった

それは何か？どうやって作るのか？

イジングモデル

$ \mathcal{H} = -\sum_{(ij)\in E} J_{ij} \sigma_i^z \sigma_j^z - \sum_{i\in V} h_i \sigma_i^z

ここで $ \sigma_i^z は二値の変数

肩のzはz軸方向のスピンという意味で、この先の議論でz以外のものは出てこないので無視していい

グラフの頂点と1対1対応している

重要ではないのでこう書いてもよい $ \mathcal{H} = -\sum_{(ij)\in E} J_{ij} x_i x_j - \sum_{i\in V} h_i x_i

Vがグラフの頂点、Eはグラフの辺

各頂点ごとの重みhと各辺ごとの重みJを掛けて足し合わせた形

Hはハミルトニアン

イジングモデルのスピンの状態に対応したエネルギー

このエネルギーが小さい解を量子アニーリングマシンは高い確率で返す

物理的なビー玉が位置エネルギーの低い「低い所」に転がるのと同じ構図

ハミルトニアンが最適化問題におけるコスト関数に相当するように設計して、量子アニーリングマシンに投げれば解が得られる

2つ目の項を「磁場」と呼ぶけどこれはプログラムをする上で不要な背景知識。

抽象化されて元々何のモデルだったか関係なくなっているが、元々イジングモデルは強磁性体の模型であって、変数が-1と+1の値を取るのはN極とS極って意味で、特定の頂点にN極を近づければS極がこっちを向くような圧力を掛けることになるよね、そういうこと。

強磁性体の模型としては頂点をグリッド上に並べて隣接する頂点との間に相互作用(=辺)がある、という形だったが、上記数式の定義でグリッドではなくグラフになってることからわかるようにそこは捨象済み。

巡回セールスマン問題のイジングモデルでの定式化で、時間と空間の二次元グリッドを描くため、二次元イジングモデルを知っていて量子コンピュータのイジングモデルを知らない人(過去の僕)は相互関係のエッジがどう貼られているかを誤解して混乱する。

ちなみに2次元のボルツマンマシンは画像を記憶して想起することができる。これは2次元のイジングモデルとほぼ同じもの。全結合のボルツマンマシンは指数オーダーの学習時間がかかるため二部グラフに制限したRBM(Restricted Boltzmann machine) がDeep Learningの文脈で良くもちいられる。

なお、ニューラルネットの学習は一部の頂点の値が教師データとして与えられて辺の重みが更新されるのに対し、量子アニーリングは辺の重みを与えて頂点の値を求めるものであることに注意。

これくらいの知識があれば巡回セールスマン問題のイジングモデル化ができる？

巡回セールスマン問題のコツ：「あるステップtに都市iにいるかどうか」の二値変数として扱う

ある都市から次の時刻の別の都市への辺に距離の重みを乗せる

それだけだと「移動しない」という自明な解に落ちるので「各都市に1回だけ存在する」という制約を入れたい

一般論として「N個の頂点 $ \sigma_i (0 \le i < N) のいずれか1つのみが1、残りが0」という制約を表現したい

この表現は「N個全部足したら1」($ \sum_i \sigma_i = 1)と書き換えられる

さらに$ (1 - \sum_i \sigma_i) = 0 となる

以前はここで「頂点の値の足し算とかどうやるのだ？」と思っていた

両辺を二乗してから展開する

$ (1 - \sum_i \sigma_i)^2 = 1 - 2 \sum_i \sigma_i + (\sum_i \sigma_i) ^2 = 1 - 2 \sum_i \sigma_i + \sum_i \sum_j \sigma_i\sigma_j

展開してしまえば普通のハミルトニアンになるというわけ。