補遺: BOCSとFMによるブラックボックス最適化

材料の構造を少し変えたとき、熱の逃げ方はどう変わるでしょうか。基板の固定穴を変えたとき、振動の固有振動数はどこへ動くでしょうか。どちらも、候補を与えればシミュレーションで評価できます。しかし、その評価値を設計変数の簡単な式として書けるとは限りません。しかも、候補一つの評価に時間がかかります。

量子アニーリング応用事例とQUBO設計では、こうした問題でもQUBOが使われることを紹介しました。本補遺では、その間に入る「学習」を詳しく見ます。観測した少数の候補から二次式の代理モデルを作り、その二次式をSAやQAで解いて、次に評価する候補を決めます。BOCSとFMは、この学習の仕方が異なる二つの入口です。

BOCSは Bayesian Optimization of Combinatorial Structures、FMは Factorization Machine の略です。前者はベイズ推論を組み込んだ最適化の枠組み、後者は予測モデルの形式です。FMをアニーラと組み合わせて逐次最適化する方法はFMQA、FMAなどと呼ばれます。FMQAのQAをquantum annealingと読む原初の用法に加え、古典装置も含めてquadratic-optimization annealingと読む用法があります。以下では実際のソルバを明記します。原著BOCS [1]、FMQA原著 [2]、FMQA総説 [3]が出発点です。

1. 高価な評価の外側に、安価な探索を置く

まず最小化問題に統一し、設計を $\mathit{x}\in \{0,1{\}}^n$、本当に小さくしたい値を $f(\mathit{x})$ とします。最大化したい性能が $g$ なら $f=-g$ と置きます。測定誤差があるとき、得られるのは

$$y^{(a)}=f({\mathit{x}}^{(a)})+{ϵ}^{(a)},{\mathcal{D}}_t=\{({\mathit{x}}^{(a)},y^{(a)}){\}}_{a=1}^t$$

というデータです。「ブラックボックス」とは、値を問い合わせられる一方、探索に使える解析式や微分が直接は得られないという意味です。ベンチマークでは既知の関数を意図的に隠して使うこともあります。

処理の流れは次のようになります。データからモデルへ、モデルから候補へ、候補から実験へ、そして再びデータへ戻る輪を作ります。

1. 実行可能な候補をいくつか選び、実験やシミュレーションで評価します。
2. データ ${\mathcal{D}}_t$ から代理モデルを学習します。
3. 「次に試す価値」を表す獲得関数を作ります。
4. SA・QAなどで獲得関数を最小化し、新しい候補を出します。
5. その候補を本来の実験・シミュレーションで評価し、データを追加します。
6. 評価予算まで繰り返し、実際に評価した候補の中から最良のものを返します。

第4段階で代理モデルを何万回評価しても、第5段階の高価な評価は一候補分です。この二重構造が本手法の狙いです。アニーラが出した低エネルギー状態は、学習した予測の上で有望な候補です。その性能を確定するのは、その後の本来の評価です。

たとえば、一回の流体計算に一時間かかり、総予算が100回なら、設計空間を網羅するのは困難です。最初に20候補を調べ、残り80回を逐次的に配分する、という考え方になります。この20と80は説明用の数値で、一般に推奨される固定値ではありません。

2. なぜ二次式を学習するのか

二値変数では $x_i^2=x_i$ です。二次の代理モデルは

$$\hat{f}(\mathit{x})=b+\sum _i{a}_i{x}_i+\sum _{i<j}{b}_{ij}{x}_i{x}_j$$

と書けます。$a_i$ は選択肢 $i$ 単独の効果、$b_{ij}$ は二つを同時に選んだときに加わる効果です。負の $b_{ij}$ は、最小化において二つの同時選択を有利にします。ここでの係数は物理法則から与えた定数ではなく、観測から推定した量です。

特徴ベクトルを

$$\mathit{\varphi }(\mathit{x})=(1,x_1,\dots ,x_n,x_1{x}_2,\dots ,x_{n-1}{x}_n)$$

と置くと、モデルは $\hat{f}={\mathit{\varphi }}^{\mathsf{T}}\mathit{\theta }$ です。入力に関して二次でも、係数 $\mathit{\theta }$ に関しては線形です。通常の回帰の道具を使え、学習後の候補探索はQUBOになります。

ただし係数は $1+n+n(n-1)/2$ 個あります。$n=100$ なら5,051個で、100件の観測から自由に決めることはできません。ここで「少数の相互作用が重要」と仮定するBOCSと、「相互作用が少数の潜在因子を共有する」と仮定するFMが登場します。

任意の二値関数が二次式で厳密に表されるわけではありません。三体以上の相互作用や不連続な応答が強い場合、二次代理モデルには表現誤差が残ります。QUBOへの変換が厳密なのは、ここで選んだ二次モデルについてです。

3. BOCS: 係数を一つに決めず、不確かさを持たせる

3.1 二次回帰を確率モデルとして書く

説明のため、独立な正規観測雑音を仮定します。行列 $\mathrm{\Phi }$ の第 $a$ 行を $\mathit{\varphi }({\mathit{x}}^{(a)}{)}^{\mathsf{T}}$ とすると、

$$\mathit{y}=\mathrm{\Phi }\mathit{\theta }+\mathit{ϵ},\mathit{ϵ}\sim \mathcal{N}(0,{\sigma }^{2}I)$$

です。ベイズ推論では、観測前の係数の分布である事前分布と、観測を説明する尤度を掛け合わせて、観測後の分布を求めます。

$$p(\mathit{\theta },{\sigma }^2\mid {\mathcal{D}}_t)\propto p(\mathit{y}\mid \mathrm{\Phi },\mathit{\theta },{\sigma }^2)p(\mathit{\theta },{\sigma }^2).$$

元のBOCSではhorseshoe事前分布によって係数を縮小します。典型的な階層表現は、切片を別扱いにして

