量子アニーリング入門
2020年12月16日 (2021年04月23日更新)株式会社知能情報システム アモリン カーシオ
1. 概要
1.1 量子アニーリングとは
量子アニーリングとは、スケジュール問題などの組み合わせ最適化問題の解法の一つです。量子状態の特有の量子揺らぎを利用して最適解を求めるための方法であり、シミュレーテッド アニーリングと類似の手法です。
量子アニーリングは最適解を求めるため、問題に合わせた量子状態の重ね合わせ状態を生成し、強い量子揺らぎを生み出します。次に、量子揺らぎを少しずつ弱くしながら、基底状態（解きたい問題の解に収束した最低エネルギーの状態）を目指します。
このような量子揺らぎの制御はD-Wave 社の量子アニーリング マシンによって実現されています[1]。量子アニーリング マシンは、量子アニーリングで扱う問題を量子系として物理的に実装することができる計算機で、この形の基底状態を高速に作り出すことができるため、原理的に解を高速に求めることが可能です。
1.2 量子アニーリングの適用と実装
量子アニーリングを解きたい問題に適用するにあたり、その問題を 0，1の変数を持つ数式の最小値を求める問題に書き換えます。これは、量子アニーリングマシンの基本構成要素が2つの状態を持つためです。この書き換えた問題を QUBO (Quadratic Unconstrained Binary Optimization、二次制約なし二値最適化) と呼びます。
次に、QUBO の数式を量子処理ユニット（QPU）にエンベッド（埋め込む、embed)します。
その後、0 と 1 の重ね合わせを生成すると、量子揺らぎが発生します。この量子揺らぎを徐々に弱めていくと、基底状態を得ることができます。この基底状態の量子ビットの値が最適解です。
1.3 逆アニーリング
逆アニーリングは、ある解の近傍に存在するより良い解を探る方法です。これは、一度見つかった局所解の改善を繰り返す手法で、ランダムな探索を繰り返すよりも早く解を求められる可能性があります。具体的には、量子アニーリングが収束した状態に、再度量子揺らぎを導入し、再度アニーリングを繰り返します。
2. 応用例：看護師スケジューリング問題
応用例として、池田ら[2]による看護師のスケジューリング問題への適用を見てみましょう。この問題では、以下の制約条件を考えます：
- ハード シフト制約：各看護師は、連日出勤は禁止とします (たとえば、火曜日に出勤したら翌日の水曜日に出勤してはいけません)。
- ハード看護師制約：看護師全体としては、毎日決まった労働力 (＝\(\sum_{看護師}\)能力×時間) を満たす必要があります。ただし、看護師一人のエフォート (＝能力×時間) は各看護師で異なってもよい。
- ソフト看護師制約：できる限り、各看護師の休日希望を考慮します。
2.1 定式化
それぞれの制約条件を QUBO に翻訳します。そのため、まずはバイナリー変数 \(q_{(n,d)}\) を導入します。\(q_{(n,d)}\) のインデックスは \(n\) 番目の看護師と \(d\) 番目の日（スケジュールの予定日）の関数です。例えば、全部で \(N\) 人の看護師と \(D\) 日のスケジュールを組む場合、バイナリー変数 \(q_{(n,d)}\) のインデックスは \((n,d)≔ n×(D-1)+d\) (0 から数える) と定義できます。
各制約条件は \(q_{(n,d)}\) の 2 次関数を最小化する条件に定式化します。具体的には、以下のようになります。
1. ハード シフト制約：各看護師の連日出勤は禁止
一般的に、\(i\ne j\) の間の制約条件を \(J_{ij}q_iq_j\) (ここで \(J_{ij}\) は何らかの係数) で表現し、\(\sum J_{ij}q_iq_j\)を最小化するように定式化します。\(n\) 番目の看護師が \(d\) 日目と \(d+1\) 日目に連日出勤することは \(q_{(n,d)}=q_{(n,d+1)}=1\)と表せます。これを避けるため、この時に大きくなるようなエネルギー項 \(J_{ij}q_iq_j\) を導入します。そのため、このような変数の間だけに \(J_{ij}\) を大きくして、\(q_{(n,d)}=q_{(n,d+1)}=1\) の場合におけるエネルギーが増加する傾向を作ります（つまり、エネルギー ペナルティを導入します）。これは、次式のように表現できます。
\[ \sum J_{(n,d),(n',d' )} q_{(n,d)} q_{(n',d')}, \qquad J_{(n,d),(n',d' )}=\left\{ \begin{array}[ll]\ a & \mathrm{if}\, n=n',d=d'±1 \\ 0, & \mathrm{otherwise} \end{array} \right.≡a\delta_{n,n'} \delta_{d,d'+1}\]この総和は連日出勤がない場合のみ 0 となり、連日出勤が生じたら一回当たりエネルギーが \(a\) だけ増加します。
2. ハード看護師制約：看護師全体として毎日決まった労働力を満たす必要があります
一日に必要な労働力とエフォートが釣り合うことが制約条件です。一日に必要な労働力を \(W(d)\) とおき、各看護師のエフォートを \(E(n)\) と書くと、次式がゼロになることが釣り合う条件となります。
\[\left(\sum_n^{N-1} E(n) q_{(n,d)}\right)-W(d) \]一日の総エフォート (\(\sum_n E(n) q_{(n,d)}\) ) と必要な労働力（\(W(d)\)）が釣り合う際に最小エネルギーを得るため、この式を変形します。量子アニーリング マシン上で解くことを考慮し、 QUBO として問題が解けるように、全体を 2 乗します。これで、二次制約なし二値最適化（QUBO）が実現できます。
これは一日当たりの条件であるため、日について総和を取ります。したがって、次式がこの条件を表します。
\[\sum_d^{D-1} \left\{ \sum_n^{N-1} \left(E(n) q_{(n,d)}\right)-W(d)\right\}^2 \]3. ソフト看護師制約：各看護師の休日希望を尊重します。
一人の看護師の出勤希望を \(G(n,d)\) で表します。この関数は、出勤希望を 1、休日希望を 0 というような2値関数にすることもできますし、出勤でも休日でも良い日を 0.5 とするような3値関数にすることもできます。また、その看護師が雇用契約上必ず出勤しなければならない日数を \(F(n)\) で表します。すべての看護師の希望をできる限り満たすような制約条件は、次式のように表現できます。この項も、ハード看護師制約の項と同様に2乗します。
\[\sum_n^{N-1} \left\{\sum_d^{D-1} \left( G(n,d) q_{(n,d)}\right)-F(n) \right\}^2 \]以上の制約条件の線形結合が解きたい問題のハミルトニアン (エネルギー関数) \(H(q)\) になります。
\[H(q)= \sum_{n,d} J_{(n,d),(n',d' )} q_{(n,d)} q_{(n',d')} \\ + \lambda \sum_d^{D-1} \left\{ \sum_n^{N-1} \left(E(n) q_{(n,d)}\right)-W(d)\right\}^2 + \gamma \sum_n^{N-1} \left\{\sum_d^{D-1} \left( G(n,d) q_{(n,d)}\right)-F(n) \right\}^2 \]上記の \(\lambda>0\) と \(\gamma>0\) は、各制約条件の相対的な強度を調整するためのパラメーターです。パラメータ設定によって最適解が異なるため、解くべき問題に合わせた値を選ぶ必要があります。具体的には、各制約条件の相対的な重要度に応じて各パラメータを決めます。
2.2 QPU 上への問題の埋め込み
以上で、問題を数理的に表現できていますが、問題を QPU にエンベッドする必要があります。上式第 1 項に現れている変数 q_i 同士の結合は必ずしも QPU 上で直接実装できるとは限りません。その理由はQPUのトポロジー\(^1\) にあります。先述のQUBOの定式化では、任意の2つの変数 q_((n,d)) と q_((n’,d’)) の積が存在しますが、QPU上では物理的に隣接した量子ビット同士に対応する積しかハミルトニアンの項として実装できません。そのため、1論理量子ビットを複数の物理量子ビットを使って実現します（図２）。このように、量子アニーリングを実装するためには、QUBO で表現した問題を QPU 上にエンベッドする必要があります。D-Wave 2000Q (前世代の量子アニーリング マシン) までの世代のD-Wave (量子アニーリング マシンを制作している会社) のマシンは、キメラ グラフ（chimera graph）というトポロジーで量子ビットが結合しており、一つの量子ビットは 6 個の量子ビットと結合しています。最新の D-Wave Advantage システムは、ペガサス グラフ（pegasus graph）トポロジーに変更され、1 個の量子ビットは 15 個の量子ビットと結合しており、より少数の物理的なビットで論理変数を表すことができます（ただし、異なるトポロジーではアニーリングの振舞いが多少変化することがあります）。キメラとペガサス トポロジーの詳細は [1] をご参照ください。
2.3 実装例
看護師スケジューリング問題の実装例は、GitHub で公開しています[3]。この実装には次のパラメータを採用しています。
| \(a\) | \(\lambda\) | \(\gamma\) | \(E(n)\) | \(W(d)\) | \(G(n,d)\) | \(F(n)\) |
|---|---|---|---|---|---|---|
| 3.5 | 1.3 | 0.3 | 1.0 | 1.0 | 1.0 | \(\lfloor D/N \rfloor\) |
各制約条件の重要度を考慮して、\(a、\lambda、\gamma\) を決めています。ハード シフト制約はハード看護師制約より重要度が高いため、最適解からの 1 変数のずれによるエネルギー ペナルティを後者よりも大きくします。同じく、ハード看護師制約のエネルギー ペナルティはソフト看護師制約を上回るように設定します。
D-Wave Leap アカウント (D-Wave 社の量子アニーリング サービスを利用するためのアカウント) をお持ちの方は GitHub リポジトリの URL の前に https://ide.dwavesys.io/# を追加することで D-Wave Leap の IDE でコードを実行することができます。Nurse Shift.py を実行すると上記ハミルトニアンの量子アニーリングが実行できます。実行する前に、パラメータの範囲を確認してください（特に、利用したいトポロジーの指定）。逆アニーリングをする場合は、Nurse Shift.py を実行した後、Reverse Nurse Shift.py を実行してください。Reverse Nurse Shift.py は、Nurse Shift.py から得られた最低エネルギーの解から出発し、より良い解を逆アニーリングで求めます。
3．おわりに
ここでは、看護師スケジュール問題の例を取り上げましたが、他にも多くの NP 困難問題に適用可能です。ジョブ ショップ スケジューリング [4] や様々なグラフ分割に適用されています [5]。実際の問題を解く際は、複数のパラメータを調整する必要がありますが、問題の特徴によっては、量子アニーリングは強力なアプローチになりえます。スケジュール問題などにお悩みの場合、量子アニーリングを試してみてはいかがでしょうか。
参考資料
- [1] D-Wave Technical Description - Background https://docs.dwavesys.com/docs/latest/c_qpu_0.html
- [2] Ikeda et al., “Application of Quantum Annealing to Nurse Scheduling Problem” Sci Rep 9, 12837 (2019). https://doi.org/10.1038/s41598-019-49172-3
- [3] GitHub/amorim-cjs https://github.com/amorim-cjs/quantum-annealing
- [4] Venturelli et al., “Quantum Annealing Implementation of Job-Shop Scheduling” arXiv:1506.08479
- [5] Ushijima-Mwesigwa et al., “Graph Partitioning using Quantum Annealing on the D-Wave System” arXiv:1705.03082
\(^1\)この文脈でのトポロジーとは、グラフやネットワークの形状を指しています。例えば、4 点を環状の四角につなげたグラフ、対角線も引いた四角でつなげたグラフ、1 点を中心にして星形につなげたグラフは、それぞれ異なるトポロジーをもちます。なお、すべての点がお互いにリンクしているグラフはクリーク (clique) と呼ばれます。
© Copyright 2020 株式会社知能情報システム