-
Notifications
You must be signed in to change notification settings - Fork 0
/
Graph_and_vector_space.py
178 lines (149 loc) · 7.82 KB
/
Graph_and_vector_space.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
import random,copy,math
import numpy as np
import settings
import quantum_routines
import scipy.integrate
from scipy.optimize import minimize
import scipy
import igraph
from scipy.sparse import csr_matrix
class Graph:
"""
Graph used for QAOA,either for MIS or for MaxCut
Attributes : None, random generation of a graph with the parameters specified by seetings.
Use igraph to create your own instance of a particular graph.
"""
def __init__(self):
#plap
self.typegraph=settings.type_graph #Type of the graph
self.Nvertices=settings.N #Number of vertices
edges=[] #List of all the connecting edges under the form [[a,b],[c,d],...] if the vertices a and b (c and d) are connected.
weights=[] #Weight of all of the edges in the tab edges
tab_individual_links=[] #At position m, one will find the list of vertices connected to vertex m.
for m in range(self.Nvertices): #Initialisation
tab_individual_links.append([])
if self.typegraph=="Unit Disk":
#The positions of the vertices of the graph are chosen at random in [0,1]*[0,1]
#If the distance between two vertices is smaller than distance, then we define an
#edge connecting them.
_positions=[]
for m in range(self.Nvertices):
_x=random.random()*(float(settings.N)/settings.density)**0.5
_y=random.random()*(float(settings.N)/settings.density)**0.5
_positions.append([_x,_y])
for n in range(m):
if ((_x-_positions[n][0])**2+(_y-_positions[n][1])**2)**0.5<settings.distance:
edges.append([n,m]) # Below a given distance, vertices are connected
weights.append(1.) # for UD-graphs, all weights are one.
tab_individual_links[m].append(n) # Update of the links tab
tab_individual_links[n].append(m)
self.connections=edges
self.tab_individual_links=tab_individual_links
self.weights=weights
#Now we use a igraph object to describe our graph. This module has several interesting built-in functions.
g=igraph.Graph()
g.add_vertices(self.Nvertices)
for m in range(len(tab_individual_links)):
for n in range(len(tab_individual_links[m])):
g.add_edges([(m,tab_individual_links[m][n])])
self.independent_sets=g.independent_vertex_sets(min=0, max=0)
self.igraph_representation=g
elif self.typegraph=="Fixed Degree":
#We use the Igraph class to generate a certain kind of graph
g=igraph.Graph()
sequence=list(np.ones(self.Nvertices))
for m in range(len(sequence)):
sequence[m]=settings.degree
plap=g.Degree_Sequence(sequence)
self.igraph_representation=plap
for e in g.es:
edges.append(list(e.tuple))
weights.append(random.random())
self.connections=edges
self.weights=weights
self.independent_sets=g.independent_vertex_sets(min=0, max=0)
def Divide_non_connected_subgraphs(self):
"""This method divides the initial graph in its disconnected subgraphs.
The objective is to improve the performances of
QAOA UD-MIS when the connectivity is low.
Returns a list of all the disconnected subgraphs
"""
E=[]
for mm in range(self.Nvertices): #We loop through all the sites of the graph. val is a bool that asserts if
_val=False #the vertex mm is independent of all the other previous clusters.
_Dest=[] #Dest is a list of all the cluster indices the vertex mm is connected to.
for kk in range(len(E)):
for nn in range(len(E[kk])):
if mm in self.tab_individual_links[E[kk][nn]]: #if the vertex mm can be found in the links of any
_val=True #vertex nn in the cluster kk, then i) we change the value
_Dest.append(kk) #of _val to True ii) we add the cluster number kk to Dest.
E[kk].append(mm) #iii) we add vertex mm to cluster kk.
break #As soon as we find such link, break.
if _val==False:
E.append([mm]) #If the vertex mm cannot be found, then we create
else: #a new cluster
if len(_Dest)>1.:
for gg in range(len(_Dest)-1,0,-1): #If mm has been found in (previously) independent clusters
for tt in range(len(E[_Dest[gg]])): #we merge those clusters.
if E[_Dest[gg]][tt] not in E[_Dest[0]]:
E[_Dest[0]].append(E[_Dest[gg]][tt])
del E[_Dest[gg]]
return E
def indices_n_exc_basis_states(H):
"""
This function returns the indices such that list_indices_n_exc[n_0]
is the smallest index jj for which the vector jj has n_0 excitations.
"""
list_indices_n_exc=[0]
nn=0
for mm in range(len(H)):
if len(H[mm])>nn:
list_indices_n_exc.append(mm)
nn+=1
list_indices_n_exc.append(len(H))
return list_indices_n_exc
def generate_Hilbert_space(graph):
"""
This function generates the Hilbert space, either from a igraph object
of from a Graph object as defined above.
"""
if settings.type_graph=="Unit Disk":
if isinstance(graph, igraph.Graph):
H=graph.independent_vertex_sets(min=0, max=0)
else:
H=graph.independent_sets
H.insert(0,())
indices_nexc_H=indices_n_exc_basis_states(H)
return (H,indices_nexc_H)
elif settings.type_graph=="Fixed Degree":
H=[()]
ll=list(np.arange(settings.N))
for r in range(1,settings.N+1):
uu=list(itertools.combinations(ll, r))
for o in range(len(uu)):
H.append(uu[o])
indices_nexc_H=indices_n_exc_basis_states(H)
return (H,indices_nexc_H)
def generate_Hamiltonians(Hilbert_space,indices_coupling,**kwargs):
"""
This function returns the Hamiltonians of QAOA.
The first one is the mixing Hamiltonian.
The second-one is the phase-separation Hamiltonian.
The third one is the dissipation
"""
if settings.problem=="MIS":
H_Rabi=settings.Omega1*quantum_routines.sigma_x_operator(Hilbert_space,indices_coupling)
H_detuning=settings.delta_ee*quantum_routines.sigma_z_operator(Hilbert_space)
H_dissipation=-1j/2.*(settings.Gamma+settings.gamma_deph)*quantum_routines.sigma_z_operator(Hilbert_space)
elif settings.problem=="MaxCut":
H_11=settings.Omega1*quantum_routines.sigma_x_operator(Hilbert_space,indices_coupling)
graph_instance=kwargs.get('graph_instance',False)
edges=graph_instance.connections
weights=graph_instance.weights
H_22=weights[0]*quantum_routines.sigma_z_z_operator(Hilbert_space,edges[0][0],edges[0][1])
for m in range(1,len(edges)):
H_22+=weights[m]*quantum_routines.sigma_z_z_operator(Hilbert_space,edges[m][0],edges[m][1])
H_dissipation=-1j/2.*(settings.Gamma+settings.gamma_deph)*quantum_routines.sigma_z_operator(Hilbert_space)
else: ##Custom problem. Needs to specify the unitary.
pass
return (csr_matrix(H_Rabi),H_detuning,H_dissipation)