はじめに
D-Wave Systemsの量子アニーラや東芝のシミュレーテッド分岐マシンに代表されるイジングマシンを使って、一般的な組み合わせ最適化を解く場合には、イジング問題（Quadratic Unconstrained Binary Optimization、QUBO）の形でコスト関数を設定しなければなりません。そのときに、元々の変数に加えて、新たに補助的な変数を導入する必要が出てきます。では、何個の補助変数を導入すれば良いでしょうか？結論をいうと、もとの変数の数に対して、指数関数的に多くの補助変数を導入しなければならないケースが存在することが分かっています。この記事では、指数関数的に多くの補助変数が必要になることを厳密に示します。
参考文献は以下の論文です。
- Martin Anthony, Endre Boros, Yves Crama, Quadratic reformulations of nonlinear binary optimization problems, Mathematical Programming 162, pages115–144(2017)
定義
ここでは数学的な定義を行っていきます。
定義1（pseudo-Boolean関数）
$n$個のbool値変数に対する実関数、つまり$\lbrace 0, 1\rbrace^n$から$\mathbb{R}$への写像のことをpseudo-Boolean関数と呼びます。
また$n$個の2値変数$x_1,\dots, x_n$に対する、pseudo-Boolean関数の集合を$F_n$で表します。$F_n$は実係数の線形空間になっていて、その次元は$2^n$です。このpseudo-Boolean関数の最小値を求める問題は、一般的な組み合わせ最適化問題を表していると考えることができます。
さらにpseudo-Boolean関数の中でも特殊なクラスの関数を考えます。
定義2（quadratic pseudo-Boolean関数）
pseudo-Boolean関数のうち、2次形式で表すことができる関数をquadratic pseudo-Boolean関数と呼びます。
quadratic pseudo-Boolean関数は常に$$g(x) = a + \sum_{i,j=1}^nb_{ij}x_ix_j$$のように表すことができます。ここでbool変数の$x_ix_i=x_i$という性質を使っています。$n$変数のquadratic pseudo-Boolean関数の集合を$Q_{n}$で表します。$Q_{n}$も実の線形空間になっていて、その次元$D_{n}$は$$D_{n}:=\sum_{i=0}^2 {}_{n}C_i = \frac{1}{2}(n^2+n+2)$$になります。quadratic pseudo-Boolean関数の最小値を求める問題は、Quadratic Unconstrained Binary Optimization（QUBO）、もしくはQuadratic pseudo-Boolean Optimization（QPBO）と呼ばれます。QUBOはイジングマシンが解くことのできる最適化問題の形式になっています。
定義3（pseudo-Boolean関数の2次形式化）
$f(x)$を$n$変数のpseudo-Boolean関数とします。このとき、$$f(x)=\min_{y\in\lbrace 0,1\rbrace^m}g(x,y) $$を満たすような、$n+m$変数のquadratic pseudo-Boolean関数$g(x,y)\in Q_{n+m}$が存在すると仮定します。このとき、関数$g(x,y)$を$f(x)$の**2次形式化（quadratic reformulation）**と呼び、追加で導入した変数$y$を補助変数（auxiliary variable）と呼びます。
ここでbool値の関数$h:\lbrace 0, 1\rbrace^n \to \lbrace 0, 1\rbrace^m$を、$$ h(x):=\mathrm{arg}\min_{y}g(x,y) $$で定めると、pseudo-Boolean関数の2次形式化は$$f(x)=g(x,h(x))$$と表すことができます。
定理
$F_n$の中でも、高々$m$個の補助変数$y_1,\dots, y_m$を導入することで2次形式化できる関数を考えます。そのような関数の集合を$V_{n,m}$で表すことにします。$V_{n,m}$は$F_n$の部分集合ですが、線形空間になっているとは限りません。定義から明らかなように$$ V_{n,1}\subseteq V_{n,2}\subseteq\cdots\subseteq F_n $$が成り立ちます。このとき我々が興味があるのは、$$V_{n,m}=F_n$$となるような最小の整数$m$の値です。そのような$m$のことを$\xi(n)$で表すことにします。つまり$\xi(n)$は、$n$変数のpseudo-Boolean関数を2次形式化するのに十分な補助変数の数の下限を表しています。このとき、次の不等式が成立します。
定理（補助変数の個数の下限）
任意の$n$について、以下の不等式が成立する。
$$\xi(n)\geq 2^{n/2}-n-1$$
この結果から分かることは、2次形式化をするために、少なくとも$\mathcal{O}(2^{n/2})$個の補助変数を導入しなければいけないpseudo-Boolean関数が存在するということです。このこと自体は、$F_n$の次元が$2^n$であることに対して、$Q_{n}$の次元は$\mathcal{O}(n^2)$であることから明らかだと思います。
そもそもQUBOを解く場合は、QUBOの変数の数に対して指数関数的に長い時間が必要になります。したがって、pseudo-Boolean関数の最適化をQUBOに変換して解いた場合には、元々の問題の変数の数に対して二重指数関数のオーダーの計算時間が必要となると推察されます。元々の問題は全探索で$2^n$の時間で最適解が分かるので、それにくらべ悪くなる可能性があるということです。
証明
では、定理の証明を行っていきます。
任意の$f\in V_{n,m}$を1つ固定します。すると、ある$g\in Q_{n+m}$が存在して、$f(x)=\min_{y\in\lbrace 0,1\rbrace^m}g(x,y)$と表すことができます。ここで$g$は二次形式なので、
$$ g(x,y) = a + \sum_{i,j=1}^nb_{ij}x_ix_j + \sum_{i=1}^n \sum_{r=1}^mc_{ij}x_iy_r + \sum_{r,s=1}^md_{rs}y_ry_s $$と書けます。したがって、bool値の関数$h:\lbrace 0, 1\rbrace^n \to \lbrace 0, 1\rbrace^m$を$ h(x):=\mathrm{arg}\min_{y}g(x,y) $とすれば、
$$ f(x)= a + \sum_{i,j=1}^nb_{ij}x_ix_j + \sum_{i=1}^n \sum_{r=1}^mc_{ij}x_ih_r(x) + \sum_{r,s=1}^md_{rs}h_r(x)h_s(x) $$となります。つまり$f$は、$\lbrace 0, 1\rbrace^n$上のbool値の関数の集合$$L_h:=\lbrace 1,\ x_ix_j,\ x_ih_r(x),\ h_r(x)h_s(x)\rbrace_{1\leq i,j\leq n,\ 1\leq r,s \leq m}$$の要素の線形結合として表されています。ここで要素の個数を考えると、$|L_h|\leq D_{n+m}$が成り立ちます。
次に、$L_h$で張られる線形空間を$\mathrm{sp}(L_h)$で表すことにします。$L_h$が$f$の選択に依存していることに注意すると、$$V_{n,m}\subseteq \bigcup_h \mathrm{sp}(L_h)$$が成り立つことが分かります。よって$V_{n,m}=F_n$が成立しているときには、$$ F_n\subseteq \bigcup_h \mathrm{sp}(L_h) $$が成り立ちます。$\mathrm{sp}(L_h)$は$F_n$の部分空間であるから、$$V_{n,m}=\bigcup_h \mathrm{sp}(L_h)$$となります。両者の次元を考えると、$$ 2^n=\max_h |L_h|\leq D_{n+m}\leq (n+m+1)^2$$という不等式が得られます。これを変形すると、$$m\geq 2^{n/2}-n-1$$となります。$\blacksquare$
むすび
$\xi(n)$の正確な値は分かっておらず、未解決問題になっています。そこまで難しい問題ではないので、数学に強い人であれば求めることができると思います。ぜひトライしてみてください。