$${\theta }_j\mid {\lambda }_j,\tau ,{\sigma }^2\sim \mathcal{N}(0,{\sigma }^2{\tau }^2{\lambda }_j^2),{\lambda }_j,\tau \sim C^{+}(0,1)$$

です。$C^{+}$ は半Cauchy分布、$\tau$ は全体の縮小の強さ、${\lambda }_j$ は各係数の縮小を調整します。多くの係数をゼロの近くに集めながら、データに裏づけられた大きな係数は残します。厳密なゼロを自動的に作るという意味ではありません。雑音分散や切片の事前分布、標準化も含めて推論の設定になります。[1]

3.2 事後分布から何を取り出すのか

階層パラメータを固定し、$\mathit{\theta }\sim \mathcal{N}(0,{\sigma }^2\mathrm{\Lambda })$ とした部分問題を考えると、平方完成から

$$\begin{array}{rl}V& =({\mathrm{\Phi }}^{\mathsf{T}}\mathrm{\Phi }+{\mathrm{\Lambda }}^{-1}{)}^{-1},\\ \mathit{m}& =V{\mathrm{\Phi }}^{\mathsf{T}}\mathit{y},\\ \mathit{\theta }\mid \mathit{y},\mathrm{\Lambda },{\sigma }^2& \sim \mathcal{N}(\mathit{m},{\sigma }^{2}V)\end{array}$$

を得ます。実装では逆行列を直接作らず、線形方程式や適切なサンプラーを使います。horseshoeの場合は $\mathrm{\Lambda }$ 自体も更新するので、この一回の正規分布の計算だけでBOCSの推論が完結するわけではありません。

平均 $\mathit{m}$ だけを使えば、現時点で最もありそうな二次式を解くことになります。BOCSで重要なのは、係数ベクトルを事後分布から一つ引き、その二次式を解く Thompson sampling です。

$${\tilde{\mathit{\theta }}}_t\sim p(\mathit{\theta }\mid {\mathcal{D}}_t),{\mathit{x}}_{t+1}\approx \underset{\mathit{x}\in \mathcal{X}}{\mathrm{argmin}}\{\mathit{\varphi }(\mathit{x}{)}^{\mathsf{T}}{\tilde{\mathit{\theta }}}_t+\lambda \sum _i{x}_i\}.$$

$\mathcal{X}$ は実行可能集合です。最後の項は選択数のコストなどがある場合に加え、不要なら $\lambda =0$ とします。係数の縮小に使うパラメータと、この設計上のコストは役割が違います。

データが少なく係数に不確かさが残る場所では、抽出するモデルによって有望な候補が変わります。そこから探索が生まれます。すでに良いと分かっている場所を調べる活用と、不確かな場所を調べる探索を、係数分布を通じて両立させようとする仕組みです。

係数は結合したベクトルとして抽出します。各係数の周辺分布から独立に乱数を作ると、事後分布の相関が失われ、元のThompson samplingとは別の方法になります。また、近似的な事後推論やQUBO探索を使うので、理想的なThompson samplingの性質を無条件に引き継ぐわけではありません。

3.3 不確かさはQUBOを壊さないのか

事後平均から予測標準偏差を引く獲得関数 $\mu (\mathit{x})-\kappa s(\mathit{x})$ も考えられます。しかし、標準偏差には共分散と平方根が入り、一般には二次式になりません。Thompson samplingでは「一つの二次式を抽出してから解く」ため、候補探索のQUBO構造を保てます。

BOCSは高次モデルも扱う枠組みですが、本補遺は二次BOCSに限ります。高次相互作用を導入すれば、SAで直接扱うか、補助変数で二次化するなどの追加設計が必要です。

4. FM: 相互作用を潜在ベクトルの内積で表す

4.1 二つの選択肢が共有する性質を学ぶ

FMでは、各変数 $x_i$ に $k$ 次元のベクトル ${\mathit{v}}_i$ を割り当て、二変数の相互作用を内積で表します。

$${\hat{f}}_{\mathrm{F}\mathrm{M}}(\mathit{x})=w_0+\sum _i{w}_i{x}_i+\sum _{i<j}⟨{\mathit{v}}_i,{\mathit{v}}_j⟩x_i{x}_j,⟨{\mathit{v}}_i,{\mathit{v}}_j⟩=\sum _{r=1}^k{v}_{ir}{v}_{jr}.$$

これが二次FMです。たとえば材料の選択肢ごとに、熱・光・構造に関連する傾向を少数の数値で表し、それらの組合せから相互作用を推定する、と直観的に読めます。ただし学習された各成分に、必ずそのような物理的名称を割り当てられるわけではありません。

自由な二次式の $O(n^2)$ 個の係数に対し、FMのパラメータは $1+n+nk$ 個です。同時に観測されなかった変数対についても、別の観測で学習したベクトルを共有して予測できます。これが推薦システムなどの疎なデータでFMが使われる理由です。[4]

ここでいう疎なデータは、QUBOの結合が疎であることとは異なります。小さい $k$ のFMでも、内積が多くの変数対で非ゼロなら、候補探索に渡すQUBOは密になります。

4.2 学習は何を最小化するのか

回帰の基本例は、二乗誤差と正則化の和を最小化することです。

$$\mathcal{L}=\frac{1}{t}\sum _{a=1}^t{[y^{(a)}-{\hat{f}}_{\mathrm{F}\mathrm{M}}({\mathit{x}}^{(a)})]}^2+{\lambda }_w\sum _i{w}_i^2+{\lambda }_v\sum _{i,r}{v}_{ir}^2.$$

学習には確率的勾配法などを使います。$k$ を大きくすると表現能力が上がりますが、少数データでは過学習も起こります。$k$、正則化、学習を止める時点は検証データを使って調整します。最適化ループ中の評価データは偏って集まるので、学習誤差だけで予測性能を判断しないことも必要です。

FMの相互作用は次の形に書き換えられます。

