PyQUBOにおける3乗以上の項の扱い

　PyQUBOのドキュメント[1]には3乗以上の項の扱いがあまり詳しく書かれていなかったのでメモ書きしておきます。

　そもそもQUBOのQはQuadraticのQなのでコスト函数は2次形式でないといけないわけですが、現実問題として3乗以上の項が含まれたコスト函数を扱いたいときはあります。そういうときは変数の置き換えが必要になりますが、PyQUBOならそれは勝手にやってくれます。
　例えば一番シンプルな3次のコスト函数例として以下のコスト関数を考えてみます。

　もちろん、ここで\(x,y,z\)は \(0\) か \(1\) のみを取ります。
　これをPyQUBOに入れてQUBOを生成してみます。ここではとりあえず\(\alpha=7\)としてます。

#プレースホルダー
alpha = Placeholder("alpha")
#変数
x, y, z = Binary("x"), Binary("y"), Binary("z")
#コスト函数
H = alpha * x * y * z
#コンパイル
model = H.compile()
#QUBOを生成
QUBO, offset = model.to_qubo(feed_dict = {"alpha": 7})
#変数リスト
print(model.variables)
#QUBO
print(QUBO)

['x', 'y', 'z', '0*1']
{('x', 'x'): 0.0, ('y', 'y'): 0.0, ('z', 'z'): 0.0, ('y', '0*1'): -10.0, ('z', '0*1'): 7.0, ('0*1', '0*1'): 15.0, ('x', '0*1'): -10.0, ('x', 'y'): 5.0}

　ここでmodel.variablesの出力を見てみると、0*1というものが現れています。これは私たちが定義した変数ではなくて、PyQUBOが次数を下げるために自動的に生成した変数であり、\(xy\)を置き換えたものです。ここでは\(0*1=w=xy\)と書くことにします。QUBOの出力結果だけを見てもよくわからないですが、実はPyQUBOが出力したコスト函数は以下のようになっています。

　ここでPyQUBOが生成したコスト関数\(H_\mathrm{pyqubo}(x,y,z,w)\)は、新たな変数\(w=xy\)を使って次数を下げたことにより、2次式になっていることがわかります。つまり変数を追加することでQUBOを定義できるようになりました。
　この式の第一項は \(w=xy\)ですので、もとのコスト函数であることがわかります。
　次に第二項の \(S\)に比例する項が何かというと、 \(w=xy\)を成り立たせるための制約項になっています。第二項はこの等号が成り立つときに0になり、成り立たないときには正のペナルティを与えるようになっていることがわかります。そして \(S\)は8行目のcompile()の引数strengthです。いまはcompile()に引数を与えずに実行したので、この場合はデフォルト引数のstrength=5が入ります。

　つまりPyQUBOは3次以上のコスト函数を与えたとき、変数をうまく置き換えて2次式に変換し、後ろに置き換えた変数に矛盾が起こらないための制約項を追加してくれます、便利ですね。
　もともとのコスト函数には全体に \(\alpha\)がかかっていますが、PyQUBOが生成したQUBOはそうなっていないことに注意してください。

strengthの注意点

　以下のようなコスト関数考えてみます。

　これをPyQUBOで生成したQUBOを使ってコスト函数に戻すと以下のようになります。

　先程と同じように \(w:=xy\)を新たな変数として追加しています。 \(\alpha\)含みの項は明らかにもとのコスト函数部分で、 \(S\)含みの項は変数置き換えが矛盾しないように導入したペナルティで、先程と同じ表式になっています。
　ところでもともとのコスト函数の最小値は \(H(1,1,1)=-\alpha\) です。第一項を消えないようにするには \((x,y,z)=(1,1,1)\) しか許されず、この場合第二項が必ず残るからです。
　ところが、\(H_\mathrm{pyqubo}(x,y,z,w)\)では、第一項と第二項の第一項だけを生き残らせることができます。つまり

　となるときです。このとき\(S\)が小さければ元々の最小値\(-\alpha\)よりも小さい解が出てくる可能性があります。実際今考えてるコスト函数をそのままPyQUBOでQUBOを生成し計算すると、デフォルトの\(S\)は5なので、 \(\alpha\)が6以上だと誤った最小値を拾ってきます。もしくは\(\alpha=5\)だと、本来の最小値とコストは一致するが、変数を置き換えの制約を満たさないような組み合わせが出現します（ここら辺の数字の話は今回のコスト関数特有なので重要ではないですが、とにかく）。これを阻止するためには変数置き換えの制約を破ったときのペナルティ\(S\)つまり.compile(strength)のstrengthを十分大きくしましょうという話でした。

参考文献

本日の作業用BGM