QAOAの応用（問題の定式化）

QAOAは、組み合わせ最適化問題の解を求めるためのアルゴリズムであるわけですが、多くのチュートリアルでは、問題の定式化が天下り的に与えられ、その定式化方法が解説されています。実際の課題を解く場合、この定式化の部分が大きな課題になることは、間違いありません。

最適化問題を解くステップは、以下のようになります。

課題を抽出する。
組み合わせ最適化問題として解くことができる問題を抽出する。
解決すべき問題にたいして、一般に知られている数十パターンの定式化済みの組み合わせ最適化問題を使うことができるかどうかを判断する。適用できない場合は、目的関数や制約条件などを定義して、新たに定式化する。
QUBOに変換する。
最適解の算出をする。

数理最適問題

数理最適化は、数式を使って問題を数理モデルで表して解く手法です。数理最適化は、連続要素のみの連続最適化と連続以外のりさん要素を含む組み合わせ最適化にわけれらます。量子アルゴリズムで扱われるのは、もちろん、組み合わせ最適化ということになります。問題を数理モデルで表すことを定式化するといいます。

定式化の要素

決定変数 :何を決めたいのか。
例： $\forall x_{i} \in\{0,1\}$
目的関数: どうなってほしいか。
例： $\sum_{i} p_{i} x_{i}$ の最大化
制約条件
例： $\sum_{i} w_{i} x_{i} \leq 5$

古典コンピュータの世界では、数理最適化問題を解くツールは、ソルバーと呼ばれます。

典型問題

一般に知られている定式化済みの組み合わせ最適化の典型問題です。数多くの問題がすでに定式化されています。

典型問題クラス	典型問題
グラフ・ネットワーク問題	最小全域木問題
	最大安定集合問題
	最大カット問題
	最小頂点被覆問題
	最短路問題
	最大流問題
	最小費用流問題
経路問題	運搬経路問題
経路問題	巡回セールスマン問題
集合被覆・分割問題	集合被覆問題
集合被覆・分割問題	集合分割問題
スケジューリング問題	ジョブショップ問題
スケジューリング問題	勤務スケジューリング問題
切出し・詰込み問題	ナップサック問題
	ビンパッキング問題
	n次元パッキング問題
配置問題	施設配置問題
配置問題	容量制約なし施設配置問題
割当・マッチング問題	2次割当問題
	一般化割当問題
	最大マッチング問題
	重みマッチング問題
	安定マッチング問題

汎用問題

典型問題で対応できない場合は、数理モデルをそのまま扱います。数理モデルで表された問題を汎用問題と呼ばれ、つぎのようなものがあります。

線形最適化問題
変数が連続変数で目的関数と制約条件が線形なもの。
混合整数最適化問題
目的関数と制約条件は線形で、変数の中に整数変数を含むもの。この分類では、組み合わせ問題は、ここにはいります。
非線形最適化問題

Pythonによる典型問題の分析例

ナップザック問題

詰込む荷物の容量(size) の和がナップサックの容量(capacity) を超えないように、荷物の価値(weight) の和を最大にするというナップザック問題の例です。

from ortoolpy import knapsack
size = [21, 11, 15, 9, 34, 25, 41, 52]
weight = [22, 12, 16, 10, 35, 26, 42, 53]
capacity = 100
knapsack(size, weight, capacity)
>>>
(105, [0, 1, 3, 4, 5])

汎用問題として分析すると以下のようになります。

from pulp import *
size = [21, 11, 15, 9, 34, 25, 41, 52]
weight = [22, 12, 16, 10, 35, 26, 42, 53]
capacity = 100
r = range(len(size))
m = LpProblem(sense=LpMaximize) # 数理モデル
x = [LpVariable('x%d'%i, cat=LpBinary) for i in r] # 変数
m += lpDot(weight, x) # 目的関数
m += lpDot(size, x) <= capacity # 制約
m.solve()
print((value(m.objective), [i for i in r if value(x[i]) > 0.5]))
>>>
(105.0, [0, 1, 3, 4, 5])

最短路問題

グラフにおいて、始点から終点までの経路の中で最も短い経路を探すのが、最短路問題です。

import networkx as nx
g = nx.fast_gnp_random_graph(8, 0.26, 1)
nx.dijkstra_path(g, 0, 2)
>>>
[0, 1, 6, 3, 5, 2]

汎用問題として解くと以下のようになります。

from pulp import *
import networkx as nx
g = nx.fast_gnp_random_graph(8, 0.26, 1).to_directed()
source, sink = 0, 2 # 始点, 終点
r = list(enumerate(g.edges()))
m = LpProblem() # 数理モデル
x = [LpVariable('x%d'%k, lowBound=0, upBound=1) for k, (i, j) in r] # 変数(路に入るかどうか)
m += lpSum(x) # 目的関数
for nd in g.nodes():
    m += lpSum(x[k] for k, (i, j) in r if i == nd) \
      == lpSum(x[k] for k, (i, j) in r if j == nd) + {source:1, sink:-1}.get(nd, 0) # 制約
m.solve()
print([(i, j) for k, (i, j) in r if value(x[k]) > 0.5])
>>>
[(0, 1), (1, 6), (3, 5), (5, 2), (6, 3)]

このように古典コンピュータの世界では、組み合わせ最適化問題は、ソルバーが整備されています。

QAOAにおける定式化

QAOAにおいても、いろんな問題が定式化がすでにされています。

厳密被覆問題のコスト関数