$$\sum _{i<j}⟨{\mathit{v}}_i,{\mathit{v}}_j⟩x_i{x}_j=\frac{1}{2}\sum _{r=1}^k[{\left(\sum _i{v}_{ir}{x}_i\right)}^2-\sum _i{v}_{ir}^2{x}_i^2].$$

右辺を展開すると、対角項が引かれ、異なる変数の組が二回ずつ残るので、左辺になります。予測値と勾配を $O(nk)$ で計算できる理由がここにあります。特に

$$\frac{\partial {\hat{f}}_{\mathrm{F}\mathrm{M}}}{\partial v_{ir}}=x_i(\sum _j{v}_{jr}{x}_j-v_{ir}{x}_i)$$

です。全ての $v_{ir}$ をゼロにするとこの勾配もゼロになります。線形係数が更新されても相互作用は学べないため、潜在ベクトルは通常、小さな非ゼロ乱数などで初期化します。

4.3 学習したFMからQUBOを取り出す

上三角行列を使う規約なら、

$$Q_{ii}=w_i,Q_{ij}=⟨{\mathit{v}}_i,{\mathit{v}}_j⟩(i<j),Q_{ji}=0(i<j)$$

とするだけです。定数 $w_0$ は解の位置に影響しませんが、予測値の照合には必要です。対称行列 $Q^{\mathrm{s}\mathrm{y}\mathrm{m}}$ で ${\mathit{x}}^{\mathsf{T}}{Q}^{\mathrm{s}\mathrm{y}\mathrm{m}}\mathit{x}$ と書くなら、非対角成分は内積の半分です。この二倍の取り違えは実装で起こりやすい点です。

行列 $V{V}^{\mathsf{T}}$ は半正定値ですが、それだけで二値最適化が容易になるわけではありません。FMはその非対角要素を使い、対角の寄与は独立の線形係数と合わせて扱います。二値制約もあるので、連続変数の凸二次最適化と同じにはなりません。また低ランク性は相互作用を表現する因子の性質であり、取り出したQUBO全体のランクが必ず $k$ 以下という意味でもありません。

5. BOCSとFMQAを混同しない

観点	二次BOCS	基本的なFMQA
学習対象	二次係数の事後分布	線形係数と潜在ベクトル
少数データへの仮定	係数の縮小・疎性	相互作用の因子共有
探索の作り方	事後からモデルを抽出	予測最小化に別途探索を加える
候補探索	抽出した二次式を解く	学習した二次式を解く
主な調整点	事前分布・推論・モデル次数	潜在次元・正則化・学習

FMもベイズ的に学習できますが、単一のFMを二乗誤差で当てはめただけでは予測の事後分布は得られません。毎回その予測最小点だけを選ぶと、誤って低く予測された領域へ繰り返し向かうことがあります。

探索の補い方として、ランダムな未評価候補の混合、初期値を変えた複数FM、ブートストラップ、学習データのサブサンプリング、候補の近傍探索があります。ただし、モデルの初期値のばらつきを、そのまま較正済みのベイズ的な不確かさとみなすことはできません。[5]は、学習データの一部を毎回抽出してモデルを揺らし、探索と計算量を改善する研究です。

ここには二種類の乱数があります。一つは「どの代理モデルを解くか」を変える乱数、もう一つは「固定した代理モデルをどう探索するか」を変えるSA・QAの出力のばらつきです。同じモデルから多数の候補を出しても、それだけでモデルの不確かさを考慮したThompson samplingになるわけではありません。

6. 候補探索をSAで行う

候補探索の二次式を $E(\mathit{x})=\sum _i{a}_i{x}_i+\sum _{i<j}{b}_{ij}{x}_i{x}_j$ とします。ビット $i$ を反転するときのエネルギー差は

$$\mathrm{\Delta }{E}_i=(1-2x_i)(a_i+\sum _{j<i}{b}_{ji}{x}_j+\sum _{j>i}{b}_{ij}{x}_j)$$

です。下がる反転は受け入れ、上がる反転も温度 $T$ に応じて

$$p_{\mathrm{a}\mathrm{c}\mathrm{c}}=min\{1,\exp (-\mathrm{\Delta }{E}_i/T)\}$$

で受け入れます。ここでは $k_{\mathrm{B}}=1$ とし、$T$ をQUBOの係数と同じスケールで扱います。高温から低温へ冷却し、複数の初期状態で繰り返します。説明の詳細はSAの補遺を参照してください。

SAで調べている $E$ は代理モデルです。ビット反転のたびに高価な $f$ を呼び出す「直接SA」とは評価回数が大きく違います。BOCS-SAやFM-SAを直接SAと比較するときは、この違いを明記します。

固定個数の選択が必須なら、1ビット反転では実行可能集合を離れます。ペナルティを加える方法に加え、選択済みと未選択の二ビットを交換する移動を使えます。one-hot制約でも同じグループ内の交換が自然です。移動の設計が変われば探索性能も変わるので、QAとの比較条件に含めます。

7. 候補探索をQAで行う

$x_i=(1+s_i)/2$、$s_i\in \{-1,1\}$ を代入すると、QUBOは

$$\begin{array}{rl}E(\mathit{s})& =C+\sum _i{h}_i{s}_i+\sum _{i<j}{J}_{ij}{s}_i{s}_j,\\ J_{ij}& =b_{ij}/4,\\ h_i& =a_i/2+\frac{1}{4}(\sum _{j<i}{b}_{ji}+\sum _{j>i}{b}_{ij}),\\ C& =\frac{1}{2}\sum _i{a}_i+\frac{1}{4}\sum _{i<j}{b}_{ij}\end{array}$$

となります。もとの定数があれば $C$ に足します。ここでは $+h_i{s}_i+J_{ij}{s}_i{s}_j$ の符号規約です。ハミルトニアンを負号つきで定義する流儀とは、$h,J$ の符号が反転します。

QAでは、たとえば

