補遺: ハバード・ストラトノビッチ変換と大関法

量子アニーリングを実問題に使うと、しばしば「制約」をどう入れるかが問題になります。たとえば、複数の候補から1つだけ選ぶ、合計が決まった値になるように選ぶ、交通量が特定の道路に集中しないようにする、といった条件です。QUBOやIsing模型では、このような制約を二乗ペナルティとして入れることが多いです。

$$f(\mathit{q})=f_0(\mathit{q})+\frac{1}{2}\sum _k{\lambda }_k{\{F_k(\mathit{q})-C_k\}}^2$$

ここで $\mathit{q}=(q_1,\dots ,q_N)$ は0または1をとる変数です。$f_0$ は本来小さくしたい目的関数、$F_k(\mathit{q})=C_k$ は満たしたい制約、${\lambda }_k$ は制約違反を罰する強さです。${\lambda }_k$ を大きくすれば制約は守られやすくなりますが、実機で扱える係数の範囲には限りがあります。さらに $F_k$ が多くの変数の和であるとき、二乗を展開すると多くの変数どうしが互いにつながります。

たとえば

$${(\sum _i{q}_i-K)}^2=\sum _i{q}_i^2+2\sum _{i<j}{q}_i{q}_j-2K\sum _i{q}_i+K^2$$

です。0-1変数では $q_i^2=q_i$ ですが、$q_i{q}_j$ の項はすべての組 $i,j$ に出ます。つまり「合計を $K$ にしたい」という素朴な制約が、全結合の相互作用を作ります。量子アニーラやCMOSアニーリングのように結合グラフが疎な装置では、この全結合をそのまま載せることが難しくなります。

1. 二乗を線形にほどく発想

ハバード・ストラトノビッチ変換は、二乗の指数関数を、補助変数についてのガウス積分で書き直す恒等式です。もっとも単純な形は、$a>0$ に対して

$$\exp (-\frac{a}{2}{x}^2)=\int Dz\exp \left(i\sqrt{a}zx\right),Dz=\frac{dz}{\sqrt{2\pi }}\exp (-\frac{z^2}{2})$$

です。右辺には $x^2$ がありません。$x$ は補助変数 $z$ と線形にだけ結合しています。ガウス積分を実行すると、$z$ を消した結果として左辺の二乗が戻ってきます。

この式の直観は、「たくさんの変数が互いに直接つながっている相互作用」を、「共通の補助場を介して各変数が独立に感じる力」へ置き換えることです。全員が互いに握手する代わりに、全員が同じ掲示板を見る、と言ってもよいでしょう。掲示板に相当するのが補助変数です。

2. 制約ペナルティへの適用

目的関数 $f(\mathit{q})$ による分配関数を

$$Z=\sum _{\mathit{q}}\exp \{-\beta f(\mathit{q})\}$$

と書きます。$\beta$ は逆温度です。最適化だけを見たいときは、最後に $\beta \to \mathrm{\infty }$ の低温極限を考えます。

上の目的関数に含まれる二乗ペナルティへハバード・ストラトノビッチ変換を使うと、形式的には

$$Z=\sum _{\mathit{q}}\prod _k\int D{z}_k\exp [i\sum _k\sqrt{\beta {\lambda }_k}{z}_k\{F_k(\mathit{q})-C_k\}-\beta f_0(\mathit{q})]$$

となります。ここで $F_k(\mathit{q})-C_k$ は、もはや二乗されていません。ただし $i{z}_k$ が出てくるので、そのままでは実数の最適化問題として扱いにくいです。そこで積分経路を回す変数変換を行い、実数の補助変数 ${\nu }_k$ を導入します。

$$z_k\to -i\sqrt{\frac{\beta }{{\lambda }_k}}{\nu }_k$$

すると、定数因子を除いて

$$Z\propto \sum _{\mathit{q}}\prod _k\int d{\nu }_k\exp [\sum _k\frac{\beta }{2{\lambda }_k}{\nu }_k^2+\beta \sum _k{\nu }_k\{F_k(\mathit{q})-C_k\}-\beta f_0(\mathit{q})]$$

と書けます。この指数を $-\beta H(\mathit{q},\mathit{\nu })$ と見ると、有効ハミルトニアンは

$$H(\mathit{q},\mathit{\nu })=f_0(\mathit{q})-\sum _k{\nu }_k\{F_k(\mathit{q})-C_k\}-\sum _k\frac{{\nu }_k^2}{2{\lambda }_k}$$

です。重要なのは、$\mathit{q}$ に依存する制約項が $-{\nu }_k{F}_k(\mathit{q})$ という線形の形になったことです。${\nu }_k$ はラグランジュ乗数として働きます。大きな二乗ペナルティで無理に縛る代わりに、${\nu }_k$ を調整しながら制約を満たす方向へ解を動かします。

3. 固定した補助場でアニーラを使う