ある自然数の集合$U， V_1, V_2, ···, V_N$ があ_るときに，いくつかの $V_i$ を選んで含まれる自然数が，同じ自然数が複数含まれないようにしつつ $U$ と同じセットになるように $V_i$ を選ぶという問題です。
コスト関数は， $V_i$ を選んだことを表す変数 $xi ∈ {0, 1}$ （選んだら 1）に対して、定数項を除外して以下のように書けます。

$$
C \sum_{a=1}^{n}\left(1-\sum_{i, a \in V_{i}} x_{i}\right)^{2} \rightarrow C \sum_{a=1}^{n}\left(-\sum_{i=j, V_{j}} x_{i} x_{j}+2 \sum_{i \neq j, \atop a \in V_{i}, V_{j}} x_{i} x_{j}\right)
$$

セールスマン巡回問題のコスト関数

都市の集合と各都市間の距離が与えられ，すべての都市を一度ずつだけ訪問し，出発地に戻る距離が最小の経路を求めるという組合せ最適化問題です。コスト関数は，都市 $v$ を $j$番目に訪れるかどうかを表す変数$x_{v,j} ∈ {0, 1}$ に対して以下のように与えられます。

$$
\begin{aligned}
C_{1} & \sum_{v=1}^{N}\left(1-\sum_{j=1}^{N} x_{v, j}\right)^{2}+C_{2} \sum_{j=1}^{N}\left(1-\sum_{v=1}^{N} x_{v, j}\right)^{2} +\sum_{(u, v) \in E} W_{u, v} \sum_{j=1}^{N} x_{u, j} x_{v, j+1}
\end{aligned}
$$
変数は、$N^2$個あるので、コスト関数の行列は、$N^2×N^2$個あり、QAOAでは、変数の数だけ量子ビットが必要ですので、例えば、量子ビット１００としても、$N＝10$の問題がとけるだけです。大規模な問題は、NISQ量子コンピュータには適しません。

ポートフォリオ最適化問題のコスト関数

ポートフォリオがもたらす収益率の期待値と変動の大きさであるリスクを，収益率の分布の平均と分散を用いて評価するモデルで，分散を最小化する問題を考えたとき、資産 $i$ を保有しているかどうかの変数を $x_i ∈ {0, 1}$ とすると，コスト関数は以下のように書けます。
$$
-\sum_{i} \mu_{i} x_{i}+\gamma \sum_{i j} \sigma_{i j} x_{i} x_{j}+C\left(\sum_{i} x_{i}-N\right)^{2}
$$

$μ_i$ は資産 $i$ からのリターンの期待値， $σ_{ij}$ は資産 $i, j$ のリターンの共分散， $γ$ はどれだけリスクを考慮するかというパラメータです。第3項は資産数 $N$ を一定とする制約条件に対応する項で，選択された $x_i = 1$ の個数が指定の資産数 $N$ のときに最小値0をとります。

このように、QAOAでは、古典コンピュータの数理最適化ソルバとは違い、コスト関数に制約条件の項を付け加え、最適化問題を解きます。

Quantum Alternating Operator Ansatz

コスト関数に制約条件の項をつけるのではなく、初期状態を作る $U_X(β)$ を工夫することで初期状態を制限し，制約条件を考慮しつつ探索空間を削減して計算の効率化を図る Quantum Alternating Operator Ansatz と呼ばれる手法も提案されています。

コスト関数

定式化されていない問題については、定式化をしないといけません。上の定式化された例にもあるように、コスト関数に、制約条件を加えて、期待値を最小化することにより、最適化問題を解きます。目的関数に関しては、比較的容易に定式化できますが、制約条件の定式化は、ちょっとやっかいです。

量子コンピュータの応用 – QAOAの仕組みとこれを応用した組合せ最適化問題のプログラミングで解説されている交通量最適化の例では、道路の混雑度合いを評価する目的関数に、加えて、2つの車のとれるルートの制約条件が、コスト関数に加えられています。

$$x_{0}+x_{1}+x_{2}=1$$

$$x_{3}+x_{4}+x_{5}=1$$

$$
M=-\sum_{i=0, j=3}^{2,5} J_{i j} x_{i} x_{j}-k\left\{\left(\sum_{i=0}^{2} x_{i}-1\right)^{2}+\left(\sum_{j=3}^{5} x_{j}-1\right)^{2}\right\}
$$
このような制約条件を定式化するには、以下のようなやり方があります。
0 か 1 をとる変数 $x_0,x_1,\cdots,x_{n-1}$を考えて、$\sum_{i \leq j} c_{i j} x_{i} x_{j}$ を最小化するという問題を考えます。

$c_{ij}$ がプラスなら、$x_i$ と $x_j$ のどちらかが０が望ましい。
$c_{ij}$ がマイナスなら、$x_i$ と $x_j$ の両方１が望ましい。
「AかつB」が望ましいなら、$c_{AB}x_Ax_B$ の項がマイナスになるのが望ましい。
「AまたはB」が望ましいなら、$c_{A A}=c_{B B}=-t, c_{A B}=t, t>0$ として、$c_{A A} x_{A}+c_{B B} x_{B}+c_{A B} x_{A} x_{B}=-t x_{A}-t x_{B}+t x_{A} x_{B}$ とすればよい。
「A、B、Cのどれか一つを選ぶ」という条件は、$\left(x_{A}+x_{B}+x_{C}-1\right)^{2}=0$ となればいいので、$t>0$ として、$t\left(x_{A}+x_{B}+\right.\left.x_{C}-1\right)^{2}=2 t x_{A} x_{B}+2 t x_{A} x_{C}+2 t x_{B} x_{C}$ となるようにパラメータを選べばよい。
上の交通量最適化のコスト関数には、これが使われています。