$$\hat{H}(u)=-A(u)\sum _i{\hat{\sigma }}_i^x+B(u)(\sum _i{h}_i{\hat{\sigma }}_i^z+\sum _{i<j}{J}_{ij}{\hat{\sigma }}_i^z{\hat{\sigma }}_j^z)$$

を用いて候補を探索します。$u$ はアニーリングの進行を表します。実機では複数回測定し、得られたビット列を元のQUBOで採点して、新しい候補を選びます。

密なFMやBOCSのQUBOは、装置の疎な結合グラフにそのままは載りません。複数の物理量子ビットを一つの論理変数に対応づける埋め込み、チェーン強度、係数の規格化、チェーン切れの処理が必要になる場合があります。QPUの量子ビット数を、そのまま学習する特徴数の上限と読むことはできません。

係数を一様に正の定数倍しても理想的な最小点は不変です。しかし実機の雑音・有限精度やSAの温度に対する相対スケールは変わります。大きな制約ペナルティによって本来の予測差が小さく圧縮される場合は、特に注意が必要です。

実機出力を、そのまま厳密なBoltzmann分布や係数のベイズ事後分布とみなすこともできません。この補遺でのQAの基本的な役割は、与えられた二次式から有望な候補を生成することです。

8. 小さな数値例を最後まで追う

三つの部品から二つを選ぶ設計を考えます。学習の結果として、説明用のFMパラメータ

$$w_0=1,(w_1,w_2,w_3)=(-2,-1,0.5),(v_1,v_2,v_3)=(1,-1,0.5)$$

が得られたとします。潜在次元は $k=1$ です。内積は単なる積なので、

$$\hat{f}(\mathit{x})=1-2x_1-x_2+0.5x_3-x_1{x}_2+0.5x_1{x}_3-0.5x_2{x}_3$$

です。実行可能な三候補を手で評価すると、

候補	選んだ部品	予測値
$(1,1,0)$	1と2	$-3$
$(1,0,1)$	1と3	$0$
$(0,1,1)$	2と3	$0$

となり、次に試す候補は $(1,1,0)$ です。制約をQUBOに入れるなら

$$E=\hat{f}+\rho (x_1+x_2+x_3-2{)}^2$$

とします。$x_i^2=x_i$ から、ペナルティは $\rho [4-3\sum _i{x}_i+2\sum _{i<j}{x}_i{x}_j]$ です。各線形係数に $-3\rho$、各相互作用係数に $2\rho$、定数に $4\rho$ を加えればよいと分かります。この例で $\rho =2$ とすると8候補を全列挙しても $(1,1,0)$ が最小です。

本来のシミュレーションに渡した結果が、たとえば $y=-1.7$ だったとします。予測 $-3$ と違っても構いません。この観測を学習データに追加して、次のモデルを作り直します。「アニーラが正しく予測した」のではなく、「その候補を選んだことで情報が増えた」と読むのが逐次最適化です。

BOCSで同じ例を扱うなら、内積から係数を作る段階が、事後分布から係数ベクトルを引く段階に置き換わります。引いた二次式が違えば、次に選ぶ二部品も変わり得ます。

9. 実装を組み立てる順序

1. 入力と評価を固定します。 ビットの意味、実行可能条件、最小化の向き、失敗した評価の扱いを決めます。材料組成などの既知の制約は、可能なら学習に任せず明示します。
2. 初期データを作ります。 同じ候補を重ねず、変数の0と1、カテゴリの各選択肢が観測されるようにします。全てのビットを少なくとも一度有効にしても、全ての相互作用を同定できるわけではありません。
3. 値のスケールを整えます。 学習用の平均・標準偏差を保存し、予測を元の単位へ戻せるようにします。制約ペナルティの単位も揃えます。
4. モデルを学習します。 BOCSなら事後サンプルの収束を、FMなら検証誤差と初期値依存性を確認します。
5. QUBO変換を確認します。 小さい問題で全列挙し、モデルの予測とQUBOのエネルギーが定数差を除いて一致することを確かめます。
6. 複数の候補を生成します。 SA・QAの出力から、実行可能で未評価の候補を選びます。既評価の最小点しか出ない場合に備え、近傍候補やランダム候補への切替規則を用意します。
7. 真の値で更新します。 予測値を正解ラベルとして追加してはいけません。実験やシミュレーションの実測値を使います。
8. 実測の最良値を報告します。 雑音が大きい場合は最終候補を再評価し、偶然よかった一回の観測に依存していないか確認します。

この手順の骨格を擬似コードにすると、次の通りです。

D = 初期候補を真の関数で評価したデータ
while 真の評価回数 < 予算 and 未評価の実行可能候補がある:
    model = DからBOCSまたはFMを学習
    q = BOCSなら事後から抽出、FMなら学習済み係数から構築
    q = 既知の制約や選択コストを加える
    candidates = SAまたはQAでqから候補を生成
    x = 実行可能かつ未評価の候補を選ぶ
    if xがない:
        x = 事前に決めた探索規則で未評価候補を選ぶ
    y = 真の関数をxで評価
    D = Dに(x, y)を追加
return Dで実測値が最良の候補

実装の入口として、BOCSの著者実装とFMQAの著者実装があります。BOCSの配布実装にはSA版とSDP版があります。論文の再現には、モデルだけでなく、初期データ、乱数種、ソルバ設定、評価回数の数え方も揃えます。

10. 整数・連続変数と制約へ広げる

整数 $z\in \{0,\dots ,m-1\}$ はone-hot変数 $x_0,\dots ,x_{m-1}$ によって $z=\sum _{r=0}^{m-1}r{x}_r$、$\sum _r{x}_r=1$ と表せます。二進符号化はビット数を減らせますが、整数として隣り合う値でも複数ビットが変わる場合があります。domain-wall符号化では、連続した1と0の境界で値を表します。

符号化を変えると、同じ設計空間でも二次モデルが表現しやすい関数が変わります。ビット数だけでなく、代理モデルが学べる構造、制約違反の扱い、探索の移動距離を比較します。Seki–Tamura–Tanakaの整数変数研究 [6]は、この問題を直接扱っています。

