1"""This module contains the EC class."""
2
3import ast
4from collections import defaultdict
5from typing import Literal
6
7import matplotlib.pyplot as plt
8import networkx as nx
9import numpy as np
10from qiskit.quantum_info import SparsePauliOp
11
12from qlauncher import hampy, models
13from qlauncher.base import Problem
14
15
[docs]
16class EC(Problem):
17 """
18 Class for exact cover problem.
19
20 The exact cover problem is a combinatorial optimization problem that involves finding a subset of a given set
21 of elements such that the subset covers all elements and the number of elements in the subset is minimized.
22 The class contains an instance of the problem, so it can be passed into QLauncher.
23
24 Attributes:
25
26 onehot (str): The one-hot encoding used for the problem.
27 instance (any): The instance of the problem.
28 instance_name (str | None): The name of the instance.
29 instance_path (str): The path to the instance file.
30
31 """
32
33 def __init__(self, instance: list[set[int]], instance_name: str = 'unnamed') -> None:
34 super().__init__(instance=instance, instance_name=instance_name)
35
[docs]
36 @staticmethod
37 def from_preset(instance_name: Literal['micro', 'default'], **kwargs) -> 'EC':
38 match instance_name:
39 case 'micro':
40 instance = [{1, 2}, {1}]
41 case 'default':
42 instance = [{1, 4, 7}, {1, 4}, {4, 5, 7}, {3, 5, 6}, {2, 3, 6, 7}, {2, 7}]
43 case _:
44 raise TypeError
45 return EC(instance=instance, instance_name=instance_name, **kwargs)
46
[docs]
47 @classmethod
48 def from_file(cls, path: str, **kwargs) -> 'EC':
49 with open(path, encoding='utf-8') as file:
50 read_file = file.read()
51 instance = ast.literal_eval(read_file)
52 return EC(instance, **kwargs)
53
[docs]
54 def visualize(self, marked: str | None = None) -> None:
55 G = nx.Graph()
56 size = len(self.instance)
57 ec = [set(map(str, x)) for x in self.instance]
58 names = set.union(*ec)
59 for i in range(len(ec)):
60 G.add_node(i)
61 for i in sorted(names):
62 G.add_node(i)
63 covered = defaultdict(int)
64 for node, edges in enumerate(ec):
65 for goal_node in edges:
66 G.add_edge(node, goal_node)
67
68 edge_colors = []
69 for goal_node in G.edges():
70 node, str_node = goal_node
71 if marked is None:
72 edge_colors.append('black')
73 continue
74 if marked[node] == '1':
75 edge_colors.append('red')
76 covered[str_node] += 1
77 else:
78 edge_colors.append('gray')
79 color_map = []
80 for node in G:
81 if isinstance(node, int):
82 color_map.append('lightblue')
83 elif covered[node] == 0:
84 color_map.append('yellow')
85 elif covered[node] == 1:
86 color_map.append('lightgreen')
87 else:
88 color_map.append('red')
89 pos = nx.bipartite_layout(G, nodes=range(size))
90 nx.draw(G, pos, node_color=color_map, with_labels=True, edge_color=edge_colors)
91 plt.title('Exact Cover Problem Visualization')
92 plt.show()
93
[docs]
94 @staticmethod
95 def generate_ec_instance(n: int, m: int, p: float = 0.5, **kwargs) -> 'EC':
96 graph = nx.bipartite.random_graph(n, m, p)
97 right_nodes = [n for n, d in graph.nodes(data=True) if d['bipartite'] == 0]
98 instance = [set() for _ in right_nodes]
99 for left, right in graph.edges():
100 instance[left].add(right)
101 return EC(instance=instance, **kwargs)
102
[docs]
103 def to_hamiltonian(self, onehot: Literal['exact', 'quadratic'] = 'exact') -> models.Hamiltonian:
104 onehots = []
105 for ele in set().union(*self.instance):
106 ohs = set()
107 for i, subset in enumerate(self.instance):
108 if ele in subset:
109 ohs.add(i)
110 onehots.append(ohs)
111
112 equation = hampy.Equation(len(self.instance))
113
114 for ohs in onehots:
115 if onehot == 'exact':
116 part = ~hampy.one_in_n(list(ohs), len(self.instance))
117 elif onehot == 'quadratic':
118 part = hampy.one_in_n(list(ohs), len(self.instance), quadratic=True)
119 equation += part
120
121 return models.Hamiltonian(
122 equation,
123 mixer_hamiltonian=self.get_mixer_hamiltonian(),
124 )
125
[docs]
126 def get_mixer_hamiltonian(self, amount_of_rings: int | None = None) -> hampy.Equation:
127 """generates mixer hamiltonian"""
128
129 # looking for all rings in a data and creating a list with them
130 ring, x_gate = [], []
131 main_set = []
132 for element_set in self.instance:
133 for elem in element_set:
134 if elem not in main_set:
135 main_set.append(elem)
136 constraints = []
137 for element in main_set:
138 element_set = set()
139 for index, _ in enumerate(self.instance):
140 if element in self.instance[index]:
141 element_set.add(index)
142 if len(element_set) > 0 and element_set not in constraints:
143 constraints.append(element_set)
144
145 ring.append(max(constraints, key=len))
146
147 ring_qubits = set.union(*ring)
148
149 for set_ in constraints:
150 if len(set_.intersection(ring_qubits)) == 0:
151 ring.append(set_)
152 ring_qubits.update(set_)
153
154 if amount_of_rings is not None:
155 max_amount_of_rings, user_rings = len(ring), []
156 if amount_of_rings > max_amount_of_rings:
157 raise ValueError(f'Too many rings. Maximum amount is {max_amount_of_rings}')
158 if amount_of_rings == 0:
159 ring_qubits = []
160 else:
161 current_qubits = ring[0]
162 for index in range(amount_of_rings):
163 user_rings.append(ring[index])
164 current_qubits = current_qubits.union(ring[index])
165 ring_qubits = current_qubits
166 x_gate.extend(id for id, _ in enumerate(self.instance) if id not in ring_qubits)
167
168 # connecting all parts of mixer hamiltonian together
169 mix_ham = hampy.Equation(len(self.instance))
170 for set_ in ring:
171 mix_ham += ring_ham(set_, len(self.instance))
172
173 x_gate_ham = hampy.Equation(len(self.instance))
174 # creating mixer hamiltonians for all qubits that aren't in rings (in other words applying X gate to them)
175 for elem in x_gate:
176 x_gate_ham += SparsePauliOp.from_sparse_list([('X', [elem], 1)], len(self.instance))
177
178 return mix_ham + x_gate_ham
179
[docs]
180 def to_qubo(self) -> models.QUBO:
181 n = len(self.instance)
182 # Calculate length tabs
183 len_routes = []
184 for route in self.instance:
185 len_routes.append(len(route))
186
187 qubo = np.zeros((n, n))
188
189 Jrr_dict = {}
190 indices = np.triu_indices(n, 1)
191 for i1, i2 in zip(indices[0], indices[1], strict=False):
192 Jrr_dict[(i1, i2)] = len(set(self.instance[i1]).intersection(set(self.instance[i2]))) / 2
193
194 hr_dict = {}
195 for i in range(n):
196 i_sum = sum(len(set(r).intersection(set(self.instance[i]))) for r in self.instance)
197
198 hr_dict[i] = (i_sum - len(self.instance[i]) * 2) / 2
199
200 # Space
201 for key, value in Jrr_dict.items():
202 qubo[key[0]][key[1]] = value
203 qubo[key[1]][key[0]] = qubo[key[0]][key[1]]
204
205 for i in hr_dict:
206 qubo[i][i] = -hr_dict[i]
207
208 return models.QUBO(qubo, 0)
209
210
[docs]
211def ring_ham(set_ring: set[int], n: int) -> hampy.Equation:
212 total = hampy.Equation(n)
213 ring = list(set_ring)
214 for index in range(len(ring) - 1):
215 total += SparsePauliOp.from_sparse_list(
216 [
217 ('XX', [ring[index], ring[index + 1]], 1),
218 ('YY', [ring[index], ring[index + 1]], 1),
219 ],
220 n,
221 )
222 total += SparsePauliOp.from_sparse_list(
223 [
224 ('XX', [ring[-1], ring[0]], 1),
225 ('YY', [ring[-1], ring[0]], 1),
226 ],
227 n,
228 )
229 return total
