<jupyter_start><jupyter_text>クリーク問題クリーク問題は、グラフ理論において、グラフ中のクリーク（任意の二頂点間に枝があるような頂点集合）を見つける問題。下記はグラフ中にKのクリークが存在するかどうかをみつけるコスト関数です。1項目は頂点数をKに制約する条件。2項目のBで囲まれた部分は選んだ頂点が完全グラフを構成している場合にコストがもっとも小さくなるようなエッジの数の条件です。クリーク数がKのものが存在する場合、コスト関数E=0となります。 例題下記のように6つのノードのネットワーク構造からクリーク数3を探します。<jupyter_code>import networkx as nx
import matplotlib.pyplot as plt

options = {'node_color': '#efefef','node_size': 1200,'with_labels':'True'}

G = nx.Graph()
G.add_nodes_from(nx.path_graph(6))
G.add_edges_from([(0,1),(0,4),(1,2),(1,4),(2,3),(3,4),(3,5)])
nx.draw(G, **options)<jupyter_output><empty_output><jupyter_text>今回はノード数が6なので、6量子ビット用意します。次に今回はクリーク数3ということで、上記の式のK=3とします。今回も少し工夫してみます。上記の式は、1項目と2項目を別々に構築して足し合わせてみます。1項目の方は9-6A+A^2という形に変形できますので、Wildqatの機能をうまく使って行列計算で処理できます。定数項は無視します。また、2項目は手作業で作ってしまいます。まずWildqatをインストールして準備します。また、numpyを使いますので、それも準備しておきます。<jupyter_code>!pip install -U wildqat
import wildqat as wq
import numpy as np
a = wq.opt()<jupyter_output><empty_output><jupyter_text>次にx0+x1+x2+x3+x4+x5の係数を見ると全て1なので、これを対角行列で用意します。<jupyter_code>A = [1,1,1,1,1,1]
print(np.diag(A))<jupyter_output>[[1 0 0 0 0 0]
 [0 1 0 0 0 0]
 [0 0 1 0 0 0]
 [0 0 0 1 0 0]
 [0 0 0 0 1 0]
 [0 0 0 0 0 1]]<jupyter_text>そしてこのAを使って、1項目の-6A+A^2を簡単に計算してみます。Wildqatの機能を使います。<jupyter_code>print(wq.sqr(A))<jupyter_output>[[1 2 2 2 2 2]
 [0 1 2 2 2 2]
 [0 0 1 2 2 2]
 [0 0 0 1 2 2]
 [0 0 0 0 1 2]
 [0 0 0 0 0 1]]<jupyter_text>これらを足し合わせると最初の項になります。<jupyter_code>matrix1 = -6*np.diag(A)+wq.sqr(A)
print(matrix1)<jupyter_output>[[-5  2  2  2  2  2]
 [ 0 -5  2  2  2  2]
 [ 0  0 -5  2  2  2]
 [ 0  0  0 -5  2  2]
 [ 0  0  0  0 -5  2]
 [ 0  0  0  0  0 -5]]<jupyter_text>次に2項目を手入力します。Bは0.8でやってみます。<jupyter_code>B = 0.8
matrix2 = B*np.asarray([[0,-1,0,0,-1,0],[0,0,-1,0,-1,0],[0,0,0,-1,0,0],[0,0,0,0,-1,-1],[0,0,0,0,0,0],[0,0,0,0,0,0]])
print(matrix2)<jupyter_output>[[ 0.  -0.8  0.   0.  -0.8  0. ]
 [ 0.   0.  -0.8  0.  -0.8  0. ]
 [ 0.   0.   0.  -0.8  0.   0. ]
 [ 0.   0.   0.   0.  -0.8 -0.8]
 [ 0.   0.   0.   0.   0.   0. ]
 [ 0.   0.   0.   0.   0.   0. ]]<jupyter_text>最後にこれらを足し合わせて計算をします。<jupyter_code>a.qubo = matrix1 + matrix2
print(a.qubo)
a.sa()<jupyter_output>[[-5.   1.2  2.   2.   1.2  2. ]
 [ 0.  -5.   1.2  2.   1.2  2. ]
 [ 0.   0.  -5.   1.2  2.   2. ]
 [ 0.   0.   0.  -5.   1.2  1.2]
 [ 0.   0.   0.   0.  -5.   2. ]
 [ 0.   0.   0.   0.   0.  -5. ]]
1.4822120666503906<jupyter_text>上記で実際に生成されたQUBO、実行時間、最終的な解が得られました。上記からの1番目、2番目、5番目の量子ビットが1ですので、クリーク数3は上記量子ビット間にあるということがQUBOで導きだせました。念のため最終的に生成されたイジングマトリックスを確認するには、<jupyter_code>print(a.J)<jupyter_output>[[-0.4  0.3  0.5  0.5  0.3  0.5]
 [ 0.  -0.6  0.3  0.5  0.3  0.5]
 [ 0.   0.  -0.4  0.3  0.5  0.5]
 [ 0.   0.   0.  -0.6  0.3  0.3]
 [ 0.   0.   0.   0.  -0.6  0.5]
 [ 0.   0.   0.   0.   0.  -0.2]]<jupyter_text>コスト関数の変遷も見てみます。<jupyter_code>a.plot()<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.18612099644128113, 'fraction_numerical': 0.13238434163701068, 'mean_word_length': 3.311349693251534, 'pattern_counts': {'":': 0, '<': 31, '<?xml version=': 0, '>': 31, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '9', 'dir': 'jupyter-structured-clean-dedup', 'id': '116528', 'license': 'Apache-2.0', 'n_tokens_mistral': 2090, 'n_tokens_neox': 1912, 'n_words': 257, 'path': 'examples_ja/tutorial006_cliques.ipynb', 'repo_name': 'mori388/annealing', 'size': '2810'}