補助変数 $\mathit{\nu }$ を固定すると、$\mathit{q}$ について解くべき部分は

$$H_{\mathrm{e}\mathrm{f}\mathrm{f}}(\mathit{q};\mathit{\nu })=f_0(\mathit{q})-\sum _k{\nu }_k{F}_k(\mathit{q})$$

です。$C_k$ や ${\nu }_k^2/(2{\lambda }_k)$ は $\mathit{q}$ を変えても一定なので、サンプルを出すだけなら落としてよい項です。

ここで $F_k(\mathit{q})$ が

$$F_k(\mathit{q})=\sum _i{a}_{ki}{q}_i$$

のような線形和であれば、$-{\nu }_k{F}_k$ は各 $q_i$ にかかる局所磁場になります。二乗ペナルティから生じていた全結合相互作用は消え、代わりに補助変数で決まる磁場をかける問題になります。疎結合のアニーラにとっては、この違いが大きいです。全結合を無理に埋め込むのではなく、その時々の $\mathit{\nu }$ に応じた比較的扱いやすいIsing問題を解けばよいからです。

ただし、これだけでは制約が自動的に満たされるわけではありません。$\mathit{\nu }$ が小さすぎれば制約は緩く、大きすぎれば別の方向に偏ります。そこで大関法では、アニーラやサンプラから得たサンプルを使って、$\mathit{\nu }$ を反復的に更新します。

4. 期待値が制約に合うように更新する

固定した $\mathit{\nu }$ に対する分配関数を

$$Z(\mathit{\nu })=\sum _{\mathit{q}}\exp [-\beta f_0(\mathit{q})+\beta \sum _k{\nu }_k{F}_k(\mathit{q})]$$

とします。このとき対応する分布は

$$Q_{\mathit{\nu }}(\mathit{q})=\frac{1}{Z(\mathit{\nu })}\exp [-\beta f_0(\mathit{q})+\beta \sum _k{\nu }_k{F}_k(\mathit{q})]$$

です。制約 $F_k(\mathit{q})=C_k$ を完全に満たす代わりに、まずはこの分布のもとで平均値が

$$⟨F_k(\mathit{q}){⟩}_{Q_{\mathit{\nu }}}=C_k$$

になるように ${\nu }_k$ を探します。この条件は、双対側の自由エネルギーを最大化する停留条件としても得られます。

$$G(\mathit{C})=\underset{\mathit{\nu }}{max}\{\sum _k{\nu }_k{C}_k-\log Z(\mathit{\nu })\}$$

${\nu }_k$ で微分すると、勾配は $C_k-⟨F_k⟩$ になります。したがって、もっとも素朴な更新は

$${\nu }_k^{(t+1)}={\nu }_k^{(t)}+\eta [C_k-⟨F_k(\mathit{q}){⟩}_{Q_t}]$$

です。$\eta$ は更新幅です。もし現在のサンプルで $⟨F_k⟩$ が $C_k$ より大きすぎるなら、括弧の中は負になり、${\nu }_k$ は下がります。有効ハミルトニアンでは $-{\nu }_k{F}_k$ が効いているので、${\nu }_k$ が下がると大きな $F_k$ を選ぶ力が弱まります。逆に $⟨F_k⟩$ が小さすぎるなら、${\nu }_k$ は上がり、$F_k$ を増やす方向に磁場が傾きます。

大関法の1ステップは、この説明をそのまま手順にしたものです。

1. $\mathit{\nu }$ を固定します。
2. 二乗ペナルティを含まない $H_{\mathrm{e}\mathrm{f}\mathrm{f}}(\mathit{q};\mathit{\nu })$ をアニーラやサンプラで解きます。
3. 得られたサンプルから $⟨F_k⟩$ を見積もる。
4. $C_k-⟨F_k⟩$ に従って ${\nu }_k$ を更新します。
5. 制約違反と目的関数が十分小さくなるまで繰り返します。

この見方では、アニーラは元の巨大な制約付き問題を一発で解く装置ではありません。補助変数で作られた、その時点の有効Ising模型をサンプルする装置です。外側ではラグランジュ乗数がゆっくり更新され、内側ではアニーラが離散変数の候補を返します。連続変数と離散変数が交互に歩く、二重の反復法になっています。

5. 一番小さい例: K個だけ選ぶ

具体例で見ると、仕組みはかなり素直です。$N$ 個の候補からちょうど $K$ 個を選びたいとします。各候補のコストを $h_i$ とすると、二乗ペナルティを使った目的関数は

$$f(\mathit{q})=\sum _{i=1}^N{h}_i{q}_i+\frac{\lambda }{2}{(\sum _{i=1}^N{q}_i-K)}^2$$

です。普通に展開すると、$\sum _i{q}_i$ の二乗が全結合を作ります。大関法では、制約の和に対応するラグランジュ乗数 $\nu$ を導入し、固定した $\nu$ のもとで

