Table of contents
Quantum annealing for you 02
実際の問題を解いてみる
荷物分割問題
AさんとBさんに\(w_1, w_2, \dots, w_N\)までの荷物を、重さが等しくなるように渡す問題を考えます。\(W_A\)をAさんに渡した荷物の重さの合計、\(W_B\)をBさんに渡した荷物の重さの合計とすると、コスト関数\(E(\mathbf{x})\)は
\[E(\mathbf{x}) = (w_A - w_B)^2\]ここで\(W = \sum_{i=1}^N w_i = W_A + W_B\)より
\[E(\mathbf{x}) = (W_A - W_B)^2 = (2 W_A - W)^2\]Aさんに\(i\)番目の荷物を渡すとき1, Bさんに\(i\)番目の荷物を渡すとき0となるようなバイナリ変数を\(x_i\)とすると
\[W_A = \sum_{i=1}^N w_i x_i\]より
\[E(\mathbf{x}) = (2 \sum_{i=1}^N w_i x_i - W) (2 \sum_{j=1}^N w_j x_j - W) = 4 \sum_{i=1}^N \sum_{j=1}^N w_i w_j x_i x_j - 4 W \sum_{i=1}^N w_i x_i + W^2\]\(\{ 0, 1\}\)バイナリ変数では\(x_i = x_i x_i\)となるので、最終的なコスト関数は
\[E(\mathbf{x}) = 4 \sum_{i=1}^N \sum_{j=1}^N w_i w_j x_i x_j - 4 W \sum_{i=1}^N w_i x_i x_i + W^2\]ゴルフカップ型(1つだけ最適解、他はエネルギーが高いようなエネルギーランドスケープ)の問題は量子アニーリングでも間違う。量子回路でGrover探索したとしても、指数時間かかる。
オプション
sampleset = sampler.sample_qubo(Q, num_reads=10, postprocess='optimization')
postprocessにoptimizataionを指定することで、アニーリング途中で計算が打ち切られてしまう(坂道を下っている途中で突然終了してしまう)ような場合でも、後処理によってアニーリングを仕切ったようにエネルギーの低い解が見つかることがあります。
samplingを指定すると、結果を補正してギブス・ボルツマン分布に従うような答えに近づけるようにすることもできます。ボルツマンマシン機械学習などで使用すると良いでしょう。
Advantageにはpostprocessオプションがなくなりました。
annealing_timeの引数に数値を指定することで、マイクロ秒単位でアニーリング時間を設定することができます。
機械学習・深層学習のEarly Stopping(過学習になる前に打ち切る計算)に相当する話としてanneal_scheduleを設定することもできます。横磁場を急激に弱めたりといった設定も可能です。リバースアニーリング(最初に解を指定し、そこから横磁場をかけて重ね合わせを作り、最後に横磁場を再び0にする)ということも可能です。anneal_scheduleにはinitial_stateを指定することで、探索の初期値を設定することもできます。
PyQUBO
PyQUBOで\(x\)の3乗などを使うと、実は内部で2次関数に変換してくれます。
制約が満たされているかどうかはsample.constraints(only_broken=True)で見ることができます。
制約の破れ
制約を満たすためには制約の前の係数が大きくないといけません。しかし、大きすぎると「制約は満たすけれども最適解から遠い」解が見つかる可能性が高くなります。物理的には状態間のエネルギー障壁が大きくなるため、山を越えにくく(トンネル効果で状態遷移しにくく)なります。
未定乗数を機械学習でハイパーパラメータ探索することや、ベイズ推定で効率良く探索するアルゴリズムなどもあります。自動調整するようなライブラリ(e.g., hyperopt)などがあります。
どんな問題を量子アニーリングで解くべきか？
難しい問題とは…NP困難などのものではなく、フラストレーションを起こしているかどうか。\(\sum_{i,j } Q_{ij} x_i x_j\)の\(x_i\)と\(x_j\)が影響を及ぼし合っている問題が難しい。