連続変数では、格子へ離散化してから符号化する方法があります。解像度を上げるほど設計精度は上がりますが、学習や探索の負担も増えます。隣接する離散値の予測が不自然に振動する問題に対して、Endo–Takahashiの平滑化正則化 [7]が提案されています。

分子や構造のような複雑な対象は、二値潜在空間を持つ生成モデルで符号化し、その潜在ビットに対してFMを学習する方法もあります。潜在空間の候補を復号したときの妥当性や、同じ構造へ戻る重複も評価しなければなりません。

未知の制約 $g(\mathit{x})\le 0$ を学習する場合も注意が要ります。二次代理モデル $\hat{g}$ を二乗すると一般には四次になり、$max(0,\hat{g})$ もそのままではQUBOではありません。補助変数による定式化、別の二次ペナルティの学習、実行可能性を調べてから候補を選ぶ処理など、追加の方法を明示します。

11. 研究史: 基礎とSA・QAの比較

二次代理モデルを用いるブラックボックス最適化は、材料設計、分子探索、特徴選択へ応用できます。対象ごとに変数の符号化、評価関数、探索法がどのように組み合わされるかを見ていきます。

11.1 出発点

FMそのものの原著です。少ない因子を共有して変数間相互作用を予測するモデルを導入しました。QAを用いる最適化手法の論文ではありません。後年、二値入力の二次FMがQUBOになることが、アニーラへの接続点になります。[4]

疎なベイズ二次モデルとThompson samplingによる組合せ探索を導入しました。獲得関数の最適化にはSDPを使う版とSAを使う版があり、BOCSの成立時点でSAは比較対象であると同時に内部ソルバでもあります。[1]

放射冷却向けメタマテリアルの配置をFMで学習し、D-Wave 2000Qで次候補を選ぶFMQAの原著です。物性評価は電磁場シミュレーションが担います。学習、候補生成、物性評価を循環させる構成を具体化した研究です。[2]

11.2 QAとSAを直接比べたとき何が分かるか

疎性を調整したSK模型をブラックボックスとして、BOCSの内部ソルバをD-Wave 2000Q、SA、SDPで比較しました。この実験ではQAとSAがSDPよりよい結果を示す一方、QAのSAに対する優位は見つかりませんでした。代理モデルを用いる効果と、量子揺らぎ固有の効果を分けて読むための重要な研究です。[8]

基板の固定穴の選択を扱い、周波数解析をFMまたはBOCSで近似しました。FM-QUBOとBOCS-QUBO、SAと論文中でQAと呼ぶD-Wave Hybrid Solverを比較しています。後者は量子・古典ハイブリッドサービスなので、裸のQPUとSAの比較として引用してはいけません。また最適候補の周辺を確率的に学習へ追加する工夫があります。[9]

離散・連続の変数を含む行列圧縮を対象に、ベイズ回帰の事前分布やFMを比較した研究です。量子計算の宣伝例としてよりも、目的関数に対してどの代理モデルの仮定が合うかを読む題材です。[10]

磁気トンネル接合の障壁内の配置を、第一原理計算、FM、QAで探索しました。252通りの候補について、低エネルギーと高TMRを探す条件ではSA・ベイズ最適化・ランダム探索よりよい結果を報告し、低RAでは同様の優位が得られていません。特定の物性と比較設定に依存した結果であり、FMQA一般の計算量上の量子優位を示すものではありません。[11]

12. 応用の広がりをたどる文献地図

同じ「アニーリング」という語でも、熱揺らぎのSA、量子実機、デジタル回路、GPU上の古典探索は区別します。次の各項目では、原著で確認できる方法・対象を記し、ソルバの設定まで追えていない論文については量子実機の成果と断定しません。

12.1 光・熱・材料構造

透明な放射冷却材料の設計へ対象が広がった研究です。層の設計と波長依存の応答を結びつける応用として読めます。[12]

フォトニック結晶面発光レーザーの設計を対象とする研究です。二値選択の配置だけでなく、設計パラメータの符号化と高価な光学評価を接続する例です。[13]

ACS Applied Materials & Interfaces 15, 40606–40613。窒化チタンを用いた太陽光吸収構造の設計へ展開しています。[14]

コア・シェル型ナノ粒子の構造をFMQA、構成材料をベイズ最適化で選びます。内側の探索はGPU上のAmplify Annealing Engineで、QA実機は使用していません。[15]

光学ダイオードへの展開です。[16]

窓用の広角スペクトルフィルタを対象としています。[17]

Tamm構造の品質係数を高める設計です。題名に明示されている通り、古典アニーラを用いる系列です。[18]

粒子数も変わる結晶構造予測へ学習とアニーリングを組み合わせる研究です。[19]

安定なプロトン配置の探索です。材料配置の高価な評価とIsing型探索を結ぶ系列に位置します。[20]

QALOは、field-aware FM（FFM）による格子エネルギー予測、QAによる候補探索、機械学習ポテンシャルによる評価を循環させ、高エントロピー合金NbMoTaWの配置を調べます。通常のFMから、変数のグループに応じて因子を使い分けるモデルへ拡張した例です。[21]

CRYSIMは空間群、Wyckoff位置の組合せ、独立な原子座標を別々に符号化し、結晶の対称性で探索空間を縮めます。GPU上のFixstars Amplifyを用い、150原子超の単位胞について既存手法と比較しています。大きな問題を扱えた理由に、物理的な対称性の活用が含まれます。[22]

12.2 潜在空間・分子・生体配列

連続的で強い制約を持つ設計を機械学習で表現し、量子サンプリングへつなぐ研究です。二値潜在空間を用いたFMQAの関連系列として、入力をそのままビット化する方法との違いを読むとよいでしょう。[23]

離散潜在空間で非溶血性の抗菌ペプチドを設計する研究です。潜在変数のよい点を探索するだけでなく、配列へ復号し、機能を確かめる過程までが設計問題になります。[24]

