1. 본 기사의 개요

NP 다양한 문제에 대해 Ising에서 공식화한 논문 arxiv1302.5843이 있습니다.
D-wave의 공부가 있으면, 그것을 구현해 보자고 하는 것.

2. 본 기사의 가정 독자

최적화를 어쩐지 알고 있습니다

리굴은 좋기 때문에 사용할 수 있으면 좋다

파이썬 어쩐지 이해

레벨의 사람

3. 대상 문제

「2.2. Graph Partitioning」을 대상으로 한다.

정점의 수 $N=|V|$가 짝수인 무향 그래프 $ G=(V,E) $ 에 있어서, 정점수가 동수의 $N/2$ 가 되도록 그래프를 분할했을 때에, 엣지수 (변)이 최소가 되는 분할 방법은?

4. Ising 공식

논문을 보면 두 부분으로 나누어져 있네요. 정점이 동수가 되는 것 같은 제한 사항 $H_A$ 와 변의 Cut 방법 $H_B$ 로 되는 것 같습니다.
즉,
$$ H_A = A(\sum_{n=1}^N s_i)^2 $$$

$$ H_B = B(\sum_{(uv)\in E}\frac{1-s_us_v}{2}) 　$$

그렇습니다. (Qiita는 깨끗한 수식을 쓸 수 있기 때문에 기분이군요!)

글쎄, 그건 말하지 않고 구현으로 넘어 갑시다. (정말, Pyqubo 초절 편리합니다.라고 할까 나, Pyqubo 없어서는 아무것도 할 수 없습니다만, 좋은 것인가!?)

문제 생성

%matplotlib inline
import matplotlib.pyplot as plt
import networkx as nx
import numpy as np
import random
from pyqubo import Placeholder,Array,Constraint,Sum,solve_qubo

SIZE = 8
G = nx.Graph()

#サイズ分のVertixを作成し、適当にEdgeをつなぐ
for i in range(SIZE):
    G.add_node(i)
    if i != 0:
        for j in range(random.randint(1,6)):
            New_line = random.randint(0,i-1)
            if (G.get_edge_data(i,New_line) == None):
                G.add_edge(i,New_line,W=1)

#グラフの出来具合を確認する
pos = nx.spring_layout(G, k=5.,seed=0)
nx.draw_networkx(G,pos)
plt.rcParams['figure.figsize'] = (7.0, 7.0)
plt.show()

이번에 생성된 문제는 다음과 같다.



SA에서 솔루션 확인

#ハミルトニアンを構成
A = Placeholder("A")
B = Placeholder("B")

x = Array.create('x',SIZE,'SPIN')

H_A = Constraint(Sum(0,SIZE, lambda i:x[i])**2,label="H_A")

H_B = 0.0
for i in range(SIZE):
    for j in range(SIZE):
        if (G.get_edge_data(i,j) != None):
            H_B = H_B + (1.0 - x[i] * x[j]) / 2.0

H = A * H_A + B * H_B


# モデルをコンパイル
model = H.compile()
# QUBOを作成
feed_dict = {'A': 0.2,'B':0.1}
qubo, offset = model.to_qubo(feed_dict=feed_dict)

#PyquboのSAで解いてみる
sol = solve_qubo(qubo)
#結果表示
pos = nx.spring_layout(G, k=5.,seed=0)
nx.draw_networkx(G,pos,node_color=list(sol.values()))
plt.rcParams['figure.figsize'] = (7.0, 7.0)
plt.show()

그런 다음 D-wave로 시도합니다.

D-WAVE에서 실행

from dwave.system.samplers import DWaveSampler
from dwave.system.composites import EmbeddingComposite
import dimod

sampler = EmbeddingComposite(DWaveSampler(solver='DW_2000Q_VFYC_5'))
response = sampler.sample_qubo(qubo, num_reads=100)

result = []
result = model.decode_dimod_response(response,feed_dict=feed_dict)

pos = nx.spring_layout(G, k=5.,seed=0)
nx.draw_networkx(G,pos,node_color=list(result[0][0]['x'].values()))
plt.rcParams['figure.figsize'] = (7.0, 7.0)
plt.show()

오, 좋은 느낌의 대답이 나왔습니다!

죄송합니다.