最初にExact Cover問題について説明します。

ある自然数の集合Uを考えます。またその自然数を含むいくつかのグループ$V_{1}, V_{2}, \ldots, V_{N}$を想定します。１つの自然数が複数のグループに属していても構いません。さて、そのグループ$V_{i}$からいくつかピックアップしたときに、それらに同じ自然数が複数回含まれず、Uに含まれる自然数セットと同じになるようにピックアップする問題をExact Cover問題といいます。 さらに、選んだグループ数を最小になるようにするものを、Smallest Exact Coverといいます。

解きたい問題のQUBOマトリクスを作成します。

最初に自然数の集合を $U = \{1, \ldots, n\}$、グループを$V_{i} \subseteq U(i=1, \ldots, N)$とします。また、i番目のグループをピックアップしたかどうかを$x_{i} \in \{1, 0\}$で表します。ピックアップされた場合は1、されなかった場合は0です。ここで、各自然数（αとします）についてピックアップされた1つのグループのみに含まれている場合に最小となるようなコスト関数$E_{A}$を考えます。

この場合、

$E_{A} = A \sum _ { \alpha = 1 } ^ { n } \left( 1 - \sum _ { i : \alpha \in V _ { i } } x _ { i } \right) ^ { 2 }$

とすると、各自然数αに対して1つのグループのみがピックアップされた場合、$E_{A} = 0$となります。

これをQUBO形式に変換していきます。まず括弧の中を展開します。

$E_{A} = A \sum _ { \alpha = 1 } ^ { n } \{ 1 - 2\sum _ { i : \alpha \in V _ { i } } x _ { i } + ( \sum _ { i : \alpha \in V _ { i } } x _ { i } ) ^ { 2 } \}$

今回$E_{A}$を最小化する問題なので、定数である{}内の第一項は無視できます。 第二項は、$x_{i} \in {1,0}$であることを利用して、次のように書き換えることができます。

$- 2\sum _ { i : \alpha \in V _ { i } } x _ { i } = - 2\sum _ { i = j, i : \alpha \in V _ { i }, j : \alpha \in V _ { j } } x _ { i } x _ {j}$

第三項についても、i = jの場合と、$i \neq j$の場合に分けると、次の様に書き換えられます。

$( \sum _ { i : \alpha \in V _ { i } } x _ { i } ) ^ { 2 } = \sum _ { i = j, i : \alpha \in V _ { i }, j : \alpha \in V _ { j } } x _ { i } x _ {j} + 2 \sum _ { i \neq j, i : \alpha \in V _ { i }, j : \alpha \in V _ { j } } x _ { i } x _ {j}$

まとめると、

$E_{A} = A \sum _ { \alpha = 1 } ^ { n } ( - \sum _ { i = j, i : \alpha \in V _ { i }, j : \alpha \in V _ { j } } x _ { i } x _ {j} + 2 \sum _ { i \neq j, i : \alpha \in V _ { i }, j : \alpha \in V _ { j } } x _ { i } x _ {j} )$

となり、QUBO形式にすることができました。

また、結果を表示する関数を定義しておきます。

次の通り実行してみると、正しい答えが得られていることが分かります。

Vをもう少し複雑にして（2つグループを追加して）、実行してみます。

正しい答えが得られていることが分かります。

最後に意地悪なケースを試します。 {1,2}{3}{4}{5}{6}{7}{8}{9}{10}が選ばれるのが正解です。

結果を見ると、概ね正しい答えが選ばれるようですが、まれに少しエネルギーの高い不正解の方が選ばれてしまいます。