$$H_{\mathrm{e}\mathrm{f}\mathrm{f}}(\mathit{q};\nu )=\sum _{i=1}^N(h_i-\nu )q_i$$

を解きます。これは各ビットに局所磁場がかかっただけの問題です。もしサンプルで選ばれた個数が $K$ より多ければ、$\nu$ を下げます。すると $h_i-\nu$ が大きくなり、$q_i=1$ を選びにくくなります。選ばれた個数が少なければ、$\nu$ を上げます。すると $q_i=1$ が選ばれやすくなります。この反復で、選ぶ個数を $K$ に近づけながら、コストの小さい候補を選ぶ方向へ進みます。

数分割問題も同じ形で見えます。数 $n_i$ を2つのグループに分け、和の差を小さくしたいとき、

$$f(\mathit{\sigma })=\frac{1}{2}{\left(\sum _{i=1}^N{n}_i{\sigma }_i\right)}^2,{\sigma }_i=\pm 1$$

と書けます。大関法では補助変数 $\nu$ を入れて、

$$H_{\mathrm{e}\mathrm{f}\mathrm{f}}(\mathit{\sigma };\nu )=-\nu \sum _{i=1}^N{n}_i{\sigma }_i$$

のような局所磁場の問題に落とします。二乗で全員を結合する代わりに、各スピンが同じ $\nu$ に応じた磁場を感じます。$\nu$ は、現在の分割で和がどちらに偏っているかを見て更新されます。

6. 交通流最適化での読み方

交通流最適化では、車 $i$ が候補経路 $\mu$ のどれを選ぶかを $q_{\mu ,i}$ で表します。道路 $e$ をどれだけ混ませるかは、経路と道路の対応を表す $S_{\mu ,i,e}$ を使って

$$\sum _e{\left(\sum _{\mu ,i}{S}_{\mu ,i,e}{q}_{\mu ,i}\right)}^2$$

のように書けます。この二乗は、同じ道路を使う車どうしを広く結合させます。大関法では、道路ごとの補助変数 ${\nu }_e$ を入れて

$$\sum _e{\left(\sum _{\mu ,i}{S}_{\mu ,i,e}{q}_{\mu ,i}\right)}^2⟶-\sum _e{\nu }_e\left(\sum _{\mu ,i}{S}_{\mu ,i,e}{q}_{\mu ,i}\right)$$

と読み替えます。すると各経路には

$$h_{\mu ,i}=\sum _e{\nu }_e{S}_{\mu ,i,e}$$

という局所的な重みがかかり、有効ハミルトニアンには $-\sum _{\mu ,i}{h}_{\mu ,i}{q}_{\mu ,i}$ が入ります。混みやすい道路に対応する ${\nu }_e$ が変われば、その道路を通る経路の重みも変わります。アニーラは、その時点の道路重みに従って各車の経路候補をサンプルし、外側の更新が道路ごとの混雑を見ながら ${\nu }_e$ を調整します。

この構造があるため、全結合をそのままハードウェアへ埋め込む場合よりも大きな問題を扱いやすくなります。代表的な応用には、K個選択、数分割、線形方程式からの復元、二次元構造の復元、仙台市・京都市の交通流最適化があります。いずれも、二乗ペナルティを直接載せる代わりに、補助変数を更新しながら線形化された問題を繰り返し解く、という同じ骨格を持っています。

7. 何が解けて、何が残るのか

大関法は、難しい問題を簡単な問題へ魔法のように変える方法ではありません。二乗ペナルティから来る全結合や係数レンジの問題を、補助変数の更新問題へ移す方法です。元の $f_0(\mathit{q})$ が難しければ、固定した $\mathit{\nu }$ のもとで $H_{\mathrm{e}\mathrm{f}\mathrm{f}}$ をサンプルする部分は依然として難しいです。双対自由エネルギーにも局所解があり、$\nu$ の履歴や更新幅 $\eta$ によって収束の速さや到達する解が変わります。

それでも、この置き換えには大きな意味があります。制約を大きな二乗ペナルティで押さえ込む代わりに、制約違反を観測し、そのずれに応じて外場を調整します。全結合相互作用をハードウェアに埋め込む代わりに、補助変数が作る局所場として実装します。統計力学で二体・多体相互作用を補助場にほどく発想が、量子アニーリングの実装上の制約を避けるアルゴリズムに変わっています。

この観点から見ると、大関法は「制約を罰する」方法から「制約を満たす外場を学習する」方法への移行です。アニーラは高速なサンプラとして働き、ラグランジュ乗数はサンプルの平均を見て更新されます。ハバード・ストラトノビッチ変換は、その2つをつなぐ翻訳辞書です。

参考文献: [1]。

参考文献

1. Masayuki Ohzeki, “Breaking limitation of quantum annealer in solving optimization problems under constraints,” Scientific Reports 10, 3126 (2020). 出典