分子設計をGPUベースのIsing machineへ接続しています。量子実機を使わずにこの枠組みを活用する明確な例です。原著

RNAの標的二次構造を実現する配列を探し、塩基の番号づけと二値符号化の影響を調べています。学習と探索の性能を左右するのはソルバだけではない、という具体例です。[25]

12.3 工学設計・特徴量選択

アナログ回路のトポロジー設計にFMとDigital Annealer、遺伝的アルゴリズムを組み合わせます。Digital Annealerは古典装置であり、QA実機とは区別します。[26]

X線回折由来の特徴と機械的性質を結びつける研究です。FMQAを特徴量選択に用いる系列として、どの特徴をモデルに入れるかという外側の探索に注目します。[27]

自動車技術会論文集56, 229–236。複数車種の同時構造設計へFMQAを適用した研究です。単一設計の性能と複数設計にまたがる条件を、同じ探索の中で扱う応用です。[28]

誤ったラベルを持つ学習事例を除く部分集合を、検証損失の二次代理モデルと候補の後処理を使って探索します。D-WaveのQPU上のclique sampler、NealのSA、OpenJijのSQAを比較しています。清浄な検証集合を利用する人工課題での結果であり、任意の実データで同じ差が出るとは限りません。単一FMの最小化や元のBOCSをそのまま使った実験とも区別します。[29]、[29]

糖度推定の波長領域を二値変数とし、疎な二次モデルとThompson samplingでPLS回帰に用いる領域を選びます。獲得関数のQUBOをSA・QAで最適化するBOCS系列の応用です。予測誤差だけでなく、選択した波長領域の局所摂動に対する安定性を検討しています。[30]

EV経路と充電拠点を同時に最適化し、電池容量の条件をベイズ推論で学ぶ研究です。BOCSの候補探索におけるSA・QA比較では、検討条件で信頼区間が大きく重なり、統計的に有意な差は確認されていません。未知の制約の学習という展開として重要です。[31]

変化する環境に追従する実時間のブラックボックス最適化へFMQAの考え方を広げます。simulated bifurcationを用いた古典Ising machineの系列であり、通常のSAやQA実機とは分けて読みます。[32]

13. 方法の改良と隣接する研究

整数をビットへ写すときの符号化を主題とする研究です。ビット数と予測の学びやすさの両方を考える入口です。[6]

離散化した連続変数に対し、FM予測の滑らかさを学習へ組み込む方法です。[7]

学習データの部分集合を使うことでモデルの変動を作り、探索と学習コストの両方を扱います。FMの探索不足を、量子性とは別のアルゴリズム上の問題として捉える研究です。[5]、[5]

リバースアニーリングを用いたバッチ候補生成の系列です。既知の候補から探索を始める考え方はリバースアニーリングの補遺につながります。著者による掲載情報

one-hotの各ビットが初期データで有効になる機会を確保する方法です。初期データの設計を、探索開始前の準備ではなく性能を左右する要素として扱います。[33]

学習時と探索時で符号化を変える方法です。one-hotで学習しdomain-wallで探索するなど、実行可能状態での目的値を保つ変換を調べます。改善は条件依存で、単一の符号化が常に最良という主張ではありません。[34]

FMとIsing表現に補助変数を導入し、学習時にその変数も更新して高次の特徴間相互作用を捉える研究です。薬剤の組合せ効果の予測を検討しています。二次モデルの表現力を拡張する関連研究であり、この予測性能の改善だけからSA・QAによる閉ループ最適化の優位を結論してはいけません。[35]

融点やイオン伝導度などを指標に巨大な化学探索空間を扱う、古典のquantum-inspired annealingによる関連研究です。FMQAと同じ名称の手法として一括せず、回帰モデルと特徴表現の選び方も含めて読む必要があります。[36]

ランダム部分空間符号化と非負重みの回帰によって連続入力を扱う関連手法です。QAで獲得関数を探索しますが、BOCSや二次FMと同一の代理モデルではありません。[37]

こちらはベイズ最適化でQAの駆動スケジュールを設計する研究です。本補遺の「QAを獲得関数のソルバにする」方向とは、最適化する対象が違います。QAとベイズ最適化の関係を調べる際に混同しやすいため、隣接研究として分けておきます。[38]

FMQAの方法、実装、材料・化学・工学への展開を追う総説です。個別研究を探すための入口として使い、比較の数値や使用装置の詳細は各原著に戻って確かめます。[3]、[3]

14. 「うまくいった」をどう測るか

ブラックボックス最適化では、まず真の評価回数 $t$ に対する最良実測値

$$f_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}(t)=\underset{1\le a\le t}{min}f({\mathit{x}}^{(a)})$$

を比較します。雑音があるときは $f$ 自体を直接知ることができないため、観測最良値と、再評価した性能の推定値を区別します。初期データを揃えた複数試行で、平均・中央値だけでなくばらつきも示します。

さらに総所要時間を

$$T_{\mathrm{t}\mathrm{o}\mathrm{t}\mathrm{a}\mathrm{l}}=T_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{a}\mathrm{l}}+\sum _{\text{各反復}}(T_{\mathrm{l}\mathrm{e}\mathrm{a}\mathrm{r}\mathrm{n}}+T_{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{p}\mathrm{o}\mathrm{s}\mathrm{e}}+T_{\mathrm{e}\mathrm{v}\mathrm{a}\mathrm{l}\mathrm{u}\mathrm{a}\mathrm{t}\mathrm{e}})$$

に分けます。候補生成時間には、埋め込み、通信、待機、測定、後処理など、その利用場面で発生する費用を含めます。アニーリング時間だけの比較と、利用者が待つ時間の比較は別です。

比較の軸は、次の三つです。

• モデルの比較: 同じ候補ソルバで、BOCSとFM、異なる潜在次元や事前分布を比べます。
• ソルバの比較: 同じ学習済みQUBOをSAとQAへ渡し、候補の品質・多様性・生成時間を比べます。
• 閉ループ全体の比較: 同じ初期データと評価予算で、ランダム探索、直接SA、ほかのベイズ最適化などと比べます。

閉ループでは、一度違う候補を評価すると、その後の学習データも変わります。最終成績の差をソルバだけに帰属させるには、固定QUBOの比較を合わせるなどの切り分けが必要です。予測誤差が小さいモデルが、最適値に近い候補を最も早く見つけるとも限りません。探索に重要な領域での順位、過小予測、未探索領域への広がりも関わります。

BOCSとFMがQUBOの系譜に加えたものは、問題を式へ翻訳する段階に、観測からの学習を持ち込んだことです。変数、モデル、探索器、実験を一周つないで初めて最適化になります。その一周のどこを改善したのかを問うと、SAとQAの役割も具体的に議論できます。

15. 手を動かすための演習

1. 第8節の全8候補についてFM予測とペナルティを計算し、$\rho =0,0.5,2$ で最小解がどうなるか調べてください。この例だけから、一般のペナルティ強度を決められるでしょうか。
2. 第7節のQUBO–Ising変換を導出し、第8節の各候補でエネルギーが一致することを確認してください。
3. 同じ初期データから、FMの予測最小化だけを使う方法と、一定確率でランダム候補を混ぜる方法を比較してください。真の評価回数と最良実測値を記録します。
4. 自由な二次モデル、縮小を使う二次モデル、低ランクFMに、それぞれ得意・不得意になりそうな目的関数を作ってください。高次相互作用を加えた場合も調べます。
5. 文献からSA・QAの比較を一つ選び、初期データ、代理モデル、候補数、総評価回数、総時間、装置の種類を表にしてください。論文が比較しているのは、モデル・ソルバ・閉ループのどれでしょうか。

参考文献

1. Ricardo Baptista, Matthias Poloczek, “Bayesian Optimization of Combinatorial Structures,” International Conference on Machine Learning, 462–471 (2018). 出典

2. Koki Kitai, Jiang Guo, Shenghong Ju, Shu Tanaka, Koji Tsuda, Junichiro Shiomi, et al., “Designing metamaterials with quantum annealing and factorization machines,” Physical Review Research 2, 013319 (2020). 出典

3. Ryo Tamura, Yuya Seki, Yuki Minamoto, Koki Kitai, Yoshiki Matsuda, Shu Tanaka, et al., “Black-box optimization using factorization and Ising machines,” Applied Physics Reviews 13, 021307 (2026). 出典

4. Steffen Rendle, “Factorization Machines,” 2010 IEEE International Conference on Data Mining, 995–1000 (2010). 出典

5. Yusuke Hama, Tadashi Kadowaki, “Subsampling factorization machine annealing,” Physical Review Research 8, 013187 (2026). 出典

6. Yuya Seki, Ryo Tamura, Shu Tanaka, “Black-box optimization for integer-variable problems using Ising machines and factorization machines,” arXiv:2209.01016 (2022). 出典

7. Katsuhiro Endo, Kazuaki Z. Takahashi, “Function smoothing regularization for precision factorization machine annealing in continuous variable optimization problems,” Physical Review Research 7, 013149 (2025). 出典

8. Ami S. Koshikawa, Masayuki Ohzeki, Tadashi Kadowaki, Kazuyuki Tanaka, “Benchmark Test of Black-box Optimization Using D-Wave Quantum Annealer,” Journal of the Physical Society of Japan 90, 064001 (2021). 出典

9. Tadayoshi Matsumori, Masato Taki, Tadashi Kadowaki, “Application of QUBO solver using black-box optimization to structural design for resonance avoidance,” Scientific Reports 12, 12143 (2022). 出典

10. Tadashi Kadowaki, Mitsuru Ambai, “Lossy compression of matrices by black box optimisation of mixed integer nonlinear programming,” Scientific Reports 12, 15482 (2022). 出典

11. Kenji Nawa, Tsuyoshi Suzuki, Keisuke Masuda, Shu Tanaka, Yoshio Miura, “Quantum Annealing Optimization Method for the Design of Barrier Materials in Magnetic Tunnel Junctions,” Physical Review Applied 20, 024044 (2023). 出典

12. Seongmin Kim, Wenjie Shang, Seunghyun Moon, Trevor Pastega, Eungkyu Lee, Tengfei Luo, “High-Performance Transparent Radiative Cooler Designed by Quantum Computing,” ACS Energy Letters 7, 4134–4141 (2022). 出典

13. Takuya Inoue, Yuya Seki, Shu Tanaka, Nozomu Togawa, Kenji Ishizaki, Susumu Noda, “Towards optimization of photonic-crystal surface-emitting lasers via quantum annealing,” Optics Express 30, 43503 (2022). 出典

14. Seongmin Kim, Shiwen Wu, Ruda Jian, Guoping Xiong, Tengfei Luo, “Design of a High-Performance Titanium Nitride Metastructure-Based Solar Absorber Using Quantum Computing-Assisted Optimization,” ACS Applied Materials & Interfaces 15, 40606–40613 (2023). 出典

15. Makoto Urushihara, Masaya Karube, Kenji Yamaguchi, Ryo Tamura, “Optimization of Core–Shell Nanoparticles Using a Combination of Machine Learning and Ising Machine,” Advanced Photonics Research 4, 2300226 (2023). 出典

16. Seongmin Kim, Su-Jin Park, Seunghyun Moon, Qiushi Zhang, Sanghyo Hwang, Sun-Kyung Kim, et al., “Quantum annealing-aided design of an ultrathin-metamaterial optical diode,” Nano Convergence 11, 16 (2024). 出典

17. Seongmin Kim, Serang Jung, Alexandria Bobbitt, Eungkyu Lee, Tengfei Luo, “Wide-angle spectral filter for energy-saving windows designed by quantum annealing-enhanced active learning,” Cell Reports Physical Science 5, 101847 (2024). 出典

18. Jiang Guo, Koki Kitai, Hideyuki Jippo, Junichiro Shiomi, “Boosting the quality factor of Tamm structures to millions by quantum inspired classical annealer with factorization machine,” arXiv:2408.05799 (2024). 出典

19. Yannick Couzinié, Yuya Seki, Yusuke Nishiya, Hirofumi Nishi, Taichi Kosugi, Shu Tanaka, et al., “Machine Learning Supported Annealing for Prediction of Grand Canonical Crystal Structures,” Journal of the Physical Society of Japan 94, 044802 (2025). 出典

20. Jianbo Lin, Tomofumi Tada, Ai Koizumi, Masato Sumita, Koji Tsuda, Ryo Tamura, “Determination of Stable Proton Configurations by Black-Box Optimization Using an Ising Machine,” The Journal of Physical Chemistry C 129, 2332–2340 (2025). 出典

21. Zhihao Xu, Wenjie Shang, Seongmin Kim, Eungkyu Lee, Tengfei Luo, “Quantum annealing-assisted lattice optimization,” npj Computational Materials 11, 4 (2025). 出典

22. Chen Liang, Diptesh Das, Jiang Guo, Ryo Tamura, Zetian Mao, Koji Tsuda, “Predicting symmetric structures of large crystals with GPU-based Ising machines,” Communications Physics 8, 477 (2025). 出典

23. Blake A. Wilson, Zhaxylyk A. Kudyshev, Alexander V. Kildishev, Sabre Kais, Vladimir M. Shalaev, Alexandra Boltasseva, “Machine learning framework for quantum sampling of highly constrained, continuous optimization problems,” Applied Physics Reviews 8, 041418 (2021). 出典

24. Andrejs Tučs, Francois Berenger, Akiko Yumoto, Ryo Tamura, Takanori Uzawa, Koji Tsuda, “Quantum Annealing Designs Nonhemolytic Antimicrobial Peptides in a Discrete Latent Space,” ACS Medicinal Chemistry Letters 14, 577–582 (2023). 出典

25. Shuta Kikuchi, Shu Tanaka, “Factorization machine with quadratic-optimization annealing for RNA inverse folding and evaluation of binary-integer encoding and nucleotide assignment,” Scientific Reports 16, 20460 (2026). 出典

26. Masaharu HIDA, Hiroshi IKEDA, Akito MARUO, Masaru SATO, Takashi YAMAZAKI, “Topology optimization of analog circuit design via global optimization using factorization machines with digital annealer,” Journal of Advanced Mechanical Design, Systems, and Manufacturing 18, JAMDSM0076-JAMDSM0076 (2024). 出典

27. Ryo Tamura, Kenji Nagata, Keitaro Sodeyama, Kensaku Nakamura, Toshiki Tokuhira, Satoshi Shibata, et al., “Machine learning prediction of the mechanical properties of injection-molded polypropylene through X-ray diffraction analysis,” Science and Technology of Advanced Materials 25, 2388016 (2024). 出典

28. 近藤 俊樹, 小平 剛央, 源 勇気, “FMQAを用いた複数車種の車体構造同時設計最適化,” 自動車技術会論文集 56, 229–236 (2025). 出典

29. Makoto Otsuka, Kento Kodama, Keisuke Morita, Masayuki Ohzeki, “Filtering out mislabeled training instances using black-box optimization and quantum annealing,” Scientific Reports 15, 37892 (2025). 出典

30. Mitsunobu Kanebako, Ami S. Koshikawa, Masaru Hitomi, Takuro Tanaka, Mahito Chiba, Maiko Mori, et al., “Robust Wavelength Selection for Partial Least Squares Sugar Content Estimation Using Combinatorial Bayesian Optimization,” arXiv:2607.27645 (2026). 出典

31. Akihisa Okada, Keisuke Otaki, Hiroaki Yoshida, “Joint optimization of electric vehicle routes and charging locations through learning charge constraints using QUBO solvers,” Scientific Reports 16, 25090 (2026). 出典

32. Tomoya Kashimata, Yohei Hamakawa, Masaya Yamasaki, Kosuke Tatsumura, “Real-time black-box optimization for dynamic discrete environments using embedded Ising machines,” Nature Communications 17, 8085 (2026). 出典

33. Taiga Hayashi, Yuya Seki, Kotaro Terada, Yosuke Mukasa, Shuta Kikuchi, Shu Tanaka, “Improving FMQA via Initial Training Data Design Considering Marginal Bit Coverage in One-Hot Encoding,” arXiv:2605.04825 (2026). 出典

34. Ryo Ogawa, Mayumi Nakano, Yuya Seki, Shu Tanaka, “Stage-dependent integer-binary encoding in factorization-machine black-box optimization,” arXiv:2606.23188 (2026). 出典

35. Anbang Wang, Dunbo Cai, Yu Zhang, Yangqing Huang, Xiangyang Feng, Zhihong Zhang, “Surrogate modeling via factorization machine and Ising model with enhanced higher-order interaction learning,” Physical Review Research 8, 013037 (2026). 出典

36. Kan Hatakeyama-Sato, Takahiro Kashikawa, Koichi Kimura, Kenichi Oyaizu, “Tackling the Challenge of a Huge Materials Science Search Space with Quantum‐Inspired Annealing,” Advanced Intelligent Systems 3, 2000209 (2021). 出典

37. Syun Izawa, Koki Kitai, Shu Tanaka, Ryo Tamura, Koji Tsuda, “Continuous black-box optimization with quantum annealing and random subspace coding,” arXiv:2104.14778 (2021). 出典

38. Jernej Rudi Finžgar, Martin J. A. Schuetz, J. Kyle Brubaker, Hidetoshi Nishimori, Helmut G. Katzgraber, “Designing quantum annealing schedules using Bayesian optimization,” Physical Review Research 6, 023063 (2024). 出典