← Materiały bloku: Kwantowe wyżarzanie kombinatorycznych problemów optymalizacyjnych  ·  podgląd notatnika rozwiazania_wybranych_zadan_dodatkowych.ipynb  ·  pobierz plik .ipynb

Problem podziału grafu

$$ H = H_{rowne} + H_{min} $$

$$ H_{rowne} = \left( \sum_{i = 1}^N s_i \right)^{2} $$

$$ H_{min} = \sum_{(u,v) \in E} (1 - s_u s_v) $$ $h = 0$ i $J = 2$ na krawedziach które nie istnieja i 1 na krawedziach ktore istnieja

import networkx as nx
from dimod import BinaryQuadraticModel, ExactSolver
from pyqubo import Array

brute_force = ExactSolver()

graph = nx.erdos_renyi_graph(n=6, p=0.3, seed=2137)

# tworzymy model
spins = Array.create("spins", shape=graph.number_of_nodes(), vartype="SPIN")

H1 = sum([s for s in spins])**2 
H2 = sum([1 - spins[i]*spins[j] for i,j in graph.edges()])
H = sum([H1, H2])

model = H.compile()

linear, quadratic, offset = model.to_ising()

#rozwiązujemy problem
bqm = BinaryQuadraticModel(linear, quadratic, offset, vartype="SPIN")
sampleset = brute_force.sample(bqm)
print(sampleset.lowest(0))

Problem pełnego pokrycia

$$ H = \sum_{\alpha = 1}^n \left( 1 - \sum_{i: \alpha \in V_i} x_i \right)^2 $$ $-n$ na przekątnhych i $2 \times$ moc przekroju na pozostałych elementach

import numpy as np
from dimod import BinaryQuadraticModel, ExactSolver
from pyqubo import Array


brute_force = ExactSolver()
rng = np.random.default_rng(seed=42)

def random_subset(s):
    return {x for x in s if rng.choice((True, False))}


n = 4
N = 5

U = set(range(1, n+1))
R = [random_subset(U) for i in range(N)]

x = Array.create("x", shape=N, vartype="BINARY")
H = sum([(1 - sum([x[i] if a in R[i] else 0 for i in range(N)]))**2 for a in U])
model = H.compile()
qubo, offset = model.to_qubo()

bqm = BinaryQuadraticModel(qubo, offset=offset, vartype="BINARY")
sampleset = brute_force.sample(bqm)

print(sampleset.lowest(0))