Exact Cover問題

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

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

準備

%matplotlib inline

import numpy as np
import matplotlib.pyplot as plt
import blueqat.wq as wq
from blueqat import vqe

QUBOの作成

解きたい問題の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形式にすることができました。

U = [1,2,3,4,5,6,7,8,9,10]
A = 1

def get_qubo(V):
    Q = np.zeros( (len(V), len(V)) )

    for i in range(len(V)):
        for j in range(len(V)):
            for k in range(len(U)):
                alpha = U[k]
                in_Vi = V[i].count(alpha) > 0 #V[i]に存在しているか
                in_Vj = V[j].count(alpha) > 0 #V[j]に存在しているか
                if i == j and in_Vi:
                    Q[i][j] += -1
                elif i < j and in_Vi and in_Vj:
                    Q[i][j] += 2

    return Q * A

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

def display_answer(list_x, energies = None, show_graph = False):
    print("Result x:", list_x)
    text = ""
    for i in range(len(list_x)):
        if(list_x[i]):
            text += str(V[i])
    print("Picked {} group(s): {}".format(sum(list_x), text))
    if energies is not None:
        print("Energy:", a.E[-1])
    if show_graph:
        plt.plot(a.E)
        plt.show()

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

V = [ [1,2], [3,4,5,6], [7,8,9,10], [1,3,5], [10] ]
qubo = get_qubo(V)
result = vqe.Vqe(vqe.QaoaAnsatz(wq.pauli(qubo), step=4)).run()
answer = result.most_common(12)
print(answer)
display_answer(answer[0][0])

(((1, 1, 1, 0, 0), 0.3783998933018464), ((0, 0, 1, 1, 0), 0.19080753539598078), ((1, 0, 1, 1, 0), 0.10904143237775482), ((1, 1, 1, 0, 1), 0.0890989364939838), ((0, 0, 1, 1, 1), 0.0449279949063271), ((0, 1, 1, 1, 0), 0.030382807525070173), ((1, 1, 0, 0, 1), 0.028032010700668703), ((1, 0, 1, 1, 1), 0.025675154329096672), ((0, 0, 1, 0, 0), 0.022072489455340405), ((1, 0, 1, 0, 0), 0.014930464403380785), ((0, 0, 0, 1, 1), 0.014135096147402253), ((1, 1, 1, 1, 0), 0.0095426809095386))
Result x: (1, 1, 1, 0, 0)
Picked 3 group(s): [1, 2][3, 4, 5, 6][7, 8, 9, 10]

Vをもう少し複雑にしてみる

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

V = [ [1,2], [3,4,5,6], [7,8,9,10], [1,3,5], [10], [7,9], [2,4,6,8] ]
qubo = get_qubo(V)
result = vqe.Vqe(vqe.QaoaAnsatz(wq.pauli(qubo), step=2)).run()
answer = result.most_common(12)
print(answer)
display_answer(answer[0][0])

(((1, 1, 1, 0, 0, 0, 0), 0.0700844494957699), ((0, 0, 0, 1, 1, 1, 1), 0.0700844494957699), ((1, 1, 0, 0, 1, 1, 0), 0.0695151945834572), ((0, 0, 1, 1, 0, 0, 1), 0.0695151945834572), ((1, 1, 0, 0, 0, 0, 0), 0.03942041130713249), ((0, 0, 1, 1, 1, 1, 1), 0.03942041130713249), ((1, 0, 0, 0, 1, 1, 0), 0.031317165076161634), ((0, 1, 1, 1, 0, 0, 1), 0.031317165076161634), ((1, 1, 1, 0, 1, 0, 0), 0.02802224137437182), ((0, 0, 0, 1, 0, 1, 1), 0.02802224137437182), ((1, 0, 1, 0, 0, 0, 0), 0.02728514456746815), ((0, 1, 0, 1, 1, 1, 1), 0.02728514456746815))
Result x: (1, 1, 1, 0, 0, 0, 0)
Picked 3 group(s): [1, 2][3, 4, 5, 6][7, 8, 9, 10]

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

意地悪ケース

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

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

V = [ [1,2], [3], [4], [5], [6], [7], [8], [9], [10], [2,3,4,5,6,7,8,9,10]]
for i in range(5):
    print("---{}回目".format(i+1))
    qubo = get_qubo(V)
    result = vqe.Vqe(vqe.QaoaAnsatz(wq.pauli(qubo), step=6)).run()
    answer = result.most_common(12)
    display_answer(answer[0][0])

---1回目
Result x: (1, 1, 1, 1, 1, 1, 1, 1, 1, 0)
Picked 9 group(s): [1, 2][3][4][5][6][7][8][9][10]
---2回目
Result x: (1, 1, 1, 1, 1, 1, 1, 1, 1, 0)
Picked 9 group(s): [1, 2][3][4][5][6][7][8][9][10]
---3回目
Result x: (1, 0, 0, 0, 0, 0, 0, 0, 0, 1)
Picked 2 group(s): [1, 2][2, 3, 4, 5, 6, 7, 8, 9, 10]
---4回目
Result x: (1, 1, 1, 1, 1, 1, 1, 1, 1, 0)
Picked 9 group(s): [1, 2][3][4][5][6][7][8][9][10]
---5回目
Result x: (1, 0, 0, 0, 0, 0, 0, 0, 0, 1)
Picked 2 group(s): [1, 2][2, 3, 4, 5, 6, 7, 8, 9, 10]

QAOAでエグザクトカバー

Yuichiro Minato

Exact Cover問題

準備

QUBOの作成

Vをもう少し複雑にしてみる

意地悪ケース