Package optgraphstate
Version 0.3.1
OptGraphState is a python package that implements the graph-theoretical strategy to optimize the fusion-based generation of any graph state, which is proposed in Lee & Jeong, arXiv:2304.11988 [quant-ph] (2023). The package has the following features:
- Finding a resource-efficient method of generating a given graph state through type-II fusions from multiple basic resource states, which are three-qubit linear graph states.
- Computing the corresponding resource overhead, which is quantified by the average number of required basic resource states or fusion attempts.
- Computing the success probability of graph state generation when the number of provided basic resource states is limited.
- Visualizing the original graph (of the graph state you want to generate), unraveled graphs, and fusion networks. An unraveled graph is a simplified graph where the corresponding graph state is equivalent to the desired graph state up to fusions and single-qubit Clifford operations. A fusion network is a graph that instructs the fusions between basic resource states required to generate the desired graph state.
- Various predefined sample graphs for input.
Github: https://github.com/seokhyung-lee/OptGraphState
Tutorials: https://github.com/seokhyung-lee/OptGraphState/raw/main/tutorials.pdf
Expand source code
"""
**Version 0.3.1**
**OptGraphState** is a python package that implements the graph-theoretical
strategy to optimize the fusion-based generation of any graph state, which is
proposed in [Lee & Jeong, arXiv:2304.11988 [quant-ph] (2023)](https://arxiv.org/abs/2304.11988).
The package has the following features:
- Finding a resource-efficient method of generating a given graph state through
type-II fusions from multiple basic resource states, which are three-qubit
linear graph states.
- Computing the corresponding resource overhead, which is quantified by the
average number of required basic resource states or fusion attempts.
- Computing the success probability of graph state generation when the number
of provided basic resource states is limited.
- Visualizing the original graph (of the graph state you want to generate),
unraveled graphs, and fusion networks. An unraveled graph is a simplified graph
where the corresponding graph state is equivalent to the desired graph state up
to fusions and single-qubit Clifford operations. A fusion network is a graph
that instructs the fusions between basic resource states required to generate
the desired graph state.
- Various predefined sample graphs for input.
Github: https://github.com/seokhyung-lee/OptGraphState
Tutorials: https://github.com/seokhyung-lee/OptGraphState/raw/main/tutorials.pdf
"""
import os
import sys
import networkx as nx
import scipy.signal as scsig
import decimal as dec
from .graph_tools import *
from .visualization import *
from .utils import *
try:
import parmap
except ModuleNotFoundError:
pass
try:
import tqdm
except ModuleNotFoundError:
pass
def _max_seed():
return 2**32
class GraphState:
#: Graph of the graph state to investigate.
#: See Sec. 7 of our [tutorial](https://github.com/seokhyung-lee/OptGraphState/raw/main/tutorials.pdf) for the list of its vertex attributes.
graph: ig.Graph
#: Unraveled graph generated by unraveling the original graph/
#:
#: It is `None` before the unraveled graph is created.
#: See Sec. 7 of our [tutorial](https://github.com/seokhyung-lee/OptGraphState/raw/main/tutorials.pdf) for the list of its vertex attributes.
unraveled_graph: ig.Graph
#: Fuson network constructed from the unraveled or original graph.
#:
#: It is `None` before the fusion network is created.
#: See Sec. 7 of our [tutorial](https://github.com/seokhyung-lee/OptGraphState/raw/main/tutorials.pdf) for the list of its vertex and edge
#: attributes.
fusion_network: ig.Graph
#: Any data obtained during unraveling the graph, constructing the fusion
#: network, and calculating the resource overhead.
data: dict
def __init__(self,
graph=None,
edges=None,
shape=None,
prms=None,
cliffords=None,
unraveled_graph=None,
fusion_network=None):
"""
Class for calculating and optimizing the resource overhead of the
fusion-based generation of a graph state.
The graph of the graph state can be given by the following
three ways:
1. Given explicitly by [`igraph.Graph`](https://python.igraph.org/en/stable/api/igraph.Graph.html) or [`networkx.Graph`](https://networkx.org/documentation/stable/reference/classes/graph.html).
2. Given by a list of edges.
3. Chosen among predefined graphs.
Parameters
----------
graph : None or igraph.Graph or networkx.Graph (default: None)
Graph of the concerned graph.
If it is given, `edges`, `shape`, and `prms` are ignored.
If it is `networkx.Graph`, it is internally converted to
`igraph.Graph`.
edges : None or list of 2-tuple of int (default: None)
List of edges that form the concerned graph.
Each integer in the tuples indicates a vertex label.
If it is given and `graph` is `None`, `shape` and `prms` are
ignored.
shape : None or str (default: None)
Shape of the concerned graph chosen among predefined graphs.
One of `[None, 'random', 'complete', 'star', 'linear', 'cycle',
'lattice', 'tree', 'rhg', 'repeater', 'parity_encoding', 'ptqc']`.
- `shape='random'` : Random graph for fixed numbers of vertices
and edges, sampled by the Erdös-Renyi model.
- `prms[0]` <`int`> : Number of vertices.
- `prms[1]` <`int`> : Number of edges.
- [Optional] `prms[2]` <`None` or `int`> : Random seed. If
`None`, the current system time is used as the seed. If not
given, the random number generator is not initialized.
- `shape='complete'`, `'star'`, `'linear'`, or `'cycle'` :
Complete, star, linear, or cycle graph, respectively.
- `prms[0]` <`int`> : Number of vertices.
- `shape='lattice'` : Lattice graph.
- `prms` <`tuple` of `int`> : Numbers of repeated vertices
along the axes. The dimension of the lattice is
automatically set as `len(prms)`.
- `shape='tree'` : Tree graph where all branches in each
generation have an equal number of children.
- `prms[0]` <`int`> : Degree of the root vertex.
- `prms[i]` (<`int`>, i >= 1) : Number of the children of each
`i`th-generation branch.
- `shape='rhg'` : Raussendorf-Harrington-Goyal lattice with primal
boundaries only.
- `prms[0]`, `prms[1]`, `prms[2]` <`int`> : Size of the lattice
along the three axes in the unit of a cell.
- `shape='repeater'` : Repeater graph with 4m vertices.
- `prms[0]` <`int`> : Parameter m.
- `shape='parity_encoding'` : (n, m) parity-encoded graph, where
each vertex of the logical graph corresponds to a qubit encoded in
the basis of either {(|0>^m + |1>^m)^n +- (|0>^m - |1>^m)^n}
(Orientation 1) or {[(|0> + |1>)^m +- (|0> - |1>)^m]^n}
(Orientation 2).
- `prms[0]` <`str` or `igraph.Graph`> : Logical-level graph
given by either its name or graph structure. Currently 3-star
(`"3-star"` or `"3-linear"`) and 6-cycle (`"6-cycle"` or
`"6-ring"`) graphs can be given by their names. For the other
graphs, it should be given by an `igraph.Graph` object. It
can be generated directly via python-igraph library or from
the function `optgraphstate.graph_tools.get_graph_from_edges()` or
`optgraphstate.graph_tools.get_sample_graph()`.
- `prms[1]`, `prms[2]` <`int`> : Parameters n and m of the
parity encoding.
- [Optional] `prms[3]` <`bool`> : Orientation of the parity
encoding. If `True` (default), "Orientation 1" is used. If
`False`, "Orientation 2" is used.
- `shape='ptqc'` : Microcluster for parity-encoding-based
topological quantum computing protocol.
- `prms[0]`, `prms[1]` <`int`> : Parameter n and m of the
parity encoding.
- `prms[2]` <`bool`> : Whether the H-configuration is
HIC (`True`) or HIS (`False`).
- `prms[3]` <`bool`> : Whether the microcluster is
central (`True`) or side (`False`) one.
prms : None or tuple or int (default: None)
Parameters for a predefined graph.
See the description for parameter `shape`.
If only one parameter is required, it can be given as a number, not
a tuple.
cliffords : None or list of str (default: None)
Local Clifford gates applied on the qubits of the graph
state.
If it is `None`, no Clifford gates are applied on the qubits.
If it is a `list` of `str`, its length should be equal to the
number of vertices in the graph. Its i-th element indicates the
Clifford gate applied on the i-th qubit. For example,
if it is `'H'`, it means that a Hadamard gate is applied on the
qubit. If it is `'H-S-Z'`, it means that Hadamard, phase,
and Z gates are applied in order.
unraveled_graph : None or igraph.Graph or networkx.Graph (default: None)
Pregiven unraveled graph.
The code does not check the validity of the given unraveled graph.
If it is [`networkx.Graph`](https://networkx.org/documentation/stable/reference/classes/graph.html),
it is internally converted to [`igraph.Graph`](https://python.igraph.org/en/stable/api/igraph.Graph.html).
fusion_network : None or igraph.Graph or networkx.Graph (default: None)
Pregiven fusion network.
The code does not check the validity of the given fusion network.
If it is [`networkx.Graph`](https://networkx.org/documentation/stable/reference/classes/graph.html),
it is internally converted to [`igraph.Graph`](https://python.igraph.org/en/stable/api/igraph.Graph.html).
"""
def convert_type(g, varname):
if g is None:
return None
elif isinstance(g, ig.Graph):
return g
elif isinstance(g, nx.Graph):
return ig.Graph.from_networkx(g)
else:
raise TypeError(f'Parameter {varname} should be igraph.Graph '
f'or networkx.Graph.')
if graph is not None:
self.graph = convert_type(graph, 'graph')
elif edges is not None:
self.graph = ig.Graph(edges=edges)
elif shape is not None:
try:
prms[0]
except TypeError:
prms = (prms,)
self.graph = get_sample_graph(shape, *prms)
else:
raise ValueError(
"At least one of graph, edges, and shape should be given.")
self.graph.vs['name'] = [str(vid) for vid in
range(self.graph.vcount())]
if cliffords is not None and edges is None:
self.graph.vs['clifford'] = cliffords
self.unraveled_graph = convert_type(unraveled_graph, 'unraveled_graph')
self.fusion_network = convert_type(fusion_network, 'fusion_network')
self.data = {}
def initialize(self):
"""
Initialize the created unraveled graph and fusion network and the
calculation data.
"""
self.unraveled_graph = None
self.fusion_network = None
self.data = {}
def unravel_graph(self,
unravel_bcs_first='random',
plot=False,
verbose=False):
"""
Unravel bipartitely-complete subgraphs (BCSs) and cliques of the graph.
The unraveled graph is saved in `self.unraveled_graph` as
[`igraph.Graph`](https://python.igraph.org/en/stable/api/igraph.Graph.html).
Parameters
----------
unravel_bcs_first : one of [True, False, 'random'] (default: 'random')
- `True`: BCSs are unraveled first, then clqiues are
unraveled.
- `False`: cliques are unraveled first, then BCSs are
unraveled.<br>
- `'random'`: the order is randomly chosen.
plot : bool (default: False)
Whether to plot the unraveled graph after unraveling.
verbose : bool (default: False)
Whether to print logs and plot the intermediate graphs during
the unraveling process.
Returns
-------
bcss : list of list of 2-tuple of list of str
Information on the unraveled BCSs.
`bcss[i][j][k][l]` (`k`=0 or 1) is the name of the `l`-th vertex in
the `k`-th part of the `j`-th BCS obtained by the `i`-th cycle of
finding non-overlapping BCSs.
cliques : list of list of set of str
Information on the unraveled cliques.
`cliques[i][j]` is the set of the names of the vertices in the
`j`-th clique obtained by the `i`-th cycle of finding
non-overlapping cliques.
unravel_bcs_first : bool
Whether BCSs are unraveled first or not.
"""
if unravel_bcs_first == 'random':
unravel_bcs_first = np.random.choice([True, False])
if unravel_bcs_first:
bcss = self.unravel_bcss(verbose=verbose)
cliques = self.unravel_cliques(verbose=verbose)
else:
cliques = self.unravel_cliques(verbose=verbose)
bcss = self.unravel_bcss(verbose=verbose)
if plot or verbose:
if verbose:
print('[Final]')
self.plot_graph(unraveled=True)
plt.show()
self.data['unravel'] = True
self.data['unravel_bcs_first'] = unravel_bcs_first
return bcss, cliques, unravel_bcs_first
def unravel_bcss(self, verbose=False):
"""
Unravel bipartitely-complete subgraphs (BCSs) of the graph.
The unraveled graph is saved in `GraphState.unraveled_graph` as
[`igraph.Graph`](https://python.igraph.org/en/stable/api/igraph.Graph.html).
Parameters
----------
verbose : bool (default: False)
Whether to print logs and plot the intermediate graphs during
the unraveling process.
Returns
-------
bcss : list of list of 2-tuple of list of str
Information on the unraveled BCSs.
`bcss[i][j][k][l]` (`k`=0 or 1) is the name of the `l`-th vertex in
the `k`-th part of the `j`-th BCS obtained by the `i`-th cycle of
finding non-overlapping BCSs.
"""
if self.unraveled_graph is None:
self.unraveled_graph = self.graph.copy()
graph = self.unraveled_graph
vs_attrs = graph.vs.attributes()
if 'ext_fusion' not in vs_attrs:
graph.vs['ext_fusion'] = None
if 'clifford' not in vs_attrs:
graph.vs['clifford'] = None
unraveled_bcss = []
new_vertex_name = graph.vcount()
while True:
# Repeat until there are no bipartitely-complete subgraphs
bcs_exist = False
while True:
bcss = find_nonoverlapping_bcss(graph, get_name=True)
if bcss:
bcs_exist = True
else:
break
unraveled_bcss.append(bcss)
eids_to_remove = []
for part1, part2 in bcss:
if verbose:
graph.delete_edges(eids_to_remove)
eids_to_remove.clear()
print('bcs to unravel =', part1, '&', part2)
vertex_color = []
for v in graph.vs:
if v['name'] in part1:
vertex_color.append('orange')
elif v['name'] in part2:
vertex_color.append('blue')
else:
vertex_color.append('white')
self.plot_graph(unraveled=True,
vertex_color=vertex_color)
plt.show()
eids_to_remove.extend([graph.get_eid(vname1, vname2) for
vname1, vname2 in
itertools.product(part1, part2)])
vname1 = str(new_vertex_name)
vname2 = str(new_vertex_name + 1)
new_v1 = graph.add_vertex(name=vname1,
ext_fusion=vname2,
clifford=None)
new_v2 = graph.add_vertex(name=vname2,
ext_fusion=vname1,
clifford=None)
new_vertex_name += 2
graph.add_edges(itertools.product([new_v1], part1))
graph.add_edges(itertools.product([new_v2], part2))
graph.delete_edges(eids_to_remove)
if not bcs_exist:
break
return unraveled_bcss
def unravel_cliques(self, verbose=False):
"""
Unravel cliques of the graph.
The unraveled graph is saved in `GraphState.unraveled_graph` as
[`igraph.Graph`](https://python.igraph.org/en/stable/api/igraph.Graph.html).
Parameters
----------
verbose : bool (default: False)
Whether to print logs and plot the intermediate graphs during
the unraveling process.
Returns
-------
cliques : list of list of set of str
Information on the unraveled cliques.
`cliques[i][j]` is the set of the names of the vertices in the
`j`-th clique obtained by the `i`-th cycle of finding
non-overlapping cliques.
"""
if self.unraveled_graph is None:
self.unraveled_graph = self.graph.copy()
graph = self.unraveled_graph
vs_attrs = graph.vs.attributes()
if 'ext_fusion' not in vs_attrs:
graph.vs['ext_fusion'] = None
if 'clifford' not in vs_attrs:
graph.vs['clifford'] = None
unraveled_cliques = []
def apply_clifford(v, clifford):
org_clifford = v['clifford']
if org_clifford is None:
new_clifford = clifford
else:
new_clifford = '-'.join([clifford, org_clifford])
v['clifford'] = new_clifford
while True:
cliques = find_nonoverlapping_cliques(graph, get_name=True)
if not cliques:
break
unraveled_cliques.append(cliques)
for clique in cliques:
if verbose:
print('clique to unravel =', clique)
vertex_color = ['orange' if vname in clique else 'white'
for vname in graph.vs['name']]
self.plot_graph(unraveled=True, vertex_color=vertex_color)
plt.show()
clique = list(clique)
clique_size = len(clique)
# Choose a vertex to apply LC
degrees = graph.degree(clique)
min_degree = min(degrees)
if min_degree == clique_size - 1:
# There exists a vertex in the clique that doesn't have
# outer edges
vname_LC = [vname for vname, deg in zip(clique, degrees) if
deg == min_degree]
need_to_separate = False
else:
vname_LC = clique
need_to_separate = True
if len(vname_LC) > 1:
vname_LC = np.random.choice(vname_LC)
else:
vname_LC = vname_LC[0]
old_v_LC = graph.vs.find(name=vname_LC)
# Separate the edges (E) incident to v_LC outside the clique
# from v_LC
eids_to_delete = []
if need_to_separate:
# Alter v_LC
old_v_LC['name'] = str(graph.vcount())
new_v_LC = graph.add_vertex(
name=vname_LC,
clifford=old_v_LC['clifford'],
ext_fusion=old_v_LC['ext_fusion']
)
# Vertex having an external fusion with old v_LC
v_ext_fusion = graph.add_vertex(
name=str(graph.vcount()),
clifford=None,
ext_fusion=old_v_LC['name']
)
# Modify old v_LC
old_v_LC['clifford'] = None
old_v_LC['ext_fusion'] = v_ext_fusion['name']
graph.add_edge(new_v_LC, v_ext_fusion)
old_vid_LC = old_v_LC.index
ngh_vids = graph.neighbors(old_vid_LC)
for ngh_vid in ngh_vids:
if graph.vs[ngh_vid]['name'] not in clique:
graph.add_edge(ngh_vid, new_v_LC.index)
eids_to_delete.append(
graph.get_eid(old_vid_LC, ngh_vid)
)
# Remove edges
adj_vnames = set(clique) - {vname_LC}
new_eids_to_delete = [graph.get_eid(vname1, vname2) for
vname1, vname2 in
itertools.combinations(adj_vnames, r=2)]
eids_to_delete.extend(new_eids_to_delete)
graph.delete_edges(eids_to_delete)
# Apply LC
apply_clifford(old_v_LC, 'RXd')
for adj_vname in adj_vnames:
adj_v = graph.vs.find(name=adj_vname)
apply_clifford(adj_v, 'RZ')
return unraveled_cliques
def build_fusion_network(self,
use_unraveled_graph=True,
plot=False,
verbose=False):
"""
Build a fusion network from the original graph or unraveled graph.
If you want to build it from the unraveled graph, at least one of
`GraphState.unravel_graph()`, `GraphState.unravel_bcss()`, and
`GraphState.unravel_cliques()` must be executed beforehand.
The constructed fusion network is saved in `GraphState.fusion_network`
as [`igraph.Graph`](https://python.igraph.org/en/stable/api/igraph.Graph.html).
Parameters
----------
use_unraveled_graph : bool (default: True)
Whether to use the unraveled graph or the original graph for
building a fusion network.
plot : bool (default: False)
Whether to plot the fusion network after building it.
verbose : bool (default: False)
Whether to print logs.
"""
graph = self.unraveled_graph if use_unraveled_graph else self.graph
if graph is None:
raise ValueError("No unraveled qubit graph created.")
# Fusion network
network = ig.Graph()
self.fusion_network = network
node_groups = {}
# Links inside star graphs
for v in graph.vs:
num_internal_nodes = v.degree() - 1
vname = v['name']
if num_internal_nodes >= 1:
# Add nodes
nid_init = network.vcount()
seed = np.random.randint(0, num_internal_nodes)
node_names = [vname if i == 0 else f'{vname}-{i}' for
i in itertools.chain(range(seed, -1, -1),
range(seed + 1,
num_internal_nodes))]
attr = {
'name': node_names,
'seed': [True if i == seed else False for i in
range(num_internal_nodes)],
'node_group': vname,
# 'clifford_root': None,
# 'clifford_leaves': None
}
network.add_vertices(num_internal_nodes, attributes=attr)
node_groups[vname] \
= network.vs[nid_init:nid_init + num_internal_nodes]
if num_internal_nodes >= 2:
# Connect internal links
links = [(nid, nid + 1) for nid
in range(nid_init,
nid_init + num_internal_nodes - 1)]
attr = {
'kind': "RL",
'root_node': [
node_names[i] if i < seed else node_names[i + 1]
for i in range(num_internal_nodes - 1)],
'cliffords': {}
}
network.add_edges(links, attributes=attr)
# Links between star graphs
for e in graph.es:
vs = [e.source_vertex, e.target_vertex]
deg_vs = graph.degree(vs)
if deg_vs[0] > 1 and deg_vs[1] > 1:
nodes_to_connect = []
for v in vs:
vname = v['name']
nodes = node_groups[vname].select(
lambda node: node.degree() < (2 if node['seed'] else 3)
)
nodes_to_connect.append(np.random.choice(nodes))
network.add_edge(*nodes_to_connect,
kind='LL',
root_node=None,
cliffords={})
if verbose:
print("Fusion network of the unraveled graph:")
self.plot_fusion_network()
plt.show()
# Set of seed node names where root vertices are connected by
# external fusions.
nnames_root_connected = set()
is_node_not_full = lambda node: node.degree() < (
2 if node['seed'] and (
node['name'] not in nnames_root_connected) else 3)
def get_nodes_containing_vertex(vname):
try:
node = node_groups[vname].find(name=vname)
is_root = True
seed_node_name = vname
except KeyError:
ngh = graph.vs[graph.neighbors(vname)[0]]
seed_node_name = ngh['name']
nodes = node_groups[seed_node_name].select(is_node_not_full)
node = np.random.choice(nodes)
is_root = False
return node, is_root, seed_node_name
vs_attrs = graph.vs.attributes()
# Links by external fusions
if 'ext_fusion' in vs_attrs:
vnames_to_skip = set()
for v1 in graph.vs.select(ext_fusion_ne=None):
vname1 = v1['name']
if vname1 in vnames_to_skip:
continue
vname2 = v1['ext_fusion']
v2 = graph.vs.find(name=vname2)
vnames_to_skip.add(vname2)
node1, is_root1, _ = get_nodes_containing_vertex(vname1)
node2, is_root2, _ = get_nodes_containing_vertex(vname2)
if is_root1 and is_root2:
kind = 'RR'
root_node = None
nnames_root_connected.add(node1['name'])
nnames_root_connected.add(node2['name'])
elif not is_root1 and not is_root2:
kind = 'LL'
root_node = None
else:
kind = 'RL'
root_node = node1['name'] if is_root1 else node2['name']
nnames_root_connected.add(root_node)
cliffords = {}
cl1 = v1['clifford']
cl2 = v2['clifford']
for node, cl in zip([node1, node2], [cl1, cl2]):
if cl is not None:
cliffords[node['name']] = cl
network.add_edge(node1,
node2,
kind=kind,
root_node=root_node,
cliffords=cliffords)
network.es['name'] = [str(eid) for eid in range(network.ecount())]
if verbose:
print("Add external fusions:")
self.plot_fusion_network()
plt.show()
# Clifford gates on surviving qubits
# if 'clifford' in vs_attrs:
# cls_in_node_group_leaves = {}
# for v_cl in graph.vs.select(clifford_ne=None, ext_fusion=None):
# vname = v_cl['name']
# _, is_root, seed_node_name = get_nodes_containing_vertex(vname)
# seed_node = network.vs.find(name=seed_node_name)
# cl = v_cl['clifford']
#
# if is_root:
# if seed_node_name not in nnames_root_connected:
# seed_node['clifford_root'] = cl
#
# else:
# try:
# cls_in_node_group_leaves[seed_node_name].append(cl)
# except KeyError:
# cls_in_node_group_leaves[seed_node_name] = [cl]
#
# for seed_node_name, cls in cls_in_node_group_leaves.items():
# node_group = node_groups[seed_node_name]
# nums_surviving_leaves = []
# for node in node_group:
# if node['name'] in nnames_root_connected:
# num_surviving_leaves = 3 - node.degree()
# else:
# num_surviving_leaves = 2 - node.degree()
# nums_surviving_leaves.append(num_surviving_leaves)
# total_num_surviving_leaves = sum(nums_surviving_leaves)
#
# if len(cls) < total_num_surviving_leaves:
# cls.extend([None]
# * (total_num_surviving_leaves - len(cls)))
# np.random.shuffle(cls)
#
# i_start = 0
# for node, num_leaves in zip(node_group, nums_surviving_leaves):
# cls_current_node = cls[i_start:i_start + num_leaves]
# cls_current_node = [cl for cl in cls_current_node
# if cl is not None]
# node['clifford_leaves'] = cls_current_node
# i_start += num_leaves
# if verbose:
# print("Apply Clifford gates:")
# self.plot_fusion_network()
# plt.show()
self.fusion_network = network
if plot:
print("Final:")
self.plot_fusion_network()
plt.show()
def _contract_edge(self,
fusion_network: ig.Graph,
ename_to_merge,
update_weight_and_order=True):
ename_to_merge = str(ename_to_merge)
e_to_merge = fusion_network.es.find(name=ename_to_merge)
v_merged, v_removed \
= e_to_merge.source_vertex, e_to_merge.target_vertex
enames_updated_weight = []
if v_merged.degree() < v_removed.degree():
v_merged, v_removed = v_removed, v_merged
vname_merged = v_merged['name']
vname_removed = v_removed['name']
if update_weight_and_order:
v_merged['weight'] = e_to_merge['weight']
v_merged['weight_f'] = e_to_merge['weight_f']
v_merged['order'] = max(v_merged['order'], v_removed['order']) + 1
assert vname_merged != vname_removed
eids_to_delete = list(set(fusion_network.incident(v_removed)))
v_removed['on'] = False
calculate_ftpdf = 'ftpdf' in fusion_network.vertex_attributes()
for eid_connected in eids_to_delete:
e_connected: ig.Edge = fusion_network.es[eid_connected]
attrs_e_connected = e_connected.attributes()
ename_connected = e_connected['name']
if ename_connected != ename_to_merge:
enames_updated_weight.append(ename_connected)
vs_ngh = e_connected.source_vertex, e_connected.target_vertex
new_edge_eps = [v_merged if v_ngh['name'] == vname_removed
else v_ngh for v_ngh in vs_ngh]
if new_edge_eps[0] == new_edge_eps[1]: # If a loop is formed
v_vrt: ig.Vertex = fusion_network.add_vertex(
name=f'vrt_{fusion_network.vcount()}',
on=True,
)
if update_weight_and_order:
v_vrt.update_attributes(weight=0, weight_f=0, order=0)
if calculate_ftpdf:
v_vrt['ftpdf'] = np.array([1])
new_edge_eps = [v_merged, v_vrt]
new_edge: ig.Edge = fusion_network.add_edge(*new_edge_eps)
new_edge.update_attributes(**attrs_e_connected)
fusion_network.delete_edges(eids_to_delete)
if update_weight_and_order:
p_succ = fusion_network['p_succ']
for eid_connected in list(set(fusion_network.incident(v_merged))):
e_connected = fusion_network.es[eid_connected]
v_ngh1, v_ngh2 = e_connected.source_vertex, e_connected.target_vertex
assert v_ngh1 != v_ngh2
e_connected['weight'] \
= (v_ngh1['weight'] + v_ngh2['weight']) / p_succ
e_connected['weight_f'] \
= (v_ngh1['weight_f'] + v_ngh2['weight_f'] + 1) / p_succ
self.fusion_network.es.find(name=ename_to_merge)['order'] \
= v_merged['order']
return v_merged, v_removed, enames_updated_weight
def calculate_overhead(self,
p_succ=0.5,
strategy='weight_and_matching',
optimize_num_fusions=False,
fusion_order=None):
"""
Calculate the resource overhead (average number of basic resource
states required to generate the desired graph state) from the fusion
network.
`GraphState.build_fusion_network()` must be executed beforehand.
The resulting data is saved in `GraphState.data`.
Parameters
----------
p_succ : float (default: 0.5)
Success probability of a fusion.
strategy : str, one of ['weight', 'matching', 'weight_and_matching', 'random'] (default: 'weight_and_matching')
Strategy for determining the edge to contract.
- `'weight'`: Contract a random one among the edges with the
smallest weight.
- `'matching'`: Contract an edge in a maximum matching.
- `'weight_and_matching'`: Contract an edge in a maximum matching
of the subgraph of the intermediate fusion network induced by
the edges with the smallest weight.
- `'random'`: Contract a random edge.
optimize_num_fusions : bool
If `True`, the average number of required fusion attempts are used
to quantify resource overheads instead of the average number of
required basic resource states.
fusion_order : None or list of {int or str} (default: None)
Fusion order given explicitly as vertex names.
If it is not `None`, parameter `strategy` is ignored.
Returns
-------
data : dict
Outcomes of the calculation, which is a shallow copy of
`GraphState.data`.<br>
The calculated overhead and number of steps can be obtained from
`data['overhead']` and `data['num_steps']`, respectively.
"""
if self.fusion_network is None:
raise ValueError("No fusion network created")
# Trivial cases
node_num = self.fusion_network.vcount()
if node_num == 0:
self.data['overhead'] = 0
self.data['num_fusions'] = 0
self.data['num_steps'] = 0
return self.data
elif node_num == 1:
self.data['overhead'] = 1
self.data['num_fusions'] = 0
self.data['num_steps'] = 0
return self.data
if fusion_order is None:
fusion_order = []
is_fusion_order_given = False
else:
is_fusion_order_given = True
self.fusion_network['p_succ'] = p_succ
self.fusion_network.es['order'] = None
# Initialize intermediate fusion network
network = self.fusion_network.copy()
network.vs['weight'] = 1
network.vs['weight_f'] = 0
network.vs['order'] = 0
network.vs['on'] = True
network.es['weight'] = 2 / p_succ
network.es['weight_f'] = 1 / p_succ
del network.es['order']
turn = 0
weight_key = 'weight_f' if optimize_num_fusions else 'weight'
# Iterate until no edges remain in the fusion network
while True:
if not network.ecount():
break
if is_fusion_order_given:
enames_curr_step = [str(fusion_order[turn])]
is_parellel = True
elif strategy == 'weight':
min_weight = min(network.es[weight_key])
eids_min_weight = network.es.select(weight=min_weight)
enames_curr_step = eids_min_weight['name']
is_parellel = len(enames_curr_step) == 1
# elif strategy == 'betweenness':
# eb = np.array(network.edge_betweenness())
# min_eb = np.min(eb)
# eids_curr_step = np.nonzero(eb == min_eb)[0]
# enames_curr_step = [network.es[eid]['name'] for eid in
# eids_curr_step]
# is_parellel = len(enames_curr_step) == 1
#
# elif strategy == 'weight_and_betweenness':
# min_weight = min(network.es['weight'])
# eids_min_weight = network.es.select(weight=min_weight)
# es_min_ovh = eids_min_weight
#
# eb = network.edge_betweenness()
# ebs_min_ovh = np.array([eb[e.index] for e in es_min_ovh])
# min_eb = np.min(ebs_min_ovh)
# enames_curr_step = [es_min_ovh[i]['name'] for i in
# np.nonzero(ebs_min_ovh == min_eb)[0]]
# is_parellel = len(enames_curr_step) == 1
elif 'matching' in strategy:
if strategy == 'weight_and_matching':
min_weight = min(network.es[weight_key])
if optimize_num_fusions:
es_min_weight = network.es.select(weight_f=min_weight)
else:
es_min_weight = network.es.select(weight=min_weight)
subnetwork = network.subgraph_edges(es_min_weight)
else:
subnetwork = network
subnetwork_nx = subnetwork.to_networkx()
if isinstance(subnetwork_nx, nx.MultiGraph):
subnetwork_nx = nx.Graph(subnetwork_nx)
matching = nx.max_weight_matching(subnetwork_nx, weight=None)
enames_curr_step = \
subnetwork.es[subnetwork.get_eids(matching)]['name']
is_parellel = True
elif strategy == 'random':
enames_curr_step = [np.random.choice(network.es['name'])]
is_parellel = True
else:
raise ValueError
recalculated_enames = []
# if get_fusion_order and not is_fusion_order_given:
# fusion_order_curr_step = set()
# fusion_order.append(fusion_order_curr_step)
while True:
if not is_parellel:
for rec_ename in recalculated_enames:
try:
enames_curr_step.remove(rec_ename)
except ValueError:
pass
if not enames_curr_step:
break
recalculated_enames.clear()
if is_parellel:
ename_to_merge = enames_curr_step.pop()
else:
ename_to_merge = np.random.choice(enames_curr_step)
enames_curr_step.remove(ename_to_merge)
_, _, enames_updated_weight \
= self._contract_edge(network,
ename_to_merge)
recalculated_enames.extend(enames_updated_weight)
v_final = network.vs.select(on=True)
overhead = sum(v_final['weight'])
num_fusions = sum(v_final['weight_f'])
num_steps = max(v_final['order'])
results = {
'overhead': overhead,
'num_fusions': num_fusions,
'num_steps': num_steps,
'fusion_order_strategy': strategy,
'p_succ': p_succ,
}
if optimize_num_fusions:
results['optimize_num_fusions'] = True
# if get_fusion_order:
# results['fusion_order'] = fusion_order
self.data.update(results)
return self.data.copy()
def calculate_succ_probs(self,
cutoff=0.95,
auto_increasing_prec=True,
prec=30,
prec_interval=5,
diff_overhead_thrs=0.01):
"""
Calculate the success probability of the generation of the graph
state for each resource count. In other words, get the cumulative mass
function (CMF) of the resource count required to generate the state.
The success probability is computed while increasing the resource
count until the value reaches `cutoff` that is smaller than one.
The estimated resource overhead, which is the expectation value of the
resource count, is additionally returned.
It uses the `decimal` module instead of float64 since the calculation
involves the summation of many extremely small numbers thus
floating-point errors may be detrimental.
By default, it executes the computation multiple times while
increasing the precision by 5 starting from 30. When the estimated
overhead does not change by more than 1% in two consecutive trials, the
iteration is terminated and the results of the final trial are returned.
Parameters
----------
cutoff : float (default: 0.95)
Cutoff threshold between 0 and 1.
auto_increasing_prec : bool (default: True)
Whether to execute the computation multiple times. If it is False,
the parameters `prec_interval` and `diff_overhead_thrs` are ignored.
prec : int (default: 30)
Initial precision of numbers.
prec_interval : int (default: 5)
Interval of precisions between two consecutive trials.
diff_overhead_thrs : float (default: 0.01)
Threshold of the relative difference between the overheads estimated
from two consecutive trials for determining the termination of the
iteration. Namely, if the overheads are `o1` and `o2` in order, the
iteration terminates when `abs(o1 - o2) / o2 < diff_overhead_thrs`.
Returns
-------
resource_count_start : int
First resource count that gives a nonzero probability.
probs : 1D numpy array of decimal.Decimal
Success probabilities for the resource counts starting from
`resource_count_start`. `probs[i]` is the value corresponding to
the resource count of `resource_count_start+i`.
overhead : decimal.Decimal
Resource overhead estimated by the calculated probabilities.
If `cutoff` is close enough to one, this value should not be
significantly different from the correct one (`GraphState.data['overhead']`).
"""
if self.fusion_network is None:
raise ValueError("No fusion network created")
if 'order' not in self.fusion_network.edge_attributes():
raise ValueError("No fusion order data in the fusion network")
if not auto_increasing_prec:
network: ig.Graph = self.fusion_network.copy()
dec.getcontext().prec = prec
for v in network.vs:
v['ftpdf'] = np.array([dec.Decimal(0), dec.Decimal(1)])
network.vs['on'] = True
p_succ = network['p_succ']
orders = network.es['order']
num_steps = max(orders)
for order in range(1, num_steps + 1):
enames = network.es.select(order=order)['name']
for ename in enames:
link = network.es.find(name=ename)
node1, node2 = link.source_vertex, link.target_vertex
new_ftpdf = get_ftpdf_contracted(node1['ftpdf'],
node2['ftpdf'],
p_succ=p_succ)
v_merged, _, _ \
= self._contract_edge(network,
ename,
update_weight_and_order=False)
v_merged['ftpdf'] = new_ftpdf
ftpdfs_final = network.vs.select(on=True)['ftpdf']
while True:
if len(ftpdfs_final) == 1:
ftpdf_final = ftpdfs_final[0]
break
ftpdfs_final.append(scsig.convolve(ftpdfs_final[0],
ftpdfs_final[1]))
del ftpdfs_final[1], ftpdfs_final[0]
resource_count_start, probs \
= recover_cmf_from_ftpdf(ftpdf_final,
cutoff)
pmf = np.diff(probs)
overhead \
= np.sum(pmf * np.arange(resource_count_start,
resource_count_start + pmf.size))
else:
prev_overhead = None
while True:
print(f'prec = {prec}: ', end='')
try:
resource_count_start, probs, overhead \
= self.calculate_succ_probs(cutoff=cutoff,
auto_increasing_prec=False,
prec=prec)
except ValueError:
print('Error')
prec += prec_interval
continue
if prev_overhead is not None \
and abs(overhead - prev_overhead) / overhead < diff_overhead_thrs:
print(overhead)
break
print(overhead)
prec += prec_interval
prev_overhead = overhead
return resource_count_start, probs, overhead
def simulate(self,
n_iter,
p_succ=0.5,
mp=False,
n_procs=None,
get_all_data=False,
get_all_graphs=False,
get_all_fusion_networks=False,
unravel=True,
unravel_bcs_first='random',
fusion_order_strategy='weight_and_matching',
optimize_num_fusions=False,
seed='keep',
verbose=True,
pbar=True,
**kwargs):
"""
Execute the strategy for a fixed number of iterations and obtain the
best one only (by default).
Attributes such as `GraphState.data`, `GraphState.unraveled_graph`, and
`GraphState.fusion_network` are updated according to the result of the
best sample.
Parameters
----------
n_iter : int
Iteration number.
p_succ : float (default: 0.5)
Success probability of a fusion.
mp : bool (default: False)
Whether to use multiprocessing for the iterations.
Package *parmap* should be installed to use it.
n_procs : None or int (default: None)
Maximal number of simultaneous processes for multiprocessing.
If it is `None`, the number of CPUs is used.
Ignored when `mp` is `False`.
get_all_data : bool (default: False)
Whether to obtain the data (overheads, numbers of steps, etc.) from
all samples or only the best sample.
get_all_graphs : bool (default: False)
Whether to obtain the unraveled graphs from all samples or only the
best sample.
get_all_fusion_networks : bool (default: False)
Whether to obtain the fusion networks from all samples or only the
best sample.
unravel : bool (default: True)
Whether to unravel the graph or not.
unravel_bcs_first : one of [True, False, 'random'] (default: 'random')
- `True`: BCSs are unraveled first, then clqiues are unraveled.
- `False`, cliques are unraveled first, then BCSs are unraveled.
- `'random'`, the order is randomly chosen.
fusion_order_strategy : one of ['weight', 'matching', 'weight_and_matching', 'random'] (default: `weight_and_matching')
Strategy for determining the edge to contract in each step.
- `'weight'`: Contract a random one among the edges with the
smallest weight.
- `'matching'`: Contract an edge in a maximum matching.
- `'weight_and_matching'`: Contract an edge in a maximum matching
of the subgraph of the intermediate fusion network induced by
the edges with the smallest weight.
- `'random'`: Contract a random edge.
optimize_num_fusions : bool (default: False)
If `True`, use the average number of fusion attempts to quantify
resource overheads instead of the average number of basic resource
states.
seed : 'keep' or None or int (default: 'keep')
Random seed.
- `'keep'`: The seed is not initialized.
- `None`: The current time is used as the random seed.
- `int`: The given number is used as the random seed.
If `n_iter>1`, the given seed is used to sample random seeds for
individual iterations. However, if `n_iter==1`, the given seed is
used as the random seed for the (only one) iteration itself.
verbose : bool (default: True)
Whether to print logs.
pbar : bool (default: True)
Whether to show a progress bar. Ignored if tqdm is not installed.
kwargs : dict
Additional keyword arguments for calculating overheads.
See the description of `GraphState.calculate_overhead()`.
Returns
-------
res : dict
Dictionary containing the results of the iterations with keys:
- `'best_overhead'`: Overhead of the best sample (i.e., sample with
the smallest overhead or avg fusion number, determined by parameter
`optimize_num_fusions`).
- `'best_num_fusions'`: Average number of fusions of the best sample.
- `'best_num_steps'`: Number of steps (i.e., groups of fusions that
can be done in parallel) of the best sample.
- `'best_seed'`: Random seed for the best sample. To recover the
sample from it, use the `seed` parameter of `GraphState.simulate()`
with `n_iter=1`.
- `'n_iter'`: Number of iterations. Same as parameter `n_iter`.
- `'unravel_bcs_first'`: Whether to unravel BCSs or cliques first
for the best sample.
- `'overheads'`, `'nums_fusions'`, `'nums_steps'`, `'seeds'`: Lists
of the overheads, avg fusion numbers, step numbers, and seeds of
all samples, respectively. Exist only when `get_all_data==True`.
- `'unraveled_graphs'`: List of the unraveled graphs of all
samples. Exists only when `get_all_graphs==True`.
- `'fusion_networks'`: List of the fusion networks of all samples.
Exists only when `get_all_fusion_networks==True`.
"""
t0 = time.time()
overhead_key = 'num_fusions' if optimize_num_fusions else 'overhead'
if seed != 'keep':
np.random.seed(seed)
if mp:
if n_procs is None:
n_procs = os.cpu_count()
mp = mp and n_iter >= n_procs
if not mp:
if verbose:
print("Multiprocessing OFF.")
print(f"Calculating for n_iter = {n_iter}...")
if 'tqdm' not in sys.modules:
pbar = False
if verbose:
print("Install tqdm package to see the progress bar.")
if n_iter == 1 and seed is not None and seed != 'keep':
seeds_samples = [seed]
else:
seeds_samples = np.random.randint(0, _max_seed(), size=n_iter)
overheads = [] if get_all_data else None
nums_fusions = [] if get_all_data else None
nums_steps = [] if get_all_data else None
seeds = [] if get_all_data else None
unravalled_graphs = [] if get_all_graphs else None
fusion_networks = [] if get_all_fusion_networks else None
best_sample = None
lowest_overhead = None
iterable = range(n_iter)
if pbar:
iterable = tqdm.tqdm(iterable)
for i_sample in iterable:
seed_sample = seeds_samples[i_sample]
np.random.seed(seed_sample)
if unravel:
self.unraveled_graph = None
try:
self.unravel_graph(unravel_bcs_first=unravel_bcs_first)
except:
print('Error occurs during unraveling')
print('seed =', seed_sample)
raise ValueError
try:
self.build_fusion_network(use_unraveled_graph=unravel)
except:
print('Error occurs during building fusion network')
print('seed =', seed_sample)
raise ValueError
try:
data_now = self.calculate_overhead(
p_succ=p_succ,
strategy=fusion_order_strategy,
optimize_num_fusions=optimize_num_fusions,
**kwargs)
except:
print('Error occurs during calculating overhead')
print('seed =', seed_sample)
raise ValueError
overhead_now = data_now[overhead_key]
num_steps_now = data_now['num_steps']
self.data['seed'] = seed_sample
if lowest_overhead is None or overhead_now < lowest_overhead:
best_sample = i_sample
lowest_overhead = overhead_now
best_gs = self.copy()
if get_all_data:
overheads.append(data_now['overhead'])
nums_fusions.append(data_now['num_fusions'])
nums_steps.append(num_steps_now)
seeds.append(seed_sample)
if get_all_graphs:
unravalled_graphs.append(self.unraveled_graph)
if get_all_fusion_networks:
fusion_networks.append(self.fusion_network)
res = {
'best_overhead': best_gs.data['overhead'],
'best_num_fusions': best_gs.data['num_fusions'],
'best_num_steps': best_gs.data['num_steps'],
'best_seed': best_gs.data['seed'],
'n_iter': n_iter}
if unravel:
res['unravel_bcs_first'] = best_gs.data['unravel_bcs_first']
if get_all_data or get_all_graphs or get_all_fusion_networks:
res['best_sample'] = best_sample
if get_all_data:
res['overheads'] = overheads
res['nums_fusions'] = nums_fusions
res['nums_steps'] = nums_steps
res['seeds'] = seeds
if get_all_graphs:
res['unraveled_graphs'] = unravalled_graphs
if get_all_fusion_networks:
res['fusion_networks'] = fusion_networks
else:
if 'parmap' not in sys.modules:
raise ModuleNotFoundError("Package parmap is not installed.")
if verbose:
print(f"Multiprocessing ON: n_procs = {n_procs}")
print(f"Calculating for n_iter = {n_iter}... ", end='')
additional_keys = []
if get_all_data:
additional_keys.extend(['overheads', 'nums_fusions',
'nums_steps', 'seeds'])
if get_all_graphs:
additional_keys.append('unraveled_graphs')
if get_all_fusion_networks:
additional_keys.append('fusion_networks')
left = n_iter % n_procs
ns_samples = [n_iter // n_procs] * n_procs
for i in range(left):
ns_samples[i] += 1
seeds = np.random.randint(0, _max_seed(), size=n_procs)
res_procs = parmap.starmap(
_simulate_single,
list(zip(ns_samples, seeds)),
self.graph,
p_succ=p_succ,
get_all_data=get_all_data,
get_all_graphs=get_all_graphs,
get_all_fusion_networks=get_all_fusion_networks,
unravel=unravel,
unravel_bcs_first=unravel_bcs_first,
fusion_order_strategy=fusion_order_strategy,
optimize_num_fusions=optimize_num_fusions,
pbar=False,
pm_pbar=pbar,
**kwargs)
best_proc = np.argmin(
[res_each[f'best_{overhead_key}'] for res_each in res_procs]
)
res = res_procs[best_proc]
res['n_iter'] = n_iter
best_gs = res['best_gs']
del res['best_gs']
if additional_keys:
res['best_sample'] += sum(ns_samples[:best_proc])
for key in additional_keys:
vals = [res_each[key] for res_each in res_procs]
res[key] = list(itertools.chain(*vals))
if verbose:
print(f"Done. Best: {res[f'best_{overhead_key}']:.2f} "
f"({time.time() - t0:.2f} s)")
self.unraveled_graph = best_gs.unraveled_graph
self.fusion_network = best_gs.fusion_network
self.data = best_gs.data
return res
def simulate_adaptive(self,
init_n_iter,
mul=2,
p_succ=0.5,
mp=False,
n_procs=None,
get_all_data=False,
get_all_graphs=False,
get_all_fusion_networks=False,
unravel=True,
unravel_bcs_first='random',
fusion_order_strategy='weight_and_matching',
optimize_num_fusions=False,
seed='keep',
verbose=True,
pbar=True,
**kwargs):
"""
Run the adaptive iteration method for the strategy and obtain the
best one only (by default).
The adaptive iteration method looks for the best iteration while
keeps increasing the iteration number until a certain condition
meets. In detail, denoting N iterations of the strategy as R(N),
R(`init_n_iter`) is first executed and `q0` is obtained which is the
lowest resource overhead. Then, R(`mul`*`init_n_iter`) is executed
and `q1` is obtained similarly. If `q0 <= q1`, `q0` is returned. If
otherwise, R(`mul**2*init_n_iter`) is executed and `q2` is obtained.
If `q1 <= q2`, `q1` is returned. If otherwise, R(`mul**3*init_n_iter`)
is executed, and so on.
Parameters
----------
init_n_iter : int
Initial iteration number.
mul : int (default: 2)
Multiplicative factor of the iteration number.
See the description of `GraphState.simulate()` for the other parameters.
Returns
-------
res : dict
Dictionary containing the results of the iterations.
See the description of `GraphState.simulate()` for its keys.
"""
if mp and n_procs is None:
n_procs = os.cpu_count()
if seed != 'keep':
np.random.seed(seed)
additional_keys = []
if get_all_data:
additional_keys.extend(['overheads', 'nums_fusions', 'nums_steps'])
if get_all_graphs:
additional_keys.append('unraveled_graphs')
if get_all_fusion_networks:
additional_keys.append('fusion_networks')
if verbose:
if mp:
print(f"Multiprocessing (n_procs = {n_procs})")
else:
print("No multiprocessing")
best_overhead_key \
= 'best_num_fusions' if optimize_num_fusions else 'best_overhead'
n_iter_history = []
n_iter_now = init_n_iter
res = None
while True:
if verbose:
print(f"Calculating for n_iter = {n_iter_now}... ", end='')
t0 = time.time()
n_iter_history.append(n_iter_now)
res_now = self.simulate(
n_iter=n_iter_now,
p_succ=p_succ,
mp=mp,
n_procs=n_procs,
get_all_data=get_all_data,
get_all_graphs=get_all_graphs,
get_all_fusion_networks=get_all_fusion_networks,
unravel=unravel,
unravel_bcs_first=unravel_bcs_first,
fusion_order_strategy=fusion_order_strategy,
optimize_num_fusions=optimize_num_fusions,
verbose=False,
pbar=pbar,
**kwargs
)
if res is None:
res = res_now
best_gs = self.copy()
n_iter_now *= mul
else:
for key in additional_keys:
res[key].extend(res_now[key])
if res_now[best_overhead_key] < res[best_overhead_key]:
for key in additional_keys:
res_now[key] = res[key]
res = res_now
best_gs = self.copy()
n_iter_now *= mul
else:
if verbose:
print(f"Done. Best: {res[best_overhead_key]:.2f} ("
f"{time.time() - t0:.2f} s)")
break
if verbose:
print(f"Done. Best: {res[best_overhead_key]:.2f} "
f"({time.time() - t0:.2f} s)")
res['n_iter'] = sum(n_iter_history)
if additional_keys:
res['best_sample'] += res['best_sample']
self.unraveled_graph = best_gs.unraveled_graph
self.fusion_network = best_gs.fusion_network
self.data = best_gs.data
return res
def get_instructions(self):
"""
Get the instruction to generate the desired graph state from multiple
three-qubit linear graph states.
One of `GraphState.calculate_overhead()`, `GraphState.simulate()`, and
`GraphState.simulate_adaptive()` must be executed beforehand.
Returns
-------
node_names : list of str
List of the names of nodes in the fusion network.
fusions : dict
Dictionary that contains the information about required fusions and
Clifford gates.
Each required fusion is represented by a 2-tuple of 3-tuples:
`((n1, q1, cl1), (n2, q2, cl2))`. `n1` and `n2` are the names of
the nodes involved in the fusion, `q1` and `q2` are `'R'` or `'L'`
that indicate the qubits undergoing the fusion (`'R'` for a root
qubit and `'L'` for a leaf qubit), and `cl1` and `cl2` are the
Clifford gates applied to the qubits before the fusion is
performed.
`fusions[i]` for a positive integer `i` is a list of such 2-tuples,
which indicate fusions that can be done in parallel in the `i`-th
step.
qubit_correspondence : dict
Dictionary that contains the correspondence between the vertices in
the original graph and the final remaining qubits after performing
all the fusions.
For each name (say, `vname`) of a vertex in the original graph,
`qubit_correspondence[vname]` is a 3-tuple `(node, qubit, cl)`,
where `node` is the node containing the qubit, `qubit` is either
`'R'` or `'L'` that indicates whether the qubit is a root or leaf
qubit, and `cl` is the Clifford gate applied to the qubit.
"""
network = self.fusion_network
# Fusions
fusions = {}
orders = network.es['order']
num_steps = max(orders)
for order in range(1, num_steps + 1):
inst_same_order = []
links = network.es.select(order=order)
for link in links:
nname1 = link.source_vertex['name']
nname2 = link.target_vertex['name']
kind = link['kind']
if kind == 'RR':
qubit1 = qubit2 = 'R'
elif kind == 'LL':
qubit1 = qubit2 = 'L'
else:
root_node = link['root_node']
qubit1 = 'R' if root_node == nname1 else 'L'
qubit2 = 'L' if qubit1 == 'R' else 'R'
cliffords = link['cliffords']
try:
cl1 = cliffords[nname1]
except KeyError:
cl1 = None
try:
cl2 = cliffords[nname2]
except KeyError:
cl2 = None
inst_same_order.append(((nname1, qubit1, cl1),
(nname2, qubit2, cl2)))
fusions[order] = inst_same_order
# Final remaining qubits & Clifford gates on them
qubit_correspondence = {}
remaining_leaves = {}
for vname in self.graph.vs['name']:
v_unrv: ig.Vertex = self.unraveled_graph.vs.find(name=vname)
cl = v_unrv['clifford']
if v_unrv.degree() > 1:
corr = (vname, 'R', cl)
else:
v_ngh_unrv = v_unrv.neighbors()[0]
seed_node_name = v_ngh_unrv['name']
try:
remaining_leaves_curr \
= remaining_leaves[seed_node_name]
except KeyError:
node_group \
= network.vs.select(node_group=seed_node_name)
remaining_leaves_curr = {}
for node in node_group:
num_remaining_leaves = 2
for link in node.incident():
kind = link['kind']
if kind == 'LL' \
or (kind == 'RL'
and link['root_node'] != node['name']):
num_remaining_leaves -= 1
remaining_leaves_curr[node['name']] \
= num_remaining_leaves
remaining_leaves[seed_node_name] = remaining_leaves_curr
corr = None
for node_name, num_remaining_leaves in remaining_leaves_curr.items():
if num_remaining_leaves:
corr = (node_name, 'L', cl)
remaining_leaves_curr[node_name] -= 1
assert corr is not None
qubit_correspondence[vname] = corr
node_names = network.vs['name']
return node_names, fusions, qubit_correspondence
def get_vertex_clifford(self, vertex, unraveled=True):
"""
Get the Clifford gate applied to a vertex in the unraveled graph
(by default) or the original graph.
Each Clifford gate is represented by a string. For example,
- `'RX'`: pi/2 X-rotation
- `'RXd'`: -pi/2 X-rotation
- `'RZ'`: pi/2 Z-rotation
- `'RZd'`: -pi/2 Z-rotation
('d' means dagger)
If a qubit is subjected to pi/2 X-rotation followed by pi/2
Z-rotation, it is represented by `'RX-RZ'`.
Parameters
----------
vertex : int or str
Name of the vertex.
unraveled : bool (default: True)
Whether to find the vertex in the unraveled or original graph.
Returns
-------
clifford : None or str
Clifford gate applied to the vertex.
"""
graph = self.unraveled_graph if unraveled else self.graph
if 'clifford' in graph.vertex_attributes():
cl = graph.vs.find(name=str(vertex))['clifford']
return cl
else:
return None
def get_link_clifford(self, n1, n2):
"""
Get the Clifford gates that need to be applied to two qubits involved
in the fusion of a given link.
Each Clifford gate is represented by a string. For example,
- `'RX'`: pi/2 X-rotation
- `'RXd'`: -pi/2 X-rotation
- `'RZ'`: pi/2 Z-rotation
- `'RZd'`: -pi/2 Z-rotation
('d' means dagger)
If a qubit is subjected to pi/2 X-rotation followed by pi/2
Z-rotation, it is represented by `'RX-RZ'`.
Parameters
----------
n1, n2 : int or str
Names of the nodes connected by the link.
Returns
-------
cl1, cl2 : None or str
Clifford gates applied on the two qubits involved in the fusion
of the link.
"""
network = self.fusion_network
n1 = str(n1)
n2 = str(n2)
link = network.es[network.get_eid(n1, n2)]
cliffords = link['cliffords']
cls = []
for n in [n1, n2]:
try:
cls.append(cliffords[n])
except KeyError:
cls.append(None)
return tuple(cls)
def plot_graph(self, unraveled=False, **kwargs):
"""
Plot the original or unraveled graph.
If the unraveled graph is plotted, edges in the unraveled graph are
drawn as black solid lines while external fusions are drawn as red
dashed lines (by default).
Vertices with Clifford gates are colored in orange (by default).
These Clifford gates can be obtained by using
`GraphState.get_vertex_clifford()`.
Parameters
----------
unraveled : bool (default: False)
Whether to plot the unraveled graph or the original graph.
ax : None or matplotlib Axes object (default: None)
If given, the figure is plotted on the given `Axes` object.
layout : str (default: 'auto')
Layout algorithm for plotting.
See https://python.igraph.org/en/stable/tutorial.html#layouts-and-plotting
figsize : 2-tuple of float (default: (5, 5))
Size of the figure in inches.
save : None or str (default: None)
Path to save the figure.
show_vertex_names : bool (default: True)
If `True`, vertex names are shown.
vertex_color_normal : str (default: 'white')
Color of vertices without Clifford gates.
vertex_color_clifford : str (default: 'orange')
Color of vertices with Clifford gates.
vertices_to_highlight : None or list of {str or int} (default: None)
Name of vertices to highlight.
vertex_color_highlight : str (default: purple)
Color of the highlighted vertices.
Ignored if `vertices_to_highlight` is `None`.
edge_color_normal : str (default: black)
Color of edges in the graph.
edge_color_fusion : str (default: red)
Color of lines for external fusions.
Ignored if `unraveled` is `False`.
edge_style_fusion : str (default: '--')
Style of lines for external fusions.
Any other keyword arguments in `igraph.plot()` can be directly used.
See https://python.igraph.org/en/stable/tutorial.html#layouts-and-plotting
If they are given, they override the above parameters.
Returns
-------
fig, ax : matplotlib Figure and Axes object.
"""
graph = self.unraveled_graph if unraveled else self.graph
if graph is None:
raise ValueError("No unraveled graph created.")
fig, ax = plot_graph(graph, **kwargs)
return fig, ax
def plot_fusion_network(self, **kwargs):
"""
Plot the fusion network.
Links have different styles and colors depending on their types:
- 'LL': Black solid line.
- 'RR': Red dashed line.
- 'RL': Blue arrow from leaf to root.
The number placed on each link indicates the order of the fusion. It is
presented only when the resource overhead has been computed beforehand.
Links with `'C'` written on them indicate fusions accompanied by
non-trivial Clifford gates. These Clifford gates can be obtained by
using `GraphState.get_link_clifford()`.
Parameters
----------
ax : None or matplotlib Axes object (default: None)
If given, the figure is plotted on the given `Axes` object.
layout : str (default: 'auto')
Layout algorithm for plotting.<br>
See https://python.igraph.org/en/stable/tutorial.html#layouts-and-plotting
figsize : 2-tuple of float (default: (5, 5))
Size of the figure in inches.
save : None or str (default: None)
Path to save the figure.
show_only_structure : bool (default: False)
If `True`, show only the network structure without any labels,
ignoring the values of parameters `show_node_names`, `show_link_names`,
`show_fusion_orders`, and `show_link_cliffords`.
show_node_names : bool (default: True)
If `True`, node names are shown.
node_color : str (default: 'white')
Color of nodes.
show_link_names : bool (default: False)
If `True`, link names are shown.
show_fusion_orders : bool (default: True)
If `True`, fusion orders are shown on links.
If both `show_link_names` and `show_fusion_orders` are `True`,
it is shown as `'{link name}-{fusion order}'`
show_link_cliffords : bool (default: True)
If `True`, links that correspond to fusions accompanied by
non-trivial Clifford gates are marked as `'C'`.
If `show_link_names` or `show_fusion_orders` are `True`, `'C'` is
appended to the end of the label.
link_color_ll : str (default: 'black')
Color of leaf-to-leaf links.
link_color_rl : str (default: 'blue')
Color of root-to-leaf links.
link_color_rr : str (default: 'red')
Color of root-to-root links.
arrow_size : float (default: 0.02)
Size of arrows for root-to-leaf links.
Any other keyword arguments in igraph.plot can be directly used.<br>
See https://python.igraph.org/en/stable/tutorial.html#layouts-and-plotting <br>
If they are given, they override the above parameters.<br>
Returns
-------
fig, ax : matplotlib Figure and Axes object.
"""
network = self.fusion_network
if network is None:
raise ValueError('No fusion network created.')
fig, ax = plot_fusion_network(network, **kwargs)
return fig, ax
def copy(self):
"""
Return a **shallow** copy of this object.
Use `copy.deepcopy()` to get a deep copy.
Returns
-------
copy : GraphState
Copied instance of itself.
"""
copy = GraphState(graph=self.graph,
unraveled_graph=self.unraveled_graph,
fusion_network=self.fusion_network)
copy.data = self.data.copy()
return copy
def _simulate_single(n_iter, seed, graph, **kwargs):
ogs = GraphState(graph=graph)
res = ogs.simulate(n_iter=n_iter, seed=seed, verbose=False, **kwargs)
res['best_gs'] = ogs
return resSub-modules
optgraphstate.graph_toolsoptgraphstate.utilsoptgraphstate.visualization
Classes
class GraphState (graph=None, edges=None, shape=None, prms=None, cliffords=None, unraveled_graph=None, fusion_network=None)-
Class for calculating and optimizing the resource overhead of the fusion-based generation of a graph state.
The graph of the graph state can be given by the following three ways:
- Given explicitly by
igraph.Graphornetworkx.Graph. - Given by a list of edges.
- Chosen among predefined graphs.
Parameters
graph:Noneorigraph.Graphornetworkx.Graph (default: None)-
Graph of the concerned graph.
If it is given,
edges,shape, andprmsare ignored.If it is
networkx.Graph, it is internally converted toigraph.Graph. edges:Noneorlistof2-tupleofint (default: None)-
List of edges that form the concerned graph.
Each integer in the tuples indicates a vertex label.
If it is given and
graphisNone,shapeandprmsare ignored. shape:Noneorstr (default: None)-
Shape of the concerned graph chosen among predefined graphs.
One of
[None, 'random', 'complete', 'star', 'linear', 'cycle', 'lattice', 'tree', 'rhg', 'repeater', 'parity_encoding', 'ptqc'].shape='random': Random graph for fixed numbers of vertices and edges, sampled by the Erdös-Renyi model.prms[0]<int> : Number of vertices.prms[1]<int> : Number of edges.- [Optional]
prms[2]<Noneorint> : Random seed. IfNone, the current system time is used as the seed. If not given, the random number generator is not initialized.
shape='complete','star','linear', or'cycle': Complete, star, linear, or cycle graph, respectively.prms[0]<int> : Number of vertices.
shape='lattice': Lattice graph.prms<tupleofint> : Numbers of repeated vertices along the axes. The dimension of the lattice is automatically set aslen(prms).
shape='tree': Tree graph where all branches in each generation have an equal number of children.prms[0]<int> : Degree of the root vertex.prms[i](<int>, i >= 1) : Number of the children of eachith-generation branch.
shape='rhg': Raussendorf-Harrington-Goyal lattice with primal boundaries only.prms[0],prms[1],prms[2]<int> : Size of the lattice along the three axes in the unit of a cell.
shape='repeater': Repeater graph with 4m vertices.prms[0]<int> : Parameter m.
shape='parity_encoding': (n, m) parity-encoded graph, where each vertex of the logical graph corresponds to a qubit encoded in the basis of either {(|0>^m + |1>^m)^n +- (|0>^m - |1>^m)^n} (Orientation 1) or {[(|0> + |1>)^m +- (|0> - |1>)^m]^n} (Orientation 2).prms[0]<strorigraph.Graph> : Logical-level graph given by either its name or graph structure. Currently 3-star ("3-star"or"3-linear") and 6-cycle ("6-cycle"or"6-ring") graphs can be given by their names. For the other graphs, it should be given by anigraph.Graphobject. It can be generated directly via python-igraph library or from the functionget_graph_from_edges()orget_sample_graph().prms[1],prms[2]<int> : Parameters n and m of the parity encoding.- [Optional]
prms[3]<bool> : Orientation of the parity encoding. IfTrue(default), "Orientation 1" is used. IfFalse, "Orientation 2" is used.
shape='ptqc': Microcluster for parity-encoding-based topological quantum computing protocol.prms[0],prms[1]<int> : Parameter n and m of the parity encoding.prms[2]<bool> : Whether the H-configuration is HIC (True) or HIS (False).prms[3]<bool> : Whether the microcluster is central (True) or side (False) one.
prms:Noneortupleorint (default: None)-
Parameters for a predefined graph.
See the description for parameter
shape.If only one parameter is required, it can be given as a number, not a tuple.
cliffords:Noneorlistofstr (default: None)-
Local Clifford gates applied on the qubits of the graph state.
If it is
None, no Clifford gates are applied on the qubits.If it is a
listofstr, its length should be equal to the number of vertices in the graph. Its i-th element indicates the Clifford gate applied on the i-th qubit. For example, if it is'H', it means that a Hadamard gate is applied on the qubit. If it is'H-S-Z', it means that Hadamard, phase, and Z gates are applied in order. unraveled_graph:Noneorigraph.Graphornetworkx.Graph (default: None)-
Pregiven unraveled graph.
The code does not check the validity of the given unraveled graph.
If it is
networkx.Graph, it is internally converted toigraph.Graph. fusion_network:Noneorigraph.Graphornetworkx.Graph (default: None)-
Pregiven fusion network.
The code does not check the validity of the given fusion network.
If it is
networkx.Graph, it is internally converted toigraph.Graph.
Expand source code
class GraphState: #: Graph of the graph state to investigate. #: See Sec. 7 of our [tutorial](https://github.com/seokhyung-lee/OptGraphState/raw/main/tutorials.pdf) for the list of its vertex attributes. graph: ig.Graph #: Unraveled graph generated by unraveling the original graph/ #: #: It is `None` before the unraveled graph is created. #: See Sec. 7 of our [tutorial](https://github.com/seokhyung-lee/OptGraphState/raw/main/tutorials.pdf) for the list of its vertex attributes. unraveled_graph: ig.Graph #: Fuson network constructed from the unraveled or original graph. #: #: It is `None` before the fusion network is created. #: See Sec. 7 of our [tutorial](https://github.com/seokhyung-lee/OptGraphState/raw/main/tutorials.pdf) for the list of its vertex and edge #: attributes. fusion_network: ig.Graph #: Any data obtained during unraveling the graph, constructing the fusion #: network, and calculating the resource overhead. data: dict def __init__(self, graph=None, edges=None, shape=None, prms=None, cliffords=None, unraveled_graph=None, fusion_network=None): """ Class for calculating and optimizing the resource overhead of the fusion-based generation of a graph state. The graph of the graph state can be given by the following three ways: 1. Given explicitly by [`igraph.Graph`](https://python.igraph.org/en/stable/api/igraph.Graph.html) or [`networkx.Graph`](https://networkx.org/documentation/stable/reference/classes/graph.html). 2. Given by a list of edges. 3. Chosen among predefined graphs. Parameters ---------- graph : None or igraph.Graph or networkx.Graph (default: None) Graph of the concerned graph. If it is given, `edges`, `shape`, and `prms` are ignored. If it is `networkx.Graph`, it is internally converted to `igraph.Graph`. edges : None or list of 2-tuple of int (default: None) List of edges that form the concerned graph. Each integer in the tuples indicates a vertex label. If it is given and `graph` is `None`, `shape` and `prms` are ignored. shape : None or str (default: None) Shape of the concerned graph chosen among predefined graphs. One of `[None, 'random', 'complete', 'star', 'linear', 'cycle', 'lattice', 'tree', 'rhg', 'repeater', 'parity_encoding', 'ptqc']`. - `shape='random'` : Random graph for fixed numbers of vertices and edges, sampled by the Erdös-Renyi model. - `prms[0]` <`int`> : Number of vertices. - `prms[1]` <`int`> : Number of edges. - [Optional] `prms[2]` <`None` or `int`> : Random seed. If `None`, the current system time is used as the seed. If not given, the random number generator is not initialized. - `shape='complete'`, `'star'`, `'linear'`, or `'cycle'` : Complete, star, linear, or cycle graph, respectively. - `prms[0]` <`int`> : Number of vertices. - `shape='lattice'` : Lattice graph. - `prms` <`tuple` of `int`> : Numbers of repeated vertices along the axes. The dimension of the lattice is automatically set as `len(prms)`. - `shape='tree'` : Tree graph where all branches in each generation have an equal number of children. - `prms[0]` <`int`> : Degree of the root vertex. - `prms[i]` (<`int`>, i >= 1) : Number of the children of each `i`th-generation branch. - `shape='rhg'` : Raussendorf-Harrington-Goyal lattice with primal boundaries only. - `prms[0]`, `prms[1]`, `prms[2]` <`int`> : Size of the lattice along the three axes in the unit of a cell. - `shape='repeater'` : Repeater graph with 4m vertices. - `prms[0]` <`int`> : Parameter m. - `shape='parity_encoding'` : (n, m) parity-encoded graph, where each vertex of the logical graph corresponds to a qubit encoded in the basis of either {(|0>^m + |1>^m)^n +- (|0>^m - |1>^m)^n} (Orientation 1) or {[(|0> + |1>)^m +- (|0> - |1>)^m]^n} (Orientation 2). - `prms[0]` <`str` or `igraph.Graph`> : Logical-level graph given by either its name or graph structure. Currently 3-star (`"3-star"` or `"3-linear"`) and 6-cycle (`"6-cycle"` or `"6-ring"`) graphs can be given by their names. For the other graphs, it should be given by an `igraph.Graph` object. It can be generated directly via python-igraph library or from the function `optgraphstate.graph_tools.get_graph_from_edges()` or `optgraphstate.graph_tools.get_sample_graph()`. - `prms[1]`, `prms[2]` <`int`> : Parameters n and m of the parity encoding. - [Optional] `prms[3]` <`bool`> : Orientation of the parity encoding. If `True` (default), "Orientation 1" is used. If `False`, "Orientation 2" is used. - `shape='ptqc'` : Microcluster for parity-encoding-based topological quantum computing protocol. - `prms[0]`, `prms[1]` <`int`> : Parameter n and m of the parity encoding. - `prms[2]` <`bool`> : Whether the H-configuration is HIC (`True`) or HIS (`False`). - `prms[3]` <`bool`> : Whether the microcluster is central (`True`) or side (`False`) one. prms : None or tuple or int (default: None) Parameters for a predefined graph. See the description for parameter `shape`. If only one parameter is required, it can be given as a number, not a tuple. cliffords : None or list of str (default: None) Local Clifford gates applied on the qubits of the graph state. If it is `None`, no Clifford gates are applied on the qubits. If it is a `list` of `str`, its length should be equal to the number of vertices in the graph. Its i-th element indicates the Clifford gate applied on the i-th qubit. For example, if it is `'H'`, it means that a Hadamard gate is applied on the qubit. If it is `'H-S-Z'`, it means that Hadamard, phase, and Z gates are applied in order. unraveled_graph : None or igraph.Graph or networkx.Graph (default: None) Pregiven unraveled graph. The code does not check the validity of the given unraveled graph. If it is [`networkx.Graph`](https://networkx.org/documentation/stable/reference/classes/graph.html), it is internally converted to [`igraph.Graph`](https://python.igraph.org/en/stable/api/igraph.Graph.html). fusion_network : None or igraph.Graph or networkx.Graph (default: None) Pregiven fusion network. The code does not check the validity of the given fusion network. If it is [`networkx.Graph`](https://networkx.org/documentation/stable/reference/classes/graph.html), it is internally converted to [`igraph.Graph`](https://python.igraph.org/en/stable/api/igraph.Graph.html). """ def convert_type(g, varname): if g is None: return None elif isinstance(g, ig.Graph): return g elif isinstance(g, nx.Graph): return ig.Graph.from_networkx(g) else: raise TypeError(f'Parameter {varname} should be igraph.Graph ' f'or networkx.Graph.') if graph is not None: self.graph = convert_type(graph, 'graph') elif edges is not None: self.graph = ig.Graph(edges=edges) elif shape is not None: try: prms[0] except TypeError: prms = (prms,) self.graph = get_sample_graph(shape, *prms) else: raise ValueError( "At least one of graph, edges, and shape should be given.") self.graph.vs['name'] = [str(vid) for vid in range(self.graph.vcount())] if cliffords is not None and edges is None: self.graph.vs['clifford'] = cliffords self.unraveled_graph = convert_type(unraveled_graph, 'unraveled_graph') self.fusion_network = convert_type(fusion_network, 'fusion_network') self.data = {} def initialize(self): """ Initialize the created unraveled graph and fusion network and the calculation data. """ self.unraveled_graph = None self.fusion_network = None self.data = {} def unravel_graph(self, unravel_bcs_first='random', plot=False, verbose=False): """ Unravel bipartitely-complete subgraphs (BCSs) and cliques of the graph. The unraveled graph is saved in `self.unraveled_graph` as [`igraph.Graph`](https://python.igraph.org/en/stable/api/igraph.Graph.html). Parameters ---------- unravel_bcs_first : one of [True, False, 'random'] (default: 'random') - `True`: BCSs are unraveled first, then clqiues are unraveled. - `False`: cliques are unraveled first, then BCSs are unraveled.<br> - `'random'`: the order is randomly chosen. plot : bool (default: False) Whether to plot the unraveled graph after unraveling. verbose : bool (default: False) Whether to print logs and plot the intermediate graphs during the unraveling process. Returns ------- bcss : list of list of 2-tuple of list of str Information on the unraveled BCSs. `bcss[i][j][k][l]` (`k`=0 or 1) is the name of the `l`-th vertex in the `k`-th part of the `j`-th BCS obtained by the `i`-th cycle of finding non-overlapping BCSs. cliques : list of list of set of str Information on the unraveled cliques. `cliques[i][j]` is the set of the names of the vertices in the `j`-th clique obtained by the `i`-th cycle of finding non-overlapping cliques. unravel_bcs_first : bool Whether BCSs are unraveled first or not. """ if unravel_bcs_first == 'random': unravel_bcs_first = np.random.choice([True, False]) if unravel_bcs_first: bcss = self.unravel_bcss(verbose=verbose) cliques = self.unravel_cliques(verbose=verbose) else: cliques = self.unravel_cliques(verbose=verbose) bcss = self.unravel_bcss(verbose=verbose) if plot or verbose: if verbose: print('[Final]') self.plot_graph(unraveled=True) plt.show() self.data['unravel'] = True self.data['unravel_bcs_first'] = unravel_bcs_first return bcss, cliques, unravel_bcs_first def unravel_bcss(self, verbose=False): """ Unravel bipartitely-complete subgraphs (BCSs) of the graph. The unraveled graph is saved in `GraphState.unraveled_graph` as [`igraph.Graph`](https://python.igraph.org/en/stable/api/igraph.Graph.html). Parameters ---------- verbose : bool (default: False) Whether to print logs and plot the intermediate graphs during the unraveling process. Returns ------- bcss : list of list of 2-tuple of list of str Information on the unraveled BCSs. `bcss[i][j][k][l]` (`k`=0 or 1) is the name of the `l`-th vertex in the `k`-th part of the `j`-th BCS obtained by the `i`-th cycle of finding non-overlapping BCSs. """ if self.unraveled_graph is None: self.unraveled_graph = self.graph.copy() graph = self.unraveled_graph vs_attrs = graph.vs.attributes() if 'ext_fusion' not in vs_attrs: graph.vs['ext_fusion'] = None if 'clifford' not in vs_attrs: graph.vs['clifford'] = None unraveled_bcss = [] new_vertex_name = graph.vcount() while True: # Repeat until there are no bipartitely-complete subgraphs bcs_exist = False while True: bcss = find_nonoverlapping_bcss(graph, get_name=True) if bcss: bcs_exist = True else: break unraveled_bcss.append(bcss) eids_to_remove = [] for part1, part2 in bcss: if verbose: graph.delete_edges(eids_to_remove) eids_to_remove.clear() print('bcs to unravel =', part1, '&', part2) vertex_color = [] for v in graph.vs: if v['name'] in part1: vertex_color.append('orange') elif v['name'] in part2: vertex_color.append('blue') else: vertex_color.append('white') self.plot_graph(unraveled=True, vertex_color=vertex_color) plt.show() eids_to_remove.extend([graph.get_eid(vname1, vname2) for vname1, vname2 in itertools.product(part1, part2)]) vname1 = str(new_vertex_name) vname2 = str(new_vertex_name + 1) new_v1 = graph.add_vertex(name=vname1, ext_fusion=vname2, clifford=None) new_v2 = graph.add_vertex(name=vname2, ext_fusion=vname1, clifford=None) new_vertex_name += 2 graph.add_edges(itertools.product([new_v1], part1)) graph.add_edges(itertools.product([new_v2], part2)) graph.delete_edges(eids_to_remove) if not bcs_exist: break return unraveled_bcss def unravel_cliques(self, verbose=False): """ Unravel cliques of the graph. The unraveled graph is saved in `GraphState.unraveled_graph` as [`igraph.Graph`](https://python.igraph.org/en/stable/api/igraph.Graph.html). Parameters ---------- verbose : bool (default: False) Whether to print logs and plot the intermediate graphs during the unraveling process. Returns ------- cliques : list of list of set of str Information on the unraveled cliques. `cliques[i][j]` is the set of the names of the vertices in the `j`-th clique obtained by the `i`-th cycle of finding non-overlapping cliques. """ if self.unraveled_graph is None: self.unraveled_graph = self.graph.copy() graph = self.unraveled_graph vs_attrs = graph.vs.attributes() if 'ext_fusion' not in vs_attrs: graph.vs['ext_fusion'] = None if 'clifford' not in vs_attrs: graph.vs['clifford'] = None unraveled_cliques = [] def apply_clifford(v, clifford): org_clifford = v['clifford'] if org_clifford is None: new_clifford = clifford else: new_clifford = '-'.join([clifford, org_clifford]) v['clifford'] = new_clifford while True: cliques = find_nonoverlapping_cliques(graph, get_name=True) if not cliques: break unraveled_cliques.append(cliques) for clique in cliques: if verbose: print('clique to unravel =', clique) vertex_color = ['orange' if vname in clique else 'white' for vname in graph.vs['name']] self.plot_graph(unraveled=True, vertex_color=vertex_color) plt.show() clique = list(clique) clique_size = len(clique) # Choose a vertex to apply LC degrees = graph.degree(clique) min_degree = min(degrees) if min_degree == clique_size - 1: # There exists a vertex in the clique that doesn't have # outer edges vname_LC = [vname for vname, deg in zip(clique, degrees) if deg == min_degree] need_to_separate = False else: vname_LC = clique need_to_separate = True if len(vname_LC) > 1: vname_LC = np.random.choice(vname_LC) else: vname_LC = vname_LC[0] old_v_LC = graph.vs.find(name=vname_LC) # Separate the edges (E) incident to v_LC outside the clique # from v_LC eids_to_delete = [] if need_to_separate: # Alter v_LC old_v_LC['name'] = str(graph.vcount()) new_v_LC = graph.add_vertex( name=vname_LC, clifford=old_v_LC['clifford'], ext_fusion=old_v_LC['ext_fusion'] ) # Vertex having an external fusion with old v_LC v_ext_fusion = graph.add_vertex( name=str(graph.vcount()), clifford=None, ext_fusion=old_v_LC['name'] ) # Modify old v_LC old_v_LC['clifford'] = None old_v_LC['ext_fusion'] = v_ext_fusion['name'] graph.add_edge(new_v_LC, v_ext_fusion) old_vid_LC = old_v_LC.index ngh_vids = graph.neighbors(old_vid_LC) for ngh_vid in ngh_vids: if graph.vs[ngh_vid]['name'] not in clique: graph.add_edge(ngh_vid, new_v_LC.index) eids_to_delete.append( graph.get_eid(old_vid_LC, ngh_vid) ) # Remove edges adj_vnames = set(clique) - {vname_LC} new_eids_to_delete = [graph.get_eid(vname1, vname2) for vname1, vname2 in itertools.combinations(adj_vnames, r=2)] eids_to_delete.extend(new_eids_to_delete) graph.delete_edges(eids_to_delete) # Apply LC apply_clifford(old_v_LC, 'RXd') for adj_vname in adj_vnames: adj_v = graph.vs.find(name=adj_vname) apply_clifford(adj_v, 'RZ') return unraveled_cliques def build_fusion_network(self, use_unraveled_graph=True, plot=False, verbose=False): """ Build a fusion network from the original graph or unraveled graph. If you want to build it from the unraveled graph, at least one of `GraphState.unravel_graph()`, `GraphState.unravel_bcss()`, and `GraphState.unravel_cliques()` must be executed beforehand. The constructed fusion network is saved in `GraphState.fusion_network` as [`igraph.Graph`](https://python.igraph.org/en/stable/api/igraph.Graph.html). Parameters ---------- use_unraveled_graph : bool (default: True) Whether to use the unraveled graph or the original graph for building a fusion network. plot : bool (default: False) Whether to plot the fusion network after building it. verbose : bool (default: False) Whether to print logs. """ graph = self.unraveled_graph if use_unraveled_graph else self.graph if graph is None: raise ValueError("No unraveled qubit graph created.") # Fusion network network = ig.Graph() self.fusion_network = network node_groups = {} # Links inside star graphs for v in graph.vs: num_internal_nodes = v.degree() - 1 vname = v['name'] if num_internal_nodes >= 1: # Add nodes nid_init = network.vcount() seed = np.random.randint(0, num_internal_nodes) node_names = [vname if i == 0 else f'{vname}-{i}' for i in itertools.chain(range(seed, -1, -1), range(seed + 1, num_internal_nodes))] attr = { 'name': node_names, 'seed': [True if i == seed else False for i in range(num_internal_nodes)], 'node_group': vname, # 'clifford_root': None, # 'clifford_leaves': None } network.add_vertices(num_internal_nodes, attributes=attr) node_groups[vname] \ = network.vs[nid_init:nid_init + num_internal_nodes] if num_internal_nodes >= 2: # Connect internal links links = [(nid, nid + 1) for nid in range(nid_init, nid_init + num_internal_nodes - 1)] attr = { 'kind': "RL", 'root_node': [ node_names[i] if i < seed else node_names[i + 1] for i in range(num_internal_nodes - 1)], 'cliffords': {} } network.add_edges(links, attributes=attr) # Links between star graphs for e in graph.es: vs = [e.source_vertex, e.target_vertex] deg_vs = graph.degree(vs) if deg_vs[0] > 1 and deg_vs[1] > 1: nodes_to_connect = [] for v in vs: vname = v['name'] nodes = node_groups[vname].select( lambda node: node.degree() < (2 if node['seed'] else 3) ) nodes_to_connect.append(np.random.choice(nodes)) network.add_edge(*nodes_to_connect, kind='LL', root_node=None, cliffords={}) if verbose: print("Fusion network of the unraveled graph:") self.plot_fusion_network() plt.show() # Set of seed node names where root vertices are connected by # external fusions. nnames_root_connected = set() is_node_not_full = lambda node: node.degree() < ( 2 if node['seed'] and ( node['name'] not in nnames_root_connected) else 3) def get_nodes_containing_vertex(vname): try: node = node_groups[vname].find(name=vname) is_root = True seed_node_name = vname except KeyError: ngh = graph.vs[graph.neighbors(vname)[0]] seed_node_name = ngh['name'] nodes = node_groups[seed_node_name].select(is_node_not_full) node = np.random.choice(nodes) is_root = False return node, is_root, seed_node_name vs_attrs = graph.vs.attributes() # Links by external fusions if 'ext_fusion' in vs_attrs: vnames_to_skip = set() for v1 in graph.vs.select(ext_fusion_ne=None): vname1 = v1['name'] if vname1 in vnames_to_skip: continue vname2 = v1['ext_fusion'] v2 = graph.vs.find(name=vname2) vnames_to_skip.add(vname2) node1, is_root1, _ = get_nodes_containing_vertex(vname1) node2, is_root2, _ = get_nodes_containing_vertex(vname2) if is_root1 and is_root2: kind = 'RR' root_node = None nnames_root_connected.add(node1['name']) nnames_root_connected.add(node2['name']) elif not is_root1 and not is_root2: kind = 'LL' root_node = None else: kind = 'RL' root_node = node1['name'] if is_root1 else node2['name'] nnames_root_connected.add(root_node) cliffords = {} cl1 = v1['clifford'] cl2 = v2['clifford'] for node, cl in zip([node1, node2], [cl1, cl2]): if cl is not None: cliffords[node['name']] = cl network.add_edge(node1, node2, kind=kind, root_node=root_node, cliffords=cliffords) network.es['name'] = [str(eid) for eid in range(network.ecount())] if verbose: print("Add external fusions:") self.plot_fusion_network() plt.show() # Clifford gates on surviving qubits # if 'clifford' in vs_attrs: # cls_in_node_group_leaves = {} # for v_cl in graph.vs.select(clifford_ne=None, ext_fusion=None): # vname = v_cl['name'] # _, is_root, seed_node_name = get_nodes_containing_vertex(vname) # seed_node = network.vs.find(name=seed_node_name) # cl = v_cl['clifford'] # # if is_root: # if seed_node_name not in nnames_root_connected: # seed_node['clifford_root'] = cl # # else: # try: # cls_in_node_group_leaves[seed_node_name].append(cl) # except KeyError: # cls_in_node_group_leaves[seed_node_name] = [cl] # # for seed_node_name, cls in cls_in_node_group_leaves.items(): # node_group = node_groups[seed_node_name] # nums_surviving_leaves = [] # for node in node_group: # if node['name'] in nnames_root_connected: # num_surviving_leaves = 3 - node.degree() # else: # num_surviving_leaves = 2 - node.degree() # nums_surviving_leaves.append(num_surviving_leaves) # total_num_surviving_leaves = sum(nums_surviving_leaves) # # if len(cls) < total_num_surviving_leaves: # cls.extend([None] # * (total_num_surviving_leaves - len(cls))) # np.random.shuffle(cls) # # i_start = 0 # for node, num_leaves in zip(node_group, nums_surviving_leaves): # cls_current_node = cls[i_start:i_start + num_leaves] # cls_current_node = [cl for cl in cls_current_node # if cl is not None] # node['clifford_leaves'] = cls_current_node # i_start += num_leaves # if verbose: # print("Apply Clifford gates:") # self.plot_fusion_network() # plt.show() self.fusion_network = network if plot: print("Final:") self.plot_fusion_network() plt.show() def _contract_edge(self, fusion_network: ig.Graph, ename_to_merge, update_weight_and_order=True): ename_to_merge = str(ename_to_merge) e_to_merge = fusion_network.es.find(name=ename_to_merge) v_merged, v_removed \ = e_to_merge.source_vertex, e_to_merge.target_vertex enames_updated_weight = [] if v_merged.degree() < v_removed.degree(): v_merged, v_removed = v_removed, v_merged vname_merged = v_merged['name'] vname_removed = v_removed['name'] if update_weight_and_order: v_merged['weight'] = e_to_merge['weight'] v_merged['weight_f'] = e_to_merge['weight_f'] v_merged['order'] = max(v_merged['order'], v_removed['order']) + 1 assert vname_merged != vname_removed eids_to_delete = list(set(fusion_network.incident(v_removed))) v_removed['on'] = False calculate_ftpdf = 'ftpdf' in fusion_network.vertex_attributes() for eid_connected in eids_to_delete: e_connected: ig.Edge = fusion_network.es[eid_connected] attrs_e_connected = e_connected.attributes() ename_connected = e_connected['name'] if ename_connected != ename_to_merge: enames_updated_weight.append(ename_connected) vs_ngh = e_connected.source_vertex, e_connected.target_vertex new_edge_eps = [v_merged if v_ngh['name'] == vname_removed else v_ngh for v_ngh in vs_ngh] if new_edge_eps[0] == new_edge_eps[1]: # If a loop is formed v_vrt: ig.Vertex = fusion_network.add_vertex( name=f'vrt_{fusion_network.vcount()}', on=True, ) if update_weight_and_order: v_vrt.update_attributes(weight=0, weight_f=0, order=0) if calculate_ftpdf: v_vrt['ftpdf'] = np.array([1]) new_edge_eps = [v_merged, v_vrt] new_edge: ig.Edge = fusion_network.add_edge(*new_edge_eps) new_edge.update_attributes(**attrs_e_connected) fusion_network.delete_edges(eids_to_delete) if update_weight_and_order: p_succ = fusion_network['p_succ'] for eid_connected in list(set(fusion_network.incident(v_merged))): e_connected = fusion_network.es[eid_connected] v_ngh1, v_ngh2 = e_connected.source_vertex, e_connected.target_vertex assert v_ngh1 != v_ngh2 e_connected['weight'] \ = (v_ngh1['weight'] + v_ngh2['weight']) / p_succ e_connected['weight_f'] \ = (v_ngh1['weight_f'] + v_ngh2['weight_f'] + 1) / p_succ self.fusion_network.es.find(name=ename_to_merge)['order'] \ = v_merged['order'] return v_merged, v_removed, enames_updated_weight def calculate_overhead(self, p_succ=0.5, strategy='weight_and_matching', optimize_num_fusions=False, fusion_order=None): """ Calculate the resource overhead (average number of basic resource states required to generate the desired graph state) from the fusion network. `GraphState.build_fusion_network()` must be executed beforehand. The resulting data is saved in `GraphState.data`. Parameters ---------- p_succ : float (default: 0.5) Success probability of a fusion. strategy : str, one of ['weight', 'matching', 'weight_and_matching', 'random'] (default: 'weight_and_matching') Strategy for determining the edge to contract. - `'weight'`: Contract a random one among the edges with the smallest weight. - `'matching'`: Contract an edge in a maximum matching. - `'weight_and_matching'`: Contract an edge in a maximum matching of the subgraph of the intermediate fusion network induced by the edges with the smallest weight. - `'random'`: Contract a random edge. optimize_num_fusions : bool If `True`, the average number of required fusion attempts are used to quantify resource overheads instead of the average number of required basic resource states. fusion_order : None or list of {int or str} (default: None) Fusion order given explicitly as vertex names. If it is not `None`, parameter `strategy` is ignored. Returns ------- data : dict Outcomes of the calculation, which is a shallow copy of `GraphState.data`.<br> The calculated overhead and number of steps can be obtained from `data['overhead']` and `data['num_steps']`, respectively. """ if self.fusion_network is None: raise ValueError("No fusion network created") # Trivial cases node_num = self.fusion_network.vcount() if node_num == 0: self.data['overhead'] = 0 self.data['num_fusions'] = 0 self.data['num_steps'] = 0 return self.data elif node_num == 1: self.data['overhead'] = 1 self.data['num_fusions'] = 0 self.data['num_steps'] = 0 return self.data if fusion_order is None: fusion_order = [] is_fusion_order_given = False else: is_fusion_order_given = True self.fusion_network['p_succ'] = p_succ self.fusion_network.es['order'] = None # Initialize intermediate fusion network network = self.fusion_network.copy() network.vs['weight'] = 1 network.vs['weight_f'] = 0 network.vs['order'] = 0 network.vs['on'] = True network.es['weight'] = 2 / p_succ network.es['weight_f'] = 1 / p_succ del network.es['order'] turn = 0 weight_key = 'weight_f' if optimize_num_fusions else 'weight' # Iterate until no edges remain in the fusion network while True: if not network.ecount(): break if is_fusion_order_given: enames_curr_step = [str(fusion_order[turn])] is_parellel = True elif strategy == 'weight': min_weight = min(network.es[weight_key]) eids_min_weight = network.es.select(weight=min_weight) enames_curr_step = eids_min_weight['name'] is_parellel = len(enames_curr_step) == 1 # elif strategy == 'betweenness': # eb = np.array(network.edge_betweenness()) # min_eb = np.min(eb) # eids_curr_step = np.nonzero(eb == min_eb)[0] # enames_curr_step = [network.es[eid]['name'] for eid in # eids_curr_step] # is_parellel = len(enames_curr_step) == 1 # # elif strategy == 'weight_and_betweenness': # min_weight = min(network.es['weight']) # eids_min_weight = network.es.select(weight=min_weight) # es_min_ovh = eids_min_weight # # eb = network.edge_betweenness() # ebs_min_ovh = np.array([eb[e.index] for e in es_min_ovh]) # min_eb = np.min(ebs_min_ovh) # enames_curr_step = [es_min_ovh[i]['name'] for i in # np.nonzero(ebs_min_ovh == min_eb)[0]] # is_parellel = len(enames_curr_step) == 1 elif 'matching' in strategy: if strategy == 'weight_and_matching': min_weight = min(network.es[weight_key]) if optimize_num_fusions: es_min_weight = network.es.select(weight_f=min_weight) else: es_min_weight = network.es.select(weight=min_weight) subnetwork = network.subgraph_edges(es_min_weight) else: subnetwork = network subnetwork_nx = subnetwork.to_networkx() if isinstance(subnetwork_nx, nx.MultiGraph): subnetwork_nx = nx.Graph(subnetwork_nx) matching = nx.max_weight_matching(subnetwork_nx, weight=None) enames_curr_step = \ subnetwork.es[subnetwork.get_eids(matching)]['name'] is_parellel = True elif strategy == 'random': enames_curr_step = [np.random.choice(network.es['name'])] is_parellel = True else: raise ValueError recalculated_enames = [] # if get_fusion_order and not is_fusion_order_given: # fusion_order_curr_step = set() # fusion_order.append(fusion_order_curr_step) while True: if not is_parellel: for rec_ename in recalculated_enames: try: enames_curr_step.remove(rec_ename) except ValueError: pass if not enames_curr_step: break recalculated_enames.clear() if is_parellel: ename_to_merge = enames_curr_step.pop() else: ename_to_merge = np.random.choice(enames_curr_step) enames_curr_step.remove(ename_to_merge) _, _, enames_updated_weight \ = self._contract_edge(network, ename_to_merge) recalculated_enames.extend(enames_updated_weight) v_final = network.vs.select(on=True) overhead = sum(v_final['weight']) num_fusions = sum(v_final['weight_f']) num_steps = max(v_final['order']) results = { 'overhead': overhead, 'num_fusions': num_fusions, 'num_steps': num_steps, 'fusion_order_strategy': strategy, 'p_succ': p_succ, } if optimize_num_fusions: results['optimize_num_fusions'] = True # if get_fusion_order: # results['fusion_order'] = fusion_order self.data.update(results) return self.data.copy() def calculate_succ_probs(self, cutoff=0.95, auto_increasing_prec=True, prec=30, prec_interval=5, diff_overhead_thrs=0.01): """ Calculate the success probability of the generation of the graph state for each resource count. In other words, get the cumulative mass function (CMF) of the resource count required to generate the state. The success probability is computed while increasing the resource count until the value reaches `cutoff` that is smaller than one. The estimated resource overhead, which is the expectation value of the resource count, is additionally returned. It uses the `decimal` module instead of float64 since the calculation involves the summation of many extremely small numbers thus floating-point errors may be detrimental. By default, it executes the computation multiple times while increasing the precision by 5 starting from 30. When the estimated overhead does not change by more than 1% in two consecutive trials, the iteration is terminated and the results of the final trial are returned. Parameters ---------- cutoff : float (default: 0.95) Cutoff threshold between 0 and 1. auto_increasing_prec : bool (default: True) Whether to execute the computation multiple times. If it is False, the parameters `prec_interval` and `diff_overhead_thrs` are ignored. prec : int (default: 30) Initial precision of numbers. prec_interval : int (default: 5) Interval of precisions between two consecutive trials. diff_overhead_thrs : float (default: 0.01) Threshold of the relative difference between the overheads estimated from two consecutive trials for determining the termination of the iteration. Namely, if the overheads are `o1` and `o2` in order, the iteration terminates when `abs(o1 - o2) / o2 < diff_overhead_thrs`. Returns ------- resource_count_start : int First resource count that gives a nonzero probability. probs : 1D numpy array of decimal.Decimal Success probabilities for the resource counts starting from `resource_count_start`. `probs[i]` is the value corresponding to the resource count of `resource_count_start+i`. overhead : decimal.Decimal Resource overhead estimated by the calculated probabilities. If `cutoff` is close enough to one, this value should not be significantly different from the correct one (`GraphState.data['overhead']`). """ if self.fusion_network is None: raise ValueError("No fusion network created") if 'order' not in self.fusion_network.edge_attributes(): raise ValueError("No fusion order data in the fusion network") if not auto_increasing_prec: network: ig.Graph = self.fusion_network.copy() dec.getcontext().prec = prec for v in network.vs: v['ftpdf'] = np.array([dec.Decimal(0), dec.Decimal(1)]) network.vs['on'] = True p_succ = network['p_succ'] orders = network.es['order'] num_steps = max(orders) for order in range(1, num_steps + 1): enames = network.es.select(order=order)['name'] for ename in enames: link = network.es.find(name=ename) node1, node2 = link.source_vertex, link.target_vertex new_ftpdf = get_ftpdf_contracted(node1['ftpdf'], node2['ftpdf'], p_succ=p_succ) v_merged, _, _ \ = self._contract_edge(network, ename, update_weight_and_order=False) v_merged['ftpdf'] = new_ftpdf ftpdfs_final = network.vs.select(on=True)['ftpdf'] while True: if len(ftpdfs_final) == 1: ftpdf_final = ftpdfs_final[0] break ftpdfs_final.append(scsig.convolve(ftpdfs_final[0], ftpdfs_final[1])) del ftpdfs_final[1], ftpdfs_final[0] resource_count_start, probs \ = recover_cmf_from_ftpdf(ftpdf_final, cutoff) pmf = np.diff(probs) overhead \ = np.sum(pmf * np.arange(resource_count_start, resource_count_start + pmf.size)) else: prev_overhead = None while True: print(f'prec = {prec}: ', end='') try: resource_count_start, probs, overhead \ = self.calculate_succ_probs(cutoff=cutoff, auto_increasing_prec=False, prec=prec) except ValueError: print('Error') prec += prec_interval continue if prev_overhead is not None \ and abs(overhead - prev_overhead) / overhead < diff_overhead_thrs: print(overhead) break print(overhead) prec += prec_interval prev_overhead = overhead return resource_count_start, probs, overhead def simulate(self, n_iter, p_succ=0.5, mp=False, n_procs=None, get_all_data=False, get_all_graphs=False, get_all_fusion_networks=False, unravel=True, unravel_bcs_first='random', fusion_order_strategy='weight_and_matching', optimize_num_fusions=False, seed='keep', verbose=True, pbar=True, **kwargs): """ Execute the strategy for a fixed number of iterations and obtain the best one only (by default). Attributes such as `GraphState.data`, `GraphState.unraveled_graph`, and `GraphState.fusion_network` are updated according to the result of the best sample. Parameters ---------- n_iter : int Iteration number. p_succ : float (default: 0.5) Success probability of a fusion. mp : bool (default: False) Whether to use multiprocessing for the iterations. Package *parmap* should be installed to use it. n_procs : None or int (default: None) Maximal number of simultaneous processes for multiprocessing. If it is `None`, the number of CPUs is used. Ignored when `mp` is `False`. get_all_data : bool (default: False) Whether to obtain the data (overheads, numbers of steps, etc.) from all samples or only the best sample. get_all_graphs : bool (default: False) Whether to obtain the unraveled graphs from all samples or only the best sample. get_all_fusion_networks : bool (default: False) Whether to obtain the fusion networks from all samples or only the best sample. unravel : bool (default: True) Whether to unravel the graph or not. unravel_bcs_first : one of [True, False, 'random'] (default: 'random') - `True`: BCSs are unraveled first, then clqiues are unraveled. - `False`, cliques are unraveled first, then BCSs are unraveled. - `'random'`, the order is randomly chosen. fusion_order_strategy : one of ['weight', 'matching', 'weight_and_matching', 'random'] (default: `weight_and_matching') Strategy for determining the edge to contract in each step. - `'weight'`: Contract a random one among the edges with the smallest weight. - `'matching'`: Contract an edge in a maximum matching. - `'weight_and_matching'`: Contract an edge in a maximum matching of the subgraph of the intermediate fusion network induced by the edges with the smallest weight. - `'random'`: Contract a random edge. optimize_num_fusions : bool (default: False) If `True`, use the average number of fusion attempts to quantify resource overheads instead of the average number of basic resource states. seed : 'keep' or None or int (default: 'keep') Random seed. - `'keep'`: The seed is not initialized. - `None`: The current time is used as the random seed. - `int`: The given number is used as the random seed. If `n_iter>1`, the given seed is used to sample random seeds for individual iterations. However, if `n_iter==1`, the given seed is used as the random seed for the (only one) iteration itself. verbose : bool (default: True) Whether to print logs. pbar : bool (default: True) Whether to show a progress bar. Ignored if tqdm is not installed. kwargs : dict Additional keyword arguments for calculating overheads. See the description of `GraphState.calculate_overhead()`. Returns ------- res : dict Dictionary containing the results of the iterations with keys: - `'best_overhead'`: Overhead of the best sample (i.e., sample with the smallest overhead or avg fusion number, determined by parameter `optimize_num_fusions`). - `'best_num_fusions'`: Average number of fusions of the best sample. - `'best_num_steps'`: Number of steps (i.e., groups of fusions that can be done in parallel) of the best sample. - `'best_seed'`: Random seed for the best sample. To recover the sample from it, use the `seed` parameter of `GraphState.simulate()` with `n_iter=1`. - `'n_iter'`: Number of iterations. Same as parameter `n_iter`. - `'unravel_bcs_first'`: Whether to unravel BCSs or cliques first for the best sample. - `'overheads'`, `'nums_fusions'`, `'nums_steps'`, `'seeds'`: Lists of the overheads, avg fusion numbers, step numbers, and seeds of all samples, respectively. Exist only when `get_all_data==True`. - `'unraveled_graphs'`: List of the unraveled graphs of all samples. Exists only when `get_all_graphs==True`. - `'fusion_networks'`: List of the fusion networks of all samples. Exists only when `get_all_fusion_networks==True`. """ t0 = time.time() overhead_key = 'num_fusions' if optimize_num_fusions else 'overhead' if seed != 'keep': np.random.seed(seed) if mp: if n_procs is None: n_procs = os.cpu_count() mp = mp and n_iter >= n_procs if not mp: if verbose: print("Multiprocessing OFF.") print(f"Calculating for n_iter = {n_iter}...") if 'tqdm' not in sys.modules: pbar = False if verbose: print("Install tqdm package to see the progress bar.") if n_iter == 1 and seed is not None and seed != 'keep': seeds_samples = [seed] else: seeds_samples = np.random.randint(0, _max_seed(), size=n_iter) overheads = [] if get_all_data else None nums_fusions = [] if get_all_data else None nums_steps = [] if get_all_data else None seeds = [] if get_all_data else None unravalled_graphs = [] if get_all_graphs else None fusion_networks = [] if get_all_fusion_networks else None best_sample = None lowest_overhead = None iterable = range(n_iter) if pbar: iterable = tqdm.tqdm(iterable) for i_sample in iterable: seed_sample = seeds_samples[i_sample] np.random.seed(seed_sample) if unravel: self.unraveled_graph = None try: self.unravel_graph(unravel_bcs_first=unravel_bcs_first) except: print('Error occurs during unraveling') print('seed =', seed_sample) raise ValueError try: self.build_fusion_network(use_unraveled_graph=unravel) except: print('Error occurs during building fusion network') print('seed =', seed_sample) raise ValueError try: data_now = self.calculate_overhead( p_succ=p_succ, strategy=fusion_order_strategy, optimize_num_fusions=optimize_num_fusions, **kwargs) except: print('Error occurs during calculating overhead') print('seed =', seed_sample) raise ValueError overhead_now = data_now[overhead_key] num_steps_now = data_now['num_steps'] self.data['seed'] = seed_sample if lowest_overhead is None or overhead_now < lowest_overhead: best_sample = i_sample lowest_overhead = overhead_now best_gs = self.copy() if get_all_data: overheads.append(data_now['overhead']) nums_fusions.append(data_now['num_fusions']) nums_steps.append(num_steps_now) seeds.append(seed_sample) if get_all_graphs: unravalled_graphs.append(self.unraveled_graph) if get_all_fusion_networks: fusion_networks.append(self.fusion_network) res = { 'best_overhead': best_gs.data['overhead'], 'best_num_fusions': best_gs.data['num_fusions'], 'best_num_steps': best_gs.data['num_steps'], 'best_seed': best_gs.data['seed'], 'n_iter': n_iter} if unravel: res['unravel_bcs_first'] = best_gs.data['unravel_bcs_first'] if get_all_data or get_all_graphs or get_all_fusion_networks: res['best_sample'] = best_sample if get_all_data: res['overheads'] = overheads res['nums_fusions'] = nums_fusions res['nums_steps'] = nums_steps res['seeds'] = seeds if get_all_graphs: res['unraveled_graphs'] = unravalled_graphs if get_all_fusion_networks: res['fusion_networks'] = fusion_networks else: if 'parmap' not in sys.modules: raise ModuleNotFoundError("Package parmap is not installed.") if verbose: print(f"Multiprocessing ON: n_procs = {n_procs}") print(f"Calculating for n_iter = {n_iter}... ", end='') additional_keys = [] if get_all_data: additional_keys.extend(['overheads', 'nums_fusions', 'nums_steps', 'seeds']) if get_all_graphs: additional_keys.append('unraveled_graphs') if get_all_fusion_networks: additional_keys.append('fusion_networks') left = n_iter % n_procs ns_samples = [n_iter // n_procs] * n_procs for i in range(left): ns_samples[i] += 1 seeds = np.random.randint(0, _max_seed(), size=n_procs) res_procs = parmap.starmap( _simulate_single, list(zip(ns_samples, seeds)), self.graph, p_succ=p_succ, get_all_data=get_all_data, get_all_graphs=get_all_graphs, get_all_fusion_networks=get_all_fusion_networks, unravel=unravel, unravel_bcs_first=unravel_bcs_first, fusion_order_strategy=fusion_order_strategy, optimize_num_fusions=optimize_num_fusions, pbar=False, pm_pbar=pbar, **kwargs) best_proc = np.argmin( [res_each[f'best_{overhead_key}'] for res_each in res_procs] ) res = res_procs[best_proc] res['n_iter'] = n_iter best_gs = res['best_gs'] del res['best_gs'] if additional_keys: res['best_sample'] += sum(ns_samples[:best_proc]) for key in additional_keys: vals = [res_each[key] for res_each in res_procs] res[key] = list(itertools.chain(*vals)) if verbose: print(f"Done. Best: {res[f'best_{overhead_key}']:.2f} " f"({time.time() - t0:.2f} s)") self.unraveled_graph = best_gs.unraveled_graph self.fusion_network = best_gs.fusion_network self.data = best_gs.data return res def simulate_adaptive(self, init_n_iter, mul=2, p_succ=0.5, mp=False, n_procs=None, get_all_data=False, get_all_graphs=False, get_all_fusion_networks=False, unravel=True, unravel_bcs_first='random', fusion_order_strategy='weight_and_matching', optimize_num_fusions=False, seed='keep', verbose=True, pbar=True, **kwargs): """ Run the adaptive iteration method for the strategy and obtain the best one only (by default). The adaptive iteration method looks for the best iteration while keeps increasing the iteration number until a certain condition meets. In detail, denoting N iterations of the strategy as R(N), R(`init_n_iter`) is first executed and `q0` is obtained which is the lowest resource overhead. Then, R(`mul`*`init_n_iter`) is executed and `q1` is obtained similarly. If `q0 <= q1`, `q0` is returned. If otherwise, R(`mul**2*init_n_iter`) is executed and `q2` is obtained. If `q1 <= q2`, `q1` is returned. If otherwise, R(`mul**3*init_n_iter`) is executed, and so on. Parameters ---------- init_n_iter : int Initial iteration number. mul : int (default: 2) Multiplicative factor of the iteration number. See the description of `GraphState.simulate()` for the other parameters. Returns ------- res : dict Dictionary containing the results of the iterations. See the description of `GraphState.simulate()` for its keys. """ if mp and n_procs is None: n_procs = os.cpu_count() if seed != 'keep': np.random.seed(seed) additional_keys = [] if get_all_data: additional_keys.extend(['overheads', 'nums_fusions', 'nums_steps']) if get_all_graphs: additional_keys.append('unraveled_graphs') if get_all_fusion_networks: additional_keys.append('fusion_networks') if verbose: if mp: print(f"Multiprocessing (n_procs = {n_procs})") else: print("No multiprocessing") best_overhead_key \ = 'best_num_fusions' if optimize_num_fusions else 'best_overhead' n_iter_history = [] n_iter_now = init_n_iter res = None while True: if verbose: print(f"Calculating for n_iter = {n_iter_now}... ", end='') t0 = time.time() n_iter_history.append(n_iter_now) res_now = self.simulate( n_iter=n_iter_now, p_succ=p_succ, mp=mp, n_procs=n_procs, get_all_data=get_all_data, get_all_graphs=get_all_graphs, get_all_fusion_networks=get_all_fusion_networks, unravel=unravel, unravel_bcs_first=unravel_bcs_first, fusion_order_strategy=fusion_order_strategy, optimize_num_fusions=optimize_num_fusions, verbose=False, pbar=pbar, **kwargs ) if res is None: res = res_now best_gs = self.copy() n_iter_now *= mul else: for key in additional_keys: res[key].extend(res_now[key]) if res_now[best_overhead_key] < res[best_overhead_key]: for key in additional_keys: res_now[key] = res[key] res = res_now best_gs = self.copy() n_iter_now *= mul else: if verbose: print(f"Done. Best: {res[best_overhead_key]:.2f} (" f"{time.time() - t0:.2f} s)") break if verbose: print(f"Done. Best: {res[best_overhead_key]:.2f} " f"({time.time() - t0:.2f} s)") res['n_iter'] = sum(n_iter_history) if additional_keys: res['best_sample'] += res['best_sample'] self.unraveled_graph = best_gs.unraveled_graph self.fusion_network = best_gs.fusion_network self.data = best_gs.data return res def get_instructions(self): """ Get the instruction to generate the desired graph state from multiple three-qubit linear graph states. One of `GraphState.calculate_overhead()`, `GraphState.simulate()`, and `GraphState.simulate_adaptive()` must be executed beforehand. Returns ------- node_names : list of str List of the names of nodes in the fusion network. fusions : dict Dictionary that contains the information about required fusions and Clifford gates. Each required fusion is represented by a 2-tuple of 3-tuples: `((n1, q1, cl1), (n2, q2, cl2))`. `n1` and `n2` are the names of the nodes involved in the fusion, `q1` and `q2` are `'R'` or `'L'` that indicate the qubits undergoing the fusion (`'R'` for a root qubit and `'L'` for a leaf qubit), and `cl1` and `cl2` are the Clifford gates applied to the qubits before the fusion is performed. `fusions[i]` for a positive integer `i` is a list of such 2-tuples, which indicate fusions that can be done in parallel in the `i`-th step. qubit_correspondence : dict Dictionary that contains the correspondence between the vertices in the original graph and the final remaining qubits after performing all the fusions. For each name (say, `vname`) of a vertex in the original graph, `qubit_correspondence[vname]` is a 3-tuple `(node, qubit, cl)`, where `node` is the node containing the qubit, `qubit` is either `'R'` or `'L'` that indicates whether the qubit is a root or leaf qubit, and `cl` is the Clifford gate applied to the qubit. """ network = self.fusion_network # Fusions fusions = {} orders = network.es['order'] num_steps = max(orders) for order in range(1, num_steps + 1): inst_same_order = [] links = network.es.select(order=order) for link in links: nname1 = link.source_vertex['name'] nname2 = link.target_vertex['name'] kind = link['kind'] if kind == 'RR': qubit1 = qubit2 = 'R' elif kind == 'LL': qubit1 = qubit2 = 'L' else: root_node = link['root_node'] qubit1 = 'R' if root_node == nname1 else 'L' qubit2 = 'L' if qubit1 == 'R' else 'R' cliffords = link['cliffords'] try: cl1 = cliffords[nname1] except KeyError: cl1 = None try: cl2 = cliffords[nname2] except KeyError: cl2 = None inst_same_order.append(((nname1, qubit1, cl1), (nname2, qubit2, cl2))) fusions[order] = inst_same_order # Final remaining qubits & Clifford gates on them qubit_correspondence = {} remaining_leaves = {} for vname in self.graph.vs['name']: v_unrv: ig.Vertex = self.unraveled_graph.vs.find(name=vname) cl = v_unrv['clifford'] if v_unrv.degree() > 1: corr = (vname, 'R', cl) else: v_ngh_unrv = v_unrv.neighbors()[0] seed_node_name = v_ngh_unrv['name'] try: remaining_leaves_curr \ = remaining_leaves[seed_node_name] except KeyError: node_group \ = network.vs.select(node_group=seed_node_name) remaining_leaves_curr = {} for node in node_group: num_remaining_leaves = 2 for link in node.incident(): kind = link['kind'] if kind == 'LL' \ or (kind == 'RL' and link['root_node'] != node['name']): num_remaining_leaves -= 1 remaining_leaves_curr[node['name']] \ = num_remaining_leaves remaining_leaves[seed_node_name] = remaining_leaves_curr corr = None for node_name, num_remaining_leaves in remaining_leaves_curr.items(): if num_remaining_leaves: corr = (node_name, 'L', cl) remaining_leaves_curr[node_name] -= 1 assert corr is not None qubit_correspondence[vname] = corr node_names = network.vs['name'] return node_names, fusions, qubit_correspondence def get_vertex_clifford(self, vertex, unraveled=True): """ Get the Clifford gate applied to a vertex in the unraveled graph (by default) or the original graph. Each Clifford gate is represented by a string. For example, - `'RX'`: pi/2 X-rotation - `'RXd'`: -pi/2 X-rotation - `'RZ'`: pi/2 Z-rotation - `'RZd'`: -pi/2 Z-rotation ('d' means dagger) If a qubit is subjected to pi/2 X-rotation followed by pi/2 Z-rotation, it is represented by `'RX-RZ'`. Parameters ---------- vertex : int or str Name of the vertex. unraveled : bool (default: True) Whether to find the vertex in the unraveled or original graph. Returns ------- clifford : None or str Clifford gate applied to the vertex. """ graph = self.unraveled_graph if unraveled else self.graph if 'clifford' in graph.vertex_attributes(): cl = graph.vs.find(name=str(vertex))['clifford'] return cl else: return None def get_link_clifford(self, n1, n2): """ Get the Clifford gates that need to be applied to two qubits involved in the fusion of a given link. Each Clifford gate is represented by a string. For example, - `'RX'`: pi/2 X-rotation - `'RXd'`: -pi/2 X-rotation - `'RZ'`: pi/2 Z-rotation - `'RZd'`: -pi/2 Z-rotation ('d' means dagger) If a qubit is subjected to pi/2 X-rotation followed by pi/2 Z-rotation, it is represented by `'RX-RZ'`. Parameters ---------- n1, n2 : int or str Names of the nodes connected by the link. Returns ------- cl1, cl2 : None or str Clifford gates applied on the two qubits involved in the fusion of the link. """ network = self.fusion_network n1 = str(n1) n2 = str(n2) link = network.es[network.get_eid(n1, n2)] cliffords = link['cliffords'] cls = [] for n in [n1, n2]: try: cls.append(cliffords[n]) except KeyError: cls.append(None) return tuple(cls) def plot_graph(self, unraveled=False, **kwargs): """ Plot the original or unraveled graph. If the unraveled graph is plotted, edges in the unraveled graph are drawn as black solid lines while external fusions are drawn as red dashed lines (by default). Vertices with Clifford gates are colored in orange (by default). These Clifford gates can be obtained by using `GraphState.get_vertex_clifford()`. Parameters ---------- unraveled : bool (default: False) Whether to plot the unraveled graph or the original graph. ax : None or matplotlib Axes object (default: None) If given, the figure is plotted on the given `Axes` object. layout : str (default: 'auto') Layout algorithm for plotting. See https://python.igraph.org/en/stable/tutorial.html#layouts-and-plotting figsize : 2-tuple of float (default: (5, 5)) Size of the figure in inches. save : None or str (default: None) Path to save the figure. show_vertex_names : bool (default: True) If `True`, vertex names are shown. vertex_color_normal : str (default: 'white') Color of vertices without Clifford gates. vertex_color_clifford : str (default: 'orange') Color of vertices with Clifford gates. vertices_to_highlight : None or list of {str or int} (default: None) Name of vertices to highlight. vertex_color_highlight : str (default: purple) Color of the highlighted vertices. Ignored if `vertices_to_highlight` is `None`. edge_color_normal : str (default: black) Color of edges in the graph. edge_color_fusion : str (default: red) Color of lines for external fusions. Ignored if `unraveled` is `False`. edge_style_fusion : str (default: '--') Style of lines for external fusions. Any other keyword arguments in `igraph.plot()` can be directly used. See https://python.igraph.org/en/stable/tutorial.html#layouts-and-plotting If they are given, they override the above parameters. Returns ------- fig, ax : matplotlib Figure and Axes object. """ graph = self.unraveled_graph if unraveled else self.graph if graph is None: raise ValueError("No unraveled graph created.") fig, ax = plot_graph(graph, **kwargs) return fig, ax def plot_fusion_network(self, **kwargs): """ Plot the fusion network. Links have different styles and colors depending on their types: - 'LL': Black solid line. - 'RR': Red dashed line. - 'RL': Blue arrow from leaf to root. The number placed on each link indicates the order of the fusion. It is presented only when the resource overhead has been computed beforehand. Links with `'C'` written on them indicate fusions accompanied by non-trivial Clifford gates. These Clifford gates can be obtained by using `GraphState.get_link_clifford()`. Parameters ---------- ax : None or matplotlib Axes object (default: None) If given, the figure is plotted on the given `Axes` object. layout : str (default: 'auto') Layout algorithm for plotting.<br> See https://python.igraph.org/en/stable/tutorial.html#layouts-and-plotting figsize : 2-tuple of float (default: (5, 5)) Size of the figure in inches. save : None or str (default: None) Path to save the figure. show_only_structure : bool (default: False) If `True`, show only the network structure without any labels, ignoring the values of parameters `show_node_names`, `show_link_names`, `show_fusion_orders`, and `show_link_cliffords`. show_node_names : bool (default: True) If `True`, node names are shown. node_color : str (default: 'white') Color of nodes. show_link_names : bool (default: False) If `True`, link names are shown. show_fusion_orders : bool (default: True) If `True`, fusion orders are shown on links. If both `show_link_names` and `show_fusion_orders` are `True`, it is shown as `'{link name}-{fusion order}'` show_link_cliffords : bool (default: True) If `True`, links that correspond to fusions accompanied by non-trivial Clifford gates are marked as `'C'`. If `show_link_names` or `show_fusion_orders` are `True`, `'C'` is appended to the end of the label. link_color_ll : str (default: 'black') Color of leaf-to-leaf links. link_color_rl : str (default: 'blue') Color of root-to-leaf links. link_color_rr : str (default: 'red') Color of root-to-root links. arrow_size : float (default: 0.02) Size of arrows for root-to-leaf links. Any other keyword arguments in igraph.plot can be directly used.<br> See https://python.igraph.org/en/stable/tutorial.html#layouts-and-plotting <br> If they are given, they override the above parameters.<br> Returns ------- fig, ax : matplotlib Figure and Axes object. """ network = self.fusion_network if network is None: raise ValueError('No fusion network created.') fig, ax = plot_fusion_network(network, **kwargs) return fig, ax def copy(self): """ Return a **shallow** copy of this object. Use `copy.deepcopy()` to get a deep copy. Returns ------- copy : GraphState Copied instance of itself. """ copy = GraphState(graph=self.graph, unraveled_graph=self.unraveled_graph, fusion_network=self.fusion_network) copy.data = self.data.copy() return copyClass variables
var data : dict-
Any data obtained during unraveling the graph, constructing the fusion network, and calculating the resource overhead.
var fusion_network : igraph.Graph-
It is
Nonebefore the fusion network is created. See Sec. 7 of our tutorial for the list of its vertex and edge attributes. var graph : igraph.Graph-
Graph of the graph state to investigate. See Sec. 7 of our tutorial for the list of its vertex attributes.
var unraveled_graph : igraph.Graph-
It is
Nonebefore the unraveled graph is created. See Sec. 7 of our tutorial for the list of its vertex attributes.
Methods
def build_fusion_network(self, use_unraveled_graph=True, plot=False, verbose=False)-
Build a fusion network from the original graph or unraveled graph.
If you want to build it from the unraveled graph, at least one of
GraphState.unravel_graph(),GraphState.unravel_bcss(), andGraphState.unravel_cliques()must be executed beforehand.The constructed fusion network is saved in
GraphState.fusion_networkasigraph.Graph.Parameters
use_unraveled_graph:bool (default: True)- Whether to use the unraveled graph or the original graph for building a fusion network.
plot:bool (default: False)- Whether to plot the fusion network after building it.
verbose:bool (default: False)- Whether to print logs.
Expand source code
def build_fusion_network(self, use_unraveled_graph=True, plot=False, verbose=False): """ Build a fusion network from the original graph or unraveled graph. If you want to build it from the unraveled graph, at least one of `GraphState.unravel_graph()`, `GraphState.unravel_bcss()`, and `GraphState.unravel_cliques()` must be executed beforehand. The constructed fusion network is saved in `GraphState.fusion_network` as [`igraph.Graph`](https://python.igraph.org/en/stable/api/igraph.Graph.html). Parameters ---------- use_unraveled_graph : bool (default: True) Whether to use the unraveled graph or the original graph for building a fusion network. plot : bool (default: False) Whether to plot the fusion network after building it. verbose : bool (default: False) Whether to print logs. """ graph = self.unraveled_graph if use_unraveled_graph else self.graph if graph is None: raise ValueError("No unraveled qubit graph created.") # Fusion network network = ig.Graph() self.fusion_network = network node_groups = {} # Links inside star graphs for v in graph.vs: num_internal_nodes = v.degree() - 1 vname = v['name'] if num_internal_nodes >= 1: # Add nodes nid_init = network.vcount() seed = np.random.randint(0, num_internal_nodes) node_names = [vname if i == 0 else f'{vname}-{i}' for i in itertools.chain(range(seed, -1, -1), range(seed + 1, num_internal_nodes))] attr = { 'name': node_names, 'seed': [True if i == seed else False for i in range(num_internal_nodes)], 'node_group': vname, # 'clifford_root': None, # 'clifford_leaves': None } network.add_vertices(num_internal_nodes, attributes=attr) node_groups[vname] \ = network.vs[nid_init:nid_init + num_internal_nodes] if num_internal_nodes >= 2: # Connect internal links links = [(nid, nid + 1) for nid in range(nid_init, nid_init + num_internal_nodes - 1)] attr = { 'kind': "RL", 'root_node': [ node_names[i] if i < seed else node_names[i + 1] for i in range(num_internal_nodes - 1)], 'cliffords': {} } network.add_edges(links, attributes=attr) # Links between star graphs for e in graph.es: vs = [e.source_vertex, e.target_vertex] deg_vs = graph.degree(vs) if deg_vs[0] > 1 and deg_vs[1] > 1: nodes_to_connect = [] for v in vs: vname = v['name'] nodes = node_groups[vname].select( lambda node: node.degree() < (2 if node['seed'] else 3) ) nodes_to_connect.append(np.random.choice(nodes)) network.add_edge(*nodes_to_connect, kind='LL', root_node=None, cliffords={}) if verbose: print("Fusion network of the unraveled graph:") self.plot_fusion_network() plt.show() # Set of seed node names where root vertices are connected by # external fusions. nnames_root_connected = set() is_node_not_full = lambda node: node.degree() < ( 2 if node['seed'] and ( node['name'] not in nnames_root_connected) else 3) def get_nodes_containing_vertex(vname): try: node = node_groups[vname].find(name=vname) is_root = True seed_node_name = vname except KeyError: ngh = graph.vs[graph.neighbors(vname)[0]] seed_node_name = ngh['name'] nodes = node_groups[seed_node_name].select(is_node_not_full) node = np.random.choice(nodes) is_root = False return node, is_root, seed_node_name vs_attrs = graph.vs.attributes() # Links by external fusions if 'ext_fusion' in vs_attrs: vnames_to_skip = set() for v1 in graph.vs.select(ext_fusion_ne=None): vname1 = v1['name'] if vname1 in vnames_to_skip: continue vname2 = v1['ext_fusion'] v2 = graph.vs.find(name=vname2) vnames_to_skip.add(vname2) node1, is_root1, _ = get_nodes_containing_vertex(vname1) node2, is_root2, _ = get_nodes_containing_vertex(vname2) if is_root1 and is_root2: kind = 'RR' root_node = None nnames_root_connected.add(node1['name']) nnames_root_connected.add(node2['name']) elif not is_root1 and not is_root2: kind = 'LL' root_node = None else: kind = 'RL' root_node = node1['name'] if is_root1 else node2['name'] nnames_root_connected.add(root_node) cliffords = {} cl1 = v1['clifford'] cl2 = v2['clifford'] for node, cl in zip([node1, node2], [cl1, cl2]): if cl is not None: cliffords[node['name']] = cl network.add_edge(node1, node2, kind=kind, root_node=root_node, cliffords=cliffords) network.es['name'] = [str(eid) for eid in range(network.ecount())] if verbose: print("Add external fusions:") self.plot_fusion_network() plt.show() # Clifford gates on surviving qubits # if 'clifford' in vs_attrs: # cls_in_node_group_leaves = {} # for v_cl in graph.vs.select(clifford_ne=None, ext_fusion=None): # vname = v_cl['name'] # _, is_root, seed_node_name = get_nodes_containing_vertex(vname) # seed_node = network.vs.find(name=seed_node_name) # cl = v_cl['clifford'] # # if is_root: # if seed_node_name not in nnames_root_connected: # seed_node['clifford_root'] = cl # # else: # try: # cls_in_node_group_leaves[seed_node_name].append(cl) # except KeyError: # cls_in_node_group_leaves[seed_node_name] = [cl] # # for seed_node_name, cls in cls_in_node_group_leaves.items(): # node_group = node_groups[seed_node_name] # nums_surviving_leaves = [] # for node in node_group: # if node['name'] in nnames_root_connected: # num_surviving_leaves = 3 - node.degree() # else: # num_surviving_leaves = 2 - node.degree() # nums_surviving_leaves.append(num_surviving_leaves) # total_num_surviving_leaves = sum(nums_surviving_leaves) # # if len(cls) < total_num_surviving_leaves: # cls.extend([None] # * (total_num_surviving_leaves - len(cls))) # np.random.shuffle(cls) # # i_start = 0 # for node, num_leaves in zip(node_group, nums_surviving_leaves): # cls_current_node = cls[i_start:i_start + num_leaves] # cls_current_node = [cl for cl in cls_current_node # if cl is not None] # node['clifford_leaves'] = cls_current_node # i_start += num_leaves # if verbose: # print("Apply Clifford gates:") # self.plot_fusion_network() # plt.show() self.fusion_network = network if plot: print("Final:") self.plot_fusion_network() plt.show() def calculate_overhead(self, p_succ=0.5, strategy='weight_and_matching', optimize_num_fusions=False, fusion_order=None)-
Calculate the resource overhead (average number of basic resource states required to generate the desired graph state) from the fusion network.
GraphState.build_fusion_network()must be executed beforehand.The resulting data is saved in
GraphState.data.Parameters
p_succ:float (default: 0.5)- Success probability of a fusion.
strategy:str, oneof['weight', 'matching', 'weight_and_matching', 'random'] (default: 'weight_and_matching')-
Strategy for determining the edge to contract.
'weight': Contract a random one among the edges with the smallest weight.'matching': Contract an edge in a maximum matching.'weight_and_matching': Contract an edge in a maximum matching of the subgraph of the intermediate fusion network induced by the edges with the smallest weight.'random': Contract a random edge.
optimize_num_fusions:bool- If
True, the average number of required fusion attempts are used to quantify resource overheads instead of the average number of required basic resource states. fusion_order:Noneorlistof{intorstr} (default: None)-
Fusion order given explicitly as vertex names.
If it is not
None, parameterstrategyis ignored.
Returns
data:dict- Outcomes of the calculation, which is a shallow copy of
GraphState.data.
The calculated overhead and number of steps can be obtained fromdata['overhead']anddata['num_steps'], respectively.
Expand source code
def calculate_overhead(self, p_succ=0.5, strategy='weight_and_matching', optimize_num_fusions=False, fusion_order=None): """ Calculate the resource overhead (average number of basic resource states required to generate the desired graph state) from the fusion network. `GraphState.build_fusion_network()` must be executed beforehand. The resulting data is saved in `GraphState.data`. Parameters ---------- p_succ : float (default: 0.5) Success probability of a fusion. strategy : str, one of ['weight', 'matching', 'weight_and_matching', 'random'] (default: 'weight_and_matching') Strategy for determining the edge to contract. - `'weight'`: Contract a random one among the edges with the smallest weight. - `'matching'`: Contract an edge in a maximum matching. - `'weight_and_matching'`: Contract an edge in a maximum matching of the subgraph of the intermediate fusion network induced by the edges with the smallest weight. - `'random'`: Contract a random edge. optimize_num_fusions : bool If `True`, the average number of required fusion attempts are used to quantify resource overheads instead of the average number of required basic resource states. fusion_order : None or list of {int or str} (default: None) Fusion order given explicitly as vertex names. If it is not `None`, parameter `strategy` is ignored. Returns ------- data : dict Outcomes of the calculation, which is a shallow copy of `GraphState.data`.<br> The calculated overhead and number of steps can be obtained from `data['overhead']` and `data['num_steps']`, respectively. """ if self.fusion_network is None: raise ValueError("No fusion network created") # Trivial cases node_num = self.fusion_network.vcount() if node_num == 0: self.data['overhead'] = 0 self.data['num_fusions'] = 0 self.data['num_steps'] = 0 return self.data elif node_num == 1: self.data['overhead'] = 1 self.data['num_fusions'] = 0 self.data['num_steps'] = 0 return self.data if fusion_order is None: fusion_order = [] is_fusion_order_given = False else: is_fusion_order_given = True self.fusion_network['p_succ'] = p_succ self.fusion_network.es['order'] = None # Initialize intermediate fusion network network = self.fusion_network.copy() network.vs['weight'] = 1 network.vs['weight_f'] = 0 network.vs['order'] = 0 network.vs['on'] = True network.es['weight'] = 2 / p_succ network.es['weight_f'] = 1 / p_succ del network.es['order'] turn = 0 weight_key = 'weight_f' if optimize_num_fusions else 'weight' # Iterate until no edges remain in the fusion network while True: if not network.ecount(): break if is_fusion_order_given: enames_curr_step = [str(fusion_order[turn])] is_parellel = True elif strategy == 'weight': min_weight = min(network.es[weight_key]) eids_min_weight = network.es.select(weight=min_weight) enames_curr_step = eids_min_weight['name'] is_parellel = len(enames_curr_step) == 1 # elif strategy == 'betweenness': # eb = np.array(network.edge_betweenness()) # min_eb = np.min(eb) # eids_curr_step = np.nonzero(eb == min_eb)[0] # enames_curr_step = [network.es[eid]['name'] for eid in # eids_curr_step] # is_parellel = len(enames_curr_step) == 1 # # elif strategy == 'weight_and_betweenness': # min_weight = min(network.es['weight']) # eids_min_weight = network.es.select(weight=min_weight) # es_min_ovh = eids_min_weight # # eb = network.edge_betweenness() # ebs_min_ovh = np.array([eb[e.index] for e in es_min_ovh]) # min_eb = np.min(ebs_min_ovh) # enames_curr_step = [es_min_ovh[i]['name'] for i in # np.nonzero(ebs_min_ovh == min_eb)[0]] # is_parellel = len(enames_curr_step) == 1 elif 'matching' in strategy: if strategy == 'weight_and_matching': min_weight = min(network.es[weight_key]) if optimize_num_fusions: es_min_weight = network.es.select(weight_f=min_weight) else: es_min_weight = network.es.select(weight=min_weight) subnetwork = network.subgraph_edges(es_min_weight) else: subnetwork = network subnetwork_nx = subnetwork.to_networkx() if isinstance(subnetwork_nx, nx.MultiGraph): subnetwork_nx = nx.Graph(subnetwork_nx) matching = nx.max_weight_matching(subnetwork_nx, weight=None) enames_curr_step = \ subnetwork.es[subnetwork.get_eids(matching)]['name'] is_parellel = True elif strategy == 'random': enames_curr_step = [np.random.choice(network.es['name'])] is_parellel = True else: raise ValueError recalculated_enames = [] # if get_fusion_order and not is_fusion_order_given: # fusion_order_curr_step = set() # fusion_order.append(fusion_order_curr_step) while True: if not is_parellel: for rec_ename in recalculated_enames: try: enames_curr_step.remove(rec_ename) except ValueError: pass if not enames_curr_step: break recalculated_enames.clear() if is_parellel: ename_to_merge = enames_curr_step.pop() else: ename_to_merge = np.random.choice(enames_curr_step) enames_curr_step.remove(ename_to_merge) _, _, enames_updated_weight \ = self._contract_edge(network, ename_to_merge) recalculated_enames.extend(enames_updated_weight) v_final = network.vs.select(on=True) overhead = sum(v_final['weight']) num_fusions = sum(v_final['weight_f']) num_steps = max(v_final['order']) results = { 'overhead': overhead, 'num_fusions': num_fusions, 'num_steps': num_steps, 'fusion_order_strategy': strategy, 'p_succ': p_succ, } if optimize_num_fusions: results['optimize_num_fusions'] = True # if get_fusion_order: # results['fusion_order'] = fusion_order self.data.update(results) return self.data.copy() def calculate_succ_probs(self, cutoff=0.95, auto_increasing_prec=True, prec=30, prec_interval=5, diff_overhead_thrs=0.01)-
Calculate the success probability of the generation of the graph state for each resource count. In other words, get the cumulative mass function (CMF) of the resource count required to generate the state.
The success probability is computed while increasing the resource count until the value reaches
cutoffthat is smaller than one. The estimated resource overhead, which is the expectation value of the resource count, is additionally returned.It uses the
decimalmodule instead of float64 since the calculation involves the summation of many extremely small numbers thus floating-point errors may be detrimental.By default, it executes the computation multiple times while increasing the precision by 5 starting from 30. When the estimated overhead does not change by more than 1% in two consecutive trials, the iteration is terminated and the results of the final trial are returned.
Parameters
cutoff:float (default: 0.95)- Cutoff threshold between 0 and 1.
auto_increasing_prec:bool (default: True)- Whether to execute the computation multiple times. If it is False,
the parameters
prec_intervalanddiff_overhead_thrsare ignored. prec:int (default: 30)- Initial precision of numbers.
prec_interval:int (default: 5)- Interval of precisions between two consecutive trials.
diff_overhead_thrs:float (default: 0.01)- Threshold of the relative difference between the overheads estimated
from two consecutive trials for determining the termination of the
iteration. Namely, if the overheads are
o1ando2in order, the iteration terminates whenabs(o1 - o2) / o2 < diff_overhead_thrs.
Returns
resource_count_start:int- First resource count that gives a nonzero probability.
probs:1D numpy arrayofdecimal.Decimal- Success probabilities for the resource counts starting from
resource_count_start.probs[i]is the value corresponding to the resource count ofresource_count_start+i. overhead:decimal.Decimal- Resource overhead estimated by the calculated probabilities.
If
cutoffis close enough to one, this value should not be significantly different from the correct one (GraphState.data['overhead']).
Expand source code
def calculate_succ_probs(self, cutoff=0.95, auto_increasing_prec=True, prec=30, prec_interval=5, diff_overhead_thrs=0.01): """ Calculate the success probability of the generation of the graph state for each resource count. In other words, get the cumulative mass function (CMF) of the resource count required to generate the state. The success probability is computed while increasing the resource count until the value reaches `cutoff` that is smaller than one. The estimated resource overhead, which is the expectation value of the resource count, is additionally returned. It uses the `decimal` module instead of float64 since the calculation involves the summation of many extremely small numbers thus floating-point errors may be detrimental. By default, it executes the computation multiple times while increasing the precision by 5 starting from 30. When the estimated overhead does not change by more than 1% in two consecutive trials, the iteration is terminated and the results of the final trial are returned. Parameters ---------- cutoff : float (default: 0.95) Cutoff threshold between 0 and 1. auto_increasing_prec : bool (default: True) Whether to execute the computation multiple times. If it is False, the parameters `prec_interval` and `diff_overhead_thrs` are ignored. prec : int (default: 30) Initial precision of numbers. prec_interval : int (default: 5) Interval of precisions between two consecutive trials. diff_overhead_thrs : float (default: 0.01) Threshold of the relative difference between the overheads estimated from two consecutive trials for determining the termination of the iteration. Namely, if the overheads are `o1` and `o2` in order, the iteration terminates when `abs(o1 - o2) / o2 < diff_overhead_thrs`. Returns ------- resource_count_start : int First resource count that gives a nonzero probability. probs : 1D numpy array of decimal.Decimal Success probabilities for the resource counts starting from `resource_count_start`. `probs[i]` is the value corresponding to the resource count of `resource_count_start+i`. overhead : decimal.Decimal Resource overhead estimated by the calculated probabilities. If `cutoff` is close enough to one, this value should not be significantly different from the correct one (`GraphState.data['overhead']`). """ if self.fusion_network is None: raise ValueError("No fusion network created") if 'order' not in self.fusion_network.edge_attributes(): raise ValueError("No fusion order data in the fusion network") if not auto_increasing_prec: network: ig.Graph = self.fusion_network.copy() dec.getcontext().prec = prec for v in network.vs: v['ftpdf'] = np.array([dec.Decimal(0), dec.Decimal(1)]) network.vs['on'] = True p_succ = network['p_succ'] orders = network.es['order'] num_steps = max(orders) for order in range(1, num_steps + 1): enames = network.es.select(order=order)['name'] for ename in enames: link = network.es.find(name=ename) node1, node2 = link.source_vertex, link.target_vertex new_ftpdf = get_ftpdf_contracted(node1['ftpdf'], node2['ftpdf'], p_succ=p_succ) v_merged, _, _ \ = self._contract_edge(network, ename, update_weight_and_order=False) v_merged['ftpdf'] = new_ftpdf ftpdfs_final = network.vs.select(on=True)['ftpdf'] while True: if len(ftpdfs_final) == 1: ftpdf_final = ftpdfs_final[0] break ftpdfs_final.append(scsig.convolve(ftpdfs_final[0], ftpdfs_final[1])) del ftpdfs_final[1], ftpdfs_final[0] resource_count_start, probs \ = recover_cmf_from_ftpdf(ftpdf_final, cutoff) pmf = np.diff(probs) overhead \ = np.sum(pmf * np.arange(resource_count_start, resource_count_start + pmf.size)) else: prev_overhead = None while True: print(f'prec = {prec}: ', end='') try: resource_count_start, probs, overhead \ = self.calculate_succ_probs(cutoff=cutoff, auto_increasing_prec=False, prec=prec) except ValueError: print('Error') prec += prec_interval continue if prev_overhead is not None \ and abs(overhead - prev_overhead) / overhead < diff_overhead_thrs: print(overhead) break print(overhead) prec += prec_interval prev_overhead = overhead return resource_count_start, probs, overhead def copy(self)-
Return a shallow copy of this object.
Use
copy.deepcopy()to get a deep copy.Returns
copy:GraphState- Copied instance of itself.
Expand source code
def copy(self): """ Return a **shallow** copy of this object. Use `copy.deepcopy()` to get a deep copy. Returns ------- copy : GraphState Copied instance of itself. """ copy = GraphState(graph=self.graph, unraveled_graph=self.unraveled_graph, fusion_network=self.fusion_network) copy.data = self.data.copy() return copy def get_instructions(self)-
Get the instruction to generate the desired graph state from multiple three-qubit linear graph states.
One of
GraphState.calculate_overhead(),GraphState.simulate(), andGraphState.simulate_adaptive()must be executed beforehand.Returns
node_names:listofstr- List of the names of nodes in the fusion network.
fusions:dict-
Dictionary that contains the information about required fusions and Clifford gates.
Each required fusion is represented by a 2-tuple of 3-tuples:
((n1, q1, cl1), (n2, q2, cl2)).n1andn2are the names of the nodes involved in the fusion,q1andq2are'R'or'L'that indicate the qubits undergoing the fusion ('R'for a root qubit and'L'for a leaf qubit), andcl1andcl2are the Clifford gates applied to the qubits before the fusion is performed.fusions[i]for a positive integeriis a list of such 2-tuples, which indicate fusions that can be done in parallel in thei-th step. qubit_correspondence:dict-
Dictionary that contains the correspondence between the vertices in the original graph and the final remaining qubits after performing all the fusions.
For each name (say,
vname) of a vertex in the original graph,qubit_correspondence[vname]is a 3-tuple(node, qubit, cl), wherenodeis the node containing the qubit,qubitis either'R'or'L'that indicates whether the qubit is a root or leaf qubit, andclis the Clifford gate applied to the qubit.
Expand source code
def get_instructions(self): """ Get the instruction to generate the desired graph state from multiple three-qubit linear graph states. One of `GraphState.calculate_overhead()`, `GraphState.simulate()`, and `GraphState.simulate_adaptive()` must be executed beforehand. Returns ------- node_names : list of str List of the names of nodes in the fusion network. fusions : dict Dictionary that contains the information about required fusions and Clifford gates. Each required fusion is represented by a 2-tuple of 3-tuples: `((n1, q1, cl1), (n2, q2, cl2))`. `n1` and `n2` are the names of the nodes involved in the fusion, `q1` and `q2` are `'R'` or `'L'` that indicate the qubits undergoing the fusion (`'R'` for a root qubit and `'L'` for a leaf qubit), and `cl1` and `cl2` are the Clifford gates applied to the qubits before the fusion is performed. `fusions[i]` for a positive integer `i` is a list of such 2-tuples, which indicate fusions that can be done in parallel in the `i`-th step. qubit_correspondence : dict Dictionary that contains the correspondence between the vertices in the original graph and the final remaining qubits after performing all the fusions. For each name (say, `vname`) of a vertex in the original graph, `qubit_correspondence[vname]` is a 3-tuple `(node, qubit, cl)`, where `node` is the node containing the qubit, `qubit` is either `'R'` or `'L'` that indicates whether the qubit is a root or leaf qubit, and `cl` is the Clifford gate applied to the qubit. """ network = self.fusion_network # Fusions fusions = {} orders = network.es['order'] num_steps = max(orders) for order in range(1, num_steps + 1): inst_same_order = [] links = network.es.select(order=order) for link in links: nname1 = link.source_vertex['name'] nname2 = link.target_vertex['name'] kind = link['kind'] if kind == 'RR': qubit1 = qubit2 = 'R' elif kind == 'LL': qubit1 = qubit2 = 'L' else: root_node = link['root_node'] qubit1 = 'R' if root_node == nname1 else 'L' qubit2 = 'L' if qubit1 == 'R' else 'R' cliffords = link['cliffords'] try: cl1 = cliffords[nname1] except KeyError: cl1 = None try: cl2 = cliffords[nname2] except KeyError: cl2 = None inst_same_order.append(((nname1, qubit1, cl1), (nname2, qubit2, cl2))) fusions[order] = inst_same_order # Final remaining qubits & Clifford gates on them qubit_correspondence = {} remaining_leaves = {} for vname in self.graph.vs['name']: v_unrv: ig.Vertex = self.unraveled_graph.vs.find(name=vname) cl = v_unrv['clifford'] if v_unrv.degree() > 1: corr = (vname, 'R', cl) else: v_ngh_unrv = v_unrv.neighbors()[0] seed_node_name = v_ngh_unrv['name'] try: remaining_leaves_curr \ = remaining_leaves[seed_node_name] except KeyError: node_group \ = network.vs.select(node_group=seed_node_name) remaining_leaves_curr = {} for node in node_group: num_remaining_leaves = 2 for link in node.incident(): kind = link['kind'] if kind == 'LL' \ or (kind == 'RL' and link['root_node'] != node['name']): num_remaining_leaves -= 1 remaining_leaves_curr[node['name']] \ = num_remaining_leaves remaining_leaves[seed_node_name] = remaining_leaves_curr corr = None for node_name, num_remaining_leaves in remaining_leaves_curr.items(): if num_remaining_leaves: corr = (node_name, 'L', cl) remaining_leaves_curr[node_name] -= 1 assert corr is not None qubit_correspondence[vname] = corr node_names = network.vs['name'] return node_names, fusions, qubit_correspondence def get_link_clifford(self, n1, n2)-
Get the Clifford gates that need to be applied to two qubits involved in the fusion of a given link.
Each Clifford gate is represented by a string. For example,
'RX': pi/2 X-rotation'RXd': -pi/2 X-rotation'RZ': pi/2 Z-rotation'RZd': -pi/2 Z-rotation ('d' means dagger)
If a qubit is subjected to pi/2 X-rotation followed by pi/2 Z-rotation, it is represented by
'RX-RZ'.Parameters
n1,n2:intorstr- Names of the nodes connected by the link.
Returns
cl1,cl2:Noneorstr- Clifford gates applied on the two qubits involved in the fusion of the link.
Expand source code
def get_link_clifford(self, n1, n2): """ Get the Clifford gates that need to be applied to two qubits involved in the fusion of a given link. Each Clifford gate is represented by a string. For example, - `'RX'`: pi/2 X-rotation - `'RXd'`: -pi/2 X-rotation - `'RZ'`: pi/2 Z-rotation - `'RZd'`: -pi/2 Z-rotation ('d' means dagger) If a qubit is subjected to pi/2 X-rotation followed by pi/2 Z-rotation, it is represented by `'RX-RZ'`. Parameters ---------- n1, n2 : int or str Names of the nodes connected by the link. Returns ------- cl1, cl2 : None or str Clifford gates applied on the two qubits involved in the fusion of the link. """ network = self.fusion_network n1 = str(n1) n2 = str(n2) link = network.es[network.get_eid(n1, n2)] cliffords = link['cliffords'] cls = [] for n in [n1, n2]: try: cls.append(cliffords[n]) except KeyError: cls.append(None) return tuple(cls) def get_vertex_clifford(self, vertex, unraveled=True)-
Get the Clifford gate applied to a vertex in the unraveled graph (by default) or the original graph.
Each Clifford gate is represented by a string. For example,
'RX': pi/2 X-rotation'RXd': -pi/2 X-rotation'RZ': pi/2 Z-rotation'RZd': -pi/2 Z-rotation ('d' means dagger)
If a qubit is subjected to pi/2 X-rotation followed by pi/2 Z-rotation, it is represented by
'RX-RZ'.Parameters
vertex:intorstr- Name of the vertex.
unraveled:bool (default: True)- Whether to find the vertex in the unraveled or original graph.
Returns
clifford:Noneorstr- Clifford gate applied to the vertex.
Expand source code
def get_vertex_clifford(self, vertex, unraveled=True): """ Get the Clifford gate applied to a vertex in the unraveled graph (by default) or the original graph. Each Clifford gate is represented by a string. For example, - `'RX'`: pi/2 X-rotation - `'RXd'`: -pi/2 X-rotation - `'RZ'`: pi/2 Z-rotation - `'RZd'`: -pi/2 Z-rotation ('d' means dagger) If a qubit is subjected to pi/2 X-rotation followed by pi/2 Z-rotation, it is represented by `'RX-RZ'`. Parameters ---------- vertex : int or str Name of the vertex. unraveled : bool (default: True) Whether to find the vertex in the unraveled or original graph. Returns ------- clifford : None or str Clifford gate applied to the vertex. """ graph = self.unraveled_graph if unraveled else self.graph if 'clifford' in graph.vertex_attributes(): cl = graph.vs.find(name=str(vertex))['clifford'] return cl else: return None def initialize(self)-
Initialize the created unraveled graph and fusion network and the calculation data.
Expand source code
def initialize(self): """ Initialize the created unraveled graph and fusion network and the calculation data. """ self.unraveled_graph = None self.fusion_network = None self.data = {} def plot_fusion_network(self, **kwargs)-
Plot the fusion network.
Links have different styles and colors depending on their types:
- 'LL': Black solid line.
- 'RR': Red dashed line.
- 'RL': Blue arrow from leaf to root.
The number placed on each link indicates the order of the fusion. It is presented only when the resource overhead has been computed beforehand.
Links with
'C'written on them indicate fusions accompanied by non-trivial Clifford gates. These Clifford gates can be obtained by usingGraphState.get_link_clifford().Parameters
ax:Noneormatplotlib Axes object (default: None)- If given, the figure is plotted on the given
Axesobject. layout:str (default: 'auto')- Layout algorithm for plotting.
See https://python.igraph.org/en/stable/tutorial.html#layouts-and-plotting figsize:2-tupleoffloat (default: (5, 5))- Size of the figure in inches.
save:Noneorstr (default: None)- Path to save the figure.
show_only_structure:bool (default: False)- If
True, show only the network structure without any labels, ignoring the values of parametersshow_node_names,show_link_names,show_fusion_orders, andshow_link_cliffords. show_node_names:bool (default: True)- If
True, node names are shown. node_color:str (default: 'white')- Color of nodes.
show_link_names:bool (default: False)- If
True, link names are shown. show_fusion_orders:bool (default: True)-
If
True, fusion orders are shown on links.If both
show_link_namesandshow_fusion_ordersareTrue, it is shown as'{link name}-{fusion order}' show_link_cliffords:bool (default: True)-
If
True, links that correspond to fusions accompanied by non-trivial Clifford gates are marked as'C'.If
show_link_namesorshow_fusion_ordersareTrue,'C'is appended to the end of the label. link_color_ll:str (default: 'black')- Color of leaf-to-leaf links.
link_color_rl:str (default: 'blue')- Color of root-to-leaf links.
link_color_rr:str (default: 'red')- Color of root-to-root links.
arrow_size:float (default: 0.02)- Size of arrows for root-to-leaf links.
Any other keyword arguments in igraph.plot can be directly used.
See https://python.igraph.org/en/stable/tutorial.html#layouts-and-plotting
If they are given, they override the above parameters.Returns
fig, ax : matplotlib Figure and Axes object.
Expand source code
def plot_fusion_network(self, **kwargs): """ Plot the fusion network. Links have different styles and colors depending on their types: - 'LL': Black solid line. - 'RR': Red dashed line. - 'RL': Blue arrow from leaf to root. The number placed on each link indicates the order of the fusion. It is presented only when the resource overhead has been computed beforehand. Links with `'C'` written on them indicate fusions accompanied by non-trivial Clifford gates. These Clifford gates can be obtained by using `GraphState.get_link_clifford()`. Parameters ---------- ax : None or matplotlib Axes object (default: None) If given, the figure is plotted on the given `Axes` object. layout : str (default: 'auto') Layout algorithm for plotting.<br> See https://python.igraph.org/en/stable/tutorial.html#layouts-and-plotting figsize : 2-tuple of float (default: (5, 5)) Size of the figure in inches. save : None or str (default: None) Path to save the figure. show_only_structure : bool (default: False) If `True`, show only the network structure without any labels, ignoring the values of parameters `show_node_names`, `show_link_names`, `show_fusion_orders`, and `show_link_cliffords`. show_node_names : bool (default: True) If `True`, node names are shown. node_color : str (default: 'white') Color of nodes. show_link_names : bool (default: False) If `True`, link names are shown. show_fusion_orders : bool (default: True) If `True`, fusion orders are shown on links. If both `show_link_names` and `show_fusion_orders` are `True`, it is shown as `'{link name}-{fusion order}'` show_link_cliffords : bool (default: True) If `True`, links that correspond to fusions accompanied by non-trivial Clifford gates are marked as `'C'`. If `show_link_names` or `show_fusion_orders` are `True`, `'C'` is appended to the end of the label. link_color_ll : str (default: 'black') Color of leaf-to-leaf links. link_color_rl : str (default: 'blue') Color of root-to-leaf links. link_color_rr : str (default: 'red') Color of root-to-root links. arrow_size : float (default: 0.02) Size of arrows for root-to-leaf links. Any other keyword arguments in igraph.plot can be directly used.<br> See https://python.igraph.org/en/stable/tutorial.html#layouts-and-plotting <br> If they are given, they override the above parameters.<br> Returns ------- fig, ax : matplotlib Figure and Axes object. """ network = self.fusion_network if network is None: raise ValueError('No fusion network created.') fig, ax = plot_fusion_network(network, **kwargs) return fig, ax def plot_graph(self, unraveled=False, **kwargs)-
Plot the original or unraveled graph.
If the unraveled graph is plotted, edges in the unraveled graph are drawn as black solid lines while external fusions are drawn as red dashed lines (by default).
Vertices with Clifford gates are colored in orange (by default). These Clifford gates can be obtained by using
GraphState.get_vertex_clifford().Parameters
unraveled:bool (default: False)- Whether to plot the unraveled graph or the original graph.
ax:Noneormatplotlib Axes object (default: None)- If given, the figure is plotted on the given
Axesobject. layout:str (default: 'auto')-
Layout algorithm for plotting.
See https://python.igraph.org/en/stable/tutorial.html#layouts-and-plotting
figsize:2-tupleoffloat (default: (5, 5))- Size of the figure in inches.
save:Noneorstr (default: None)- Path to save the figure.
show_vertex_names:bool (default: True)- If
True, vertex names are shown. vertex_color_normal:str (default: 'white')- Color of vertices without Clifford gates.
vertex_color_clifford:str (default: 'orange')- Color of vertices with Clifford gates.
vertices_to_highlight:Noneorlistof{strorint} (default: None)- Name of vertices to highlight.
vertex_color_highlight:str (default: purple)-
Color of the highlighted vertices.
Ignored if
vertices_to_highlightisNone. edge_color_normal:str (default: black)- Color of edges in the graph.
edge_color_fusion:str (default: red)-
Color of lines for external fusions.
Ignored if
unraveledisFalse. edge_style_fusion:str (default: '--')- Style of lines for external fusions.
Any other keyword arguments in
igraph.plot()can be directly used. See https://python.igraph.org/en/stable/tutorial.html#layouts-and-plotting If they are given, they override the above parameters.Returns
fig, ax : matplotlib Figure and Axes object.
Expand source code
def plot_graph(self, unraveled=False, **kwargs): """ Plot the original or unraveled graph. If the unraveled graph is plotted, edges in the unraveled graph are drawn as black solid lines while external fusions are drawn as red dashed lines (by default). Vertices with Clifford gates are colored in orange (by default). These Clifford gates can be obtained by using `GraphState.get_vertex_clifford()`. Parameters ---------- unraveled : bool (default: False) Whether to plot the unraveled graph or the original graph. ax : None or matplotlib Axes object (default: None) If given, the figure is plotted on the given `Axes` object. layout : str (default: 'auto') Layout algorithm for plotting. See https://python.igraph.org/en/stable/tutorial.html#layouts-and-plotting figsize : 2-tuple of float (default: (5, 5)) Size of the figure in inches. save : None or str (default: None) Path to save the figure. show_vertex_names : bool (default: True) If `True`, vertex names are shown. vertex_color_normal : str (default: 'white') Color of vertices without Clifford gates. vertex_color_clifford : str (default: 'orange') Color of vertices with Clifford gates. vertices_to_highlight : None or list of {str or int} (default: None) Name of vertices to highlight. vertex_color_highlight : str (default: purple) Color of the highlighted vertices. Ignored if `vertices_to_highlight` is `None`. edge_color_normal : str (default: black) Color of edges in the graph. edge_color_fusion : str (default: red) Color of lines for external fusions. Ignored if `unraveled` is `False`. edge_style_fusion : str (default: '--') Style of lines for external fusions. Any other keyword arguments in `igraph.plot()` can be directly used. See https://python.igraph.org/en/stable/tutorial.html#layouts-and-plotting If they are given, they override the above parameters. Returns ------- fig, ax : matplotlib Figure and Axes object. """ graph = self.unraveled_graph if unraveled else self.graph if graph is None: raise ValueError("No unraveled graph created.") fig, ax = plot_graph(graph, **kwargs) return fig, ax def simulate(self, n_iter, p_succ=0.5, mp=False, n_procs=None, get_all_data=False, get_all_graphs=False, get_all_fusion_networks=False, unravel=True, unravel_bcs_first='random', fusion_order_strategy='weight_and_matching', optimize_num_fusions=False, seed='keep', verbose=True, pbar=True, **kwargs)-
Execute the strategy for a fixed number of iterations and obtain the best one only (by default).
Attributes such as
GraphState.data,GraphState.unraveled_graph, andGraphState.fusion_networkare updated according to the result of the best sample.Parameters
n_iter:int- Iteration number.
p_succ:float (default: 0.5)- Success probability of a fusion.
mp:bool (default: False)-
Whether to use multiprocessing for the iterations.
Package parmap should be installed to use it.
n_procs:Noneorint (default: None)-
Maximal number of simultaneous processes for multiprocessing.
If it is
None, the number of CPUs is used.Ignored when
mpisFalse. get_all_data:bool (default: False)- Whether to obtain the data (overheads, numbers of steps, etc.) from all samples or only the best sample.
get_all_graphs:bool (default: False)- Whether to obtain the unraveled graphs from all samples or only the best sample.
get_all_fusion_networks:bool (default: False)- Whether to obtain the fusion networks from all samples or only the best sample.
unravel:bool (default: True)- Whether to unravel the graph or not.
unravel_bcs_first:oneof[True, False, 'random'] (default: 'random')-
True: BCSs are unraveled first, then clqiues are unraveled.False, cliques are unraveled first, then BCSs are unraveled.'random', the order is randomly chosen.
fusion_order_strategy:oneof['weight', 'matching', 'weight_and_matching', 'random'] (default:weight_and_matching')`-
Strategy for determining the edge to contract in each step.
'weight': Contract a random one among the edges with the smallest weight.'matching': Contract an edge in a maximum matching.'weight_and_matching': Contract an edge in a maximum matching of the subgraph of the intermediate fusion network induced by the edges with the smallest weight.'random': Contract a random edge.
optimize_num_fusions:bool (default: False)- If
True, use the average number of fusion attempts to quantify resource overheads instead of the average number of basic resource states. seed:'keep'orNoneorint (default: 'keep')-
Random seed.
'keep': The seed is not initialized.None: The current time is used as the random seed.int: The given number is used as the random seed.
If
n_iter>1, the given seed is used to sample random seeds for individual iterations. However, ifn_iter==1, the given seed is used as the random seed for the (only one) iteration itself. verbose:bool (default: True)- Whether to print logs.
pbar:bool (default: True)- Whether to show a progress bar. Ignored if tqdm is not installed.
kwargs:dict-
Additional keyword arguments for calculating overheads.
See the description of
GraphState.calculate_overhead().
Returns
res:dict-
Dictionary containing the results of the iterations with keys:
'best_overhead': Overhead of the best sample (i.e., sample with the smallest overhead or avg fusion number, determined by parameteroptimize_num_fusions).'best_num_fusions': Average number of fusions of the best sample.'best_num_steps': Number of steps (i.e., groups of fusions that can be done in parallel) of the best sample.'best_seed': Random seed for the best sample. To recover the sample from it, use theseedparameter ofGraphState.simulate()withn_iter=1.'n_iter': Number of iterations. Same as parametern_iter.'unravel_bcs_first': Whether to unravel BCSs or cliques first for the best sample.'overheads','nums_fusions','nums_steps','seeds': Lists of the overheads, avg fusion numbers, step numbers, and seeds of all samples, respectively. Exist only whenget_all_data==True.'unraveled_graphs': List of the unraveled graphs of all samples. Exists only whenget_all_graphs==True.'fusion_networks': List of the fusion networks of all samples. Exists only whenget_all_fusion_networks==True.
Expand source code
def simulate(self, n_iter, p_succ=0.5, mp=False, n_procs=None, get_all_data=False, get_all_graphs=False, get_all_fusion_networks=False, unravel=True, unravel_bcs_first='random', fusion_order_strategy='weight_and_matching', optimize_num_fusions=False, seed='keep', verbose=True, pbar=True, **kwargs): """ Execute the strategy for a fixed number of iterations and obtain the best one only (by default). Attributes such as `GraphState.data`, `GraphState.unraveled_graph`, and `GraphState.fusion_network` are updated according to the result of the best sample. Parameters ---------- n_iter : int Iteration number. p_succ : float (default: 0.5) Success probability of a fusion. mp : bool (default: False) Whether to use multiprocessing for the iterations. Package *parmap* should be installed to use it. n_procs : None or int (default: None) Maximal number of simultaneous processes for multiprocessing. If it is `None`, the number of CPUs is used. Ignored when `mp` is `False`. get_all_data : bool (default: False) Whether to obtain the data (overheads, numbers of steps, etc.) from all samples or only the best sample. get_all_graphs : bool (default: False) Whether to obtain the unraveled graphs from all samples or only the best sample. get_all_fusion_networks : bool (default: False) Whether to obtain the fusion networks from all samples or only the best sample. unravel : bool (default: True) Whether to unravel the graph or not. unravel_bcs_first : one of [True, False, 'random'] (default: 'random') - `True`: BCSs are unraveled first, then clqiues are unraveled. - `False`, cliques are unraveled first, then BCSs are unraveled. - `'random'`, the order is randomly chosen. fusion_order_strategy : one of ['weight', 'matching', 'weight_and_matching', 'random'] (default: `weight_and_matching') Strategy for determining the edge to contract in each step. - `'weight'`: Contract a random one among the edges with the smallest weight. - `'matching'`: Contract an edge in a maximum matching. - `'weight_and_matching'`: Contract an edge in a maximum matching of the subgraph of the intermediate fusion network induced by the edges with the smallest weight. - `'random'`: Contract a random edge. optimize_num_fusions : bool (default: False) If `True`, use the average number of fusion attempts to quantify resource overheads instead of the average number of basic resource states. seed : 'keep' or None or int (default: 'keep') Random seed. - `'keep'`: The seed is not initialized. - `None`: The current time is used as the random seed. - `int`: The given number is used as the random seed. If `n_iter>1`, the given seed is used to sample random seeds for individual iterations. However, if `n_iter==1`, the given seed is used as the random seed for the (only one) iteration itself. verbose : bool (default: True) Whether to print logs. pbar : bool (default: True) Whether to show a progress bar. Ignored if tqdm is not installed. kwargs : dict Additional keyword arguments for calculating overheads. See the description of `GraphState.calculate_overhead()`. Returns ------- res : dict Dictionary containing the results of the iterations with keys: - `'best_overhead'`: Overhead of the best sample (i.e., sample with the smallest overhead or avg fusion number, determined by parameter `optimize_num_fusions`). - `'best_num_fusions'`: Average number of fusions of the best sample. - `'best_num_steps'`: Number of steps (i.e., groups of fusions that can be done in parallel) of the best sample. - `'best_seed'`: Random seed for the best sample. To recover the sample from it, use the `seed` parameter of `GraphState.simulate()` with `n_iter=1`. - `'n_iter'`: Number of iterations. Same as parameter `n_iter`. - `'unravel_bcs_first'`: Whether to unravel BCSs or cliques first for the best sample. - `'overheads'`, `'nums_fusions'`, `'nums_steps'`, `'seeds'`: Lists of the overheads, avg fusion numbers, step numbers, and seeds of all samples, respectively. Exist only when `get_all_data==True`. - `'unraveled_graphs'`: List of the unraveled graphs of all samples. Exists only when `get_all_graphs==True`. - `'fusion_networks'`: List of the fusion networks of all samples. Exists only when `get_all_fusion_networks==True`. """ t0 = time.time() overhead_key = 'num_fusions' if optimize_num_fusions else 'overhead' if seed != 'keep': np.random.seed(seed) if mp: if n_procs is None: n_procs = os.cpu_count() mp = mp and n_iter >= n_procs if not mp: if verbose: print("Multiprocessing OFF.") print(f"Calculating for n_iter = {n_iter}...") if 'tqdm' not in sys.modules: pbar = False if verbose: print("Install tqdm package to see the progress bar.") if n_iter == 1 and seed is not None and seed != 'keep': seeds_samples = [seed] else: seeds_samples = np.random.randint(0, _max_seed(), size=n_iter) overheads = [] if get_all_data else None nums_fusions = [] if get_all_data else None nums_steps = [] if get_all_data else None seeds = [] if get_all_data else None unravalled_graphs = [] if get_all_graphs else None fusion_networks = [] if get_all_fusion_networks else None best_sample = None lowest_overhead = None iterable = range(n_iter) if pbar: iterable = tqdm.tqdm(iterable) for i_sample in iterable: seed_sample = seeds_samples[i_sample] np.random.seed(seed_sample) if unravel: self.unraveled_graph = None try: self.unravel_graph(unravel_bcs_first=unravel_bcs_first) except: print('Error occurs during unraveling') print('seed =', seed_sample) raise ValueError try: self.build_fusion_network(use_unraveled_graph=unravel) except: print('Error occurs during building fusion network') print('seed =', seed_sample) raise ValueError try: data_now = self.calculate_overhead( p_succ=p_succ, strategy=fusion_order_strategy, optimize_num_fusions=optimize_num_fusions, **kwargs) except: print('Error occurs during calculating overhead') print('seed =', seed_sample) raise ValueError overhead_now = data_now[overhead_key] num_steps_now = data_now['num_steps'] self.data['seed'] = seed_sample if lowest_overhead is None or overhead_now < lowest_overhead: best_sample = i_sample lowest_overhead = overhead_now best_gs = self.copy() if get_all_data: overheads.append(data_now['overhead']) nums_fusions.append(data_now['num_fusions']) nums_steps.append(num_steps_now) seeds.append(seed_sample) if get_all_graphs: unravalled_graphs.append(self.unraveled_graph) if get_all_fusion_networks: fusion_networks.append(self.fusion_network) res = { 'best_overhead': best_gs.data['overhead'], 'best_num_fusions': best_gs.data['num_fusions'], 'best_num_steps': best_gs.data['num_steps'], 'best_seed': best_gs.data['seed'], 'n_iter': n_iter} if unravel: res['unravel_bcs_first'] = best_gs.data['unravel_bcs_first'] if get_all_data or get_all_graphs or get_all_fusion_networks: res['best_sample'] = best_sample if get_all_data: res['overheads'] = overheads res['nums_fusions'] = nums_fusions res['nums_steps'] = nums_steps res['seeds'] = seeds if get_all_graphs: res['unraveled_graphs'] = unravalled_graphs if get_all_fusion_networks: res['fusion_networks'] = fusion_networks else: if 'parmap' not in sys.modules: raise ModuleNotFoundError("Package parmap is not installed.") if verbose: print(f"Multiprocessing ON: n_procs = {n_procs}") print(f"Calculating for n_iter = {n_iter}... ", end='') additional_keys = [] if get_all_data: additional_keys.extend(['overheads', 'nums_fusions', 'nums_steps', 'seeds']) if get_all_graphs: additional_keys.append('unraveled_graphs') if get_all_fusion_networks: additional_keys.append('fusion_networks') left = n_iter % n_procs ns_samples = [n_iter // n_procs] * n_procs for i in range(left): ns_samples[i] += 1 seeds = np.random.randint(0, _max_seed(), size=n_procs) res_procs = parmap.starmap( _simulate_single, list(zip(ns_samples, seeds)), self.graph, p_succ=p_succ, get_all_data=get_all_data, get_all_graphs=get_all_graphs, get_all_fusion_networks=get_all_fusion_networks, unravel=unravel, unravel_bcs_first=unravel_bcs_first, fusion_order_strategy=fusion_order_strategy, optimize_num_fusions=optimize_num_fusions, pbar=False, pm_pbar=pbar, **kwargs) best_proc = np.argmin( [res_each[f'best_{overhead_key}'] for res_each in res_procs] ) res = res_procs[best_proc] res['n_iter'] = n_iter best_gs = res['best_gs'] del res['best_gs'] if additional_keys: res['best_sample'] += sum(ns_samples[:best_proc]) for key in additional_keys: vals = [res_each[key] for res_each in res_procs] res[key] = list(itertools.chain(*vals)) if verbose: print(f"Done. Best: {res[f'best_{overhead_key}']:.2f} " f"({time.time() - t0:.2f} s)") self.unraveled_graph = best_gs.unraveled_graph self.fusion_network = best_gs.fusion_network self.data = best_gs.data return res def simulate_adaptive(self, init_n_iter, mul=2, p_succ=0.5, mp=False, n_procs=None, get_all_data=False, get_all_graphs=False, get_all_fusion_networks=False, unravel=True, unravel_bcs_first='random', fusion_order_strategy='weight_and_matching', optimize_num_fusions=False, seed='keep', verbose=True, pbar=True, **kwargs)-
Run the adaptive iteration method for the strategy and obtain the best one only (by default).
The adaptive iteration method looks for the best iteration while keeps increasing the iteration number until a certain condition meets. In detail, denoting N iterations of the strategy as R(N), R(
init_n_iter) is first executed andq0is obtained which is the lowest resource overhead. Then, R(mul*init_n_iter) is executed andq1is obtained similarly. Ifq0 <= q1,q0is returned. If otherwise, R(mul**2*init_n_iter) is executed andq2is obtained. Ifq1 <= q2,q1is returned. If otherwise, R(mul**3*init_n_iter) is executed, and so on.Parameters
init_n_iter:int- Initial iteration number.
mul:int (default: 2)- Multiplicative factor of the iteration number.
See the description of
GraphState.simulate()for the other parameters.Returns
res:dict- Dictionary containing the results of the iterations.
See the description of
GraphState.simulate()for its keys.
Expand source code
def simulate_adaptive(self, init_n_iter, mul=2, p_succ=0.5, mp=False, n_procs=None, get_all_data=False, get_all_graphs=False, get_all_fusion_networks=False, unravel=True, unravel_bcs_first='random', fusion_order_strategy='weight_and_matching', optimize_num_fusions=False, seed='keep', verbose=True, pbar=True, **kwargs): """ Run the adaptive iteration method for the strategy and obtain the best one only (by default). The adaptive iteration method looks for the best iteration while keeps increasing the iteration number until a certain condition meets. In detail, denoting N iterations of the strategy as R(N), R(`init_n_iter`) is first executed and `q0` is obtained which is the lowest resource overhead. Then, R(`mul`*`init_n_iter`) is executed and `q1` is obtained similarly. If `q0 <= q1`, `q0` is returned. If otherwise, R(`mul**2*init_n_iter`) is executed and `q2` is obtained. If `q1 <= q2`, `q1` is returned. If otherwise, R(`mul**3*init_n_iter`) is executed, and so on. Parameters ---------- init_n_iter : int Initial iteration number. mul : int (default: 2) Multiplicative factor of the iteration number. See the description of `GraphState.simulate()` for the other parameters. Returns ------- res : dict Dictionary containing the results of the iterations. See the description of `GraphState.simulate()` for its keys. """ if mp and n_procs is None: n_procs = os.cpu_count() if seed != 'keep': np.random.seed(seed) additional_keys = [] if get_all_data: additional_keys.extend(['overheads', 'nums_fusions', 'nums_steps']) if get_all_graphs: additional_keys.append('unraveled_graphs') if get_all_fusion_networks: additional_keys.append('fusion_networks') if verbose: if mp: print(f"Multiprocessing (n_procs = {n_procs})") else: print("No multiprocessing") best_overhead_key \ = 'best_num_fusions' if optimize_num_fusions else 'best_overhead' n_iter_history = [] n_iter_now = init_n_iter res = None while True: if verbose: print(f"Calculating for n_iter = {n_iter_now}... ", end='') t0 = time.time() n_iter_history.append(n_iter_now) res_now = self.simulate( n_iter=n_iter_now, p_succ=p_succ, mp=mp, n_procs=n_procs, get_all_data=get_all_data, get_all_graphs=get_all_graphs, get_all_fusion_networks=get_all_fusion_networks, unravel=unravel, unravel_bcs_first=unravel_bcs_first, fusion_order_strategy=fusion_order_strategy, optimize_num_fusions=optimize_num_fusions, verbose=False, pbar=pbar, **kwargs ) if res is None: res = res_now best_gs = self.copy() n_iter_now *= mul else: for key in additional_keys: res[key].extend(res_now[key]) if res_now[best_overhead_key] < res[best_overhead_key]: for key in additional_keys: res_now[key] = res[key] res = res_now best_gs = self.copy() n_iter_now *= mul else: if verbose: print(f"Done. Best: {res[best_overhead_key]:.2f} (" f"{time.time() - t0:.2f} s)") break if verbose: print(f"Done. Best: {res[best_overhead_key]:.2f} " f"({time.time() - t0:.2f} s)") res['n_iter'] = sum(n_iter_history) if additional_keys: res['best_sample'] += res['best_sample'] self.unraveled_graph = best_gs.unraveled_graph self.fusion_network = best_gs.fusion_network self.data = best_gs.data return res def unravel_bcss(self, verbose=False)-
Unravel bipartitely-complete subgraphs (BCSs) of the graph.
The unraveled graph is saved in
GraphState.unraveled_graphasigraph.Graph.Parameters
verbose:bool (default: False)- Whether to print logs and plot the intermediate graphs during the unraveling process.
Returns
bcss:listoflistof2-tupleoflistofstr-
Information on the unraveled BCSs.
bcss[i][j][k][l](k=0 or 1) is the name of thel-th vertex in thek-th part of thej-th BCS obtained by thei-th cycle of finding non-overlapping BCSs.
Expand source code
def unravel_bcss(self, verbose=False): """ Unravel bipartitely-complete subgraphs (BCSs) of the graph. The unraveled graph is saved in `GraphState.unraveled_graph` as [`igraph.Graph`](https://python.igraph.org/en/stable/api/igraph.Graph.html). Parameters ---------- verbose : bool (default: False) Whether to print logs and plot the intermediate graphs during the unraveling process. Returns ------- bcss : list of list of 2-tuple of list of str Information on the unraveled BCSs. `bcss[i][j][k][l]` (`k`=0 or 1) is the name of the `l`-th vertex in the `k`-th part of the `j`-th BCS obtained by the `i`-th cycle of finding non-overlapping BCSs. """ if self.unraveled_graph is None: self.unraveled_graph = self.graph.copy() graph = self.unraveled_graph vs_attrs = graph.vs.attributes() if 'ext_fusion' not in vs_attrs: graph.vs['ext_fusion'] = None if 'clifford' not in vs_attrs: graph.vs['clifford'] = None unraveled_bcss = [] new_vertex_name = graph.vcount() while True: # Repeat until there are no bipartitely-complete subgraphs bcs_exist = False while True: bcss = find_nonoverlapping_bcss(graph, get_name=True) if bcss: bcs_exist = True else: break unraveled_bcss.append(bcss) eids_to_remove = [] for part1, part2 in bcss: if verbose: graph.delete_edges(eids_to_remove) eids_to_remove.clear() print('bcs to unravel =', part1, '&', part2) vertex_color = [] for v in graph.vs: if v['name'] in part1: vertex_color.append('orange') elif v['name'] in part2: vertex_color.append('blue') else: vertex_color.append('white') self.plot_graph(unraveled=True, vertex_color=vertex_color) plt.show() eids_to_remove.extend([graph.get_eid(vname1, vname2) for vname1, vname2 in itertools.product(part1, part2)]) vname1 = str(new_vertex_name) vname2 = str(new_vertex_name + 1) new_v1 = graph.add_vertex(name=vname1, ext_fusion=vname2, clifford=None) new_v2 = graph.add_vertex(name=vname2, ext_fusion=vname1, clifford=None) new_vertex_name += 2 graph.add_edges(itertools.product([new_v1], part1)) graph.add_edges(itertools.product([new_v2], part2)) graph.delete_edges(eids_to_remove) if not bcs_exist: break return unraveled_bcss def unravel_cliques(self, verbose=False)-
Unravel cliques of the graph.
The unraveled graph is saved in
GraphState.unraveled_graphasigraph.Graph.Parameters
verbose:bool (default: False)- Whether to print logs and plot the intermediate graphs during the unraveling process.
Returns
cliques:listoflistofsetofstr-
Information on the unraveled cliques.
cliques[i][j]is the set of the names of the vertices in thej-th clique obtained by thei-th cycle of finding non-overlapping cliques.
Expand source code
def unravel_cliques(self, verbose=False): """ Unravel cliques of the graph. The unraveled graph is saved in `GraphState.unraveled_graph` as [`igraph.Graph`](https://python.igraph.org/en/stable/api/igraph.Graph.html). Parameters ---------- verbose : bool (default: False) Whether to print logs and plot the intermediate graphs during the unraveling process. Returns ------- cliques : list of list of set of str Information on the unraveled cliques. `cliques[i][j]` is the set of the names of the vertices in the `j`-th clique obtained by the `i`-th cycle of finding non-overlapping cliques. """ if self.unraveled_graph is None: self.unraveled_graph = self.graph.copy() graph = self.unraveled_graph vs_attrs = graph.vs.attributes() if 'ext_fusion' not in vs_attrs: graph.vs['ext_fusion'] = None if 'clifford' not in vs_attrs: graph.vs['clifford'] = None unraveled_cliques = [] def apply_clifford(v, clifford): org_clifford = v['clifford'] if org_clifford is None: new_clifford = clifford else: new_clifford = '-'.join([clifford, org_clifford]) v['clifford'] = new_clifford while True: cliques = find_nonoverlapping_cliques(graph, get_name=True) if not cliques: break unraveled_cliques.append(cliques) for clique in cliques: if verbose: print('clique to unravel =', clique) vertex_color = ['orange' if vname in clique else 'white' for vname in graph.vs['name']] self.plot_graph(unraveled=True, vertex_color=vertex_color) plt.show() clique = list(clique) clique_size = len(clique) # Choose a vertex to apply LC degrees = graph.degree(clique) min_degree = min(degrees) if min_degree == clique_size - 1: # There exists a vertex in the clique that doesn't have # outer edges vname_LC = [vname for vname, deg in zip(clique, degrees) if deg == min_degree] need_to_separate = False else: vname_LC = clique need_to_separate = True if len(vname_LC) > 1: vname_LC = np.random.choice(vname_LC) else: vname_LC = vname_LC[0] old_v_LC = graph.vs.find(name=vname_LC) # Separate the edges (E) incident to v_LC outside the clique # from v_LC eids_to_delete = [] if need_to_separate: # Alter v_LC old_v_LC['name'] = str(graph.vcount()) new_v_LC = graph.add_vertex( name=vname_LC, clifford=old_v_LC['clifford'], ext_fusion=old_v_LC['ext_fusion'] ) # Vertex having an external fusion with old v_LC v_ext_fusion = graph.add_vertex( name=str(graph.vcount()), clifford=None, ext_fusion=old_v_LC['name'] ) # Modify old v_LC old_v_LC['clifford'] = None old_v_LC['ext_fusion'] = v_ext_fusion['name'] graph.add_edge(new_v_LC, v_ext_fusion) old_vid_LC = old_v_LC.index ngh_vids = graph.neighbors(old_vid_LC) for ngh_vid in ngh_vids: if graph.vs[ngh_vid]['name'] not in clique: graph.add_edge(ngh_vid, new_v_LC.index) eids_to_delete.append( graph.get_eid(old_vid_LC, ngh_vid) ) # Remove edges adj_vnames = set(clique) - {vname_LC} new_eids_to_delete = [graph.get_eid(vname1, vname2) for vname1, vname2 in itertools.combinations(adj_vnames, r=2)] eids_to_delete.extend(new_eids_to_delete) graph.delete_edges(eids_to_delete) # Apply LC apply_clifford(old_v_LC, 'RXd') for adj_vname in adj_vnames: adj_v = graph.vs.find(name=adj_vname) apply_clifford(adj_v, 'RZ') return unraveled_cliques def unravel_graph(self, unravel_bcs_first='random', plot=False, verbose=False)-
Unravel bipartitely-complete subgraphs (BCSs) and cliques of the graph.
The unraveled graph is saved in
self.unraveled_graphasigraph.Graph.Parameters
unravel_bcs_first:oneof[True, False, 'random'] (default: 'random')-
True: BCSs are unraveled first, then clqiues are unraveled.False: cliques are unraveled first, then BCSs are unraveled.'random': the order is randomly chosen.
plot:bool (default: False)- Whether to plot the unraveled graph after unraveling.
verbose:bool (default: False)- Whether to print logs and plot the intermediate graphs during the unraveling process.
Returns
bcss:listoflistof2-tupleoflistofstr-
Information on the unraveled BCSs.
bcss[i][j][k][l](k=0 or 1) is the name of thel-th vertex in thek-th part of thej-th BCS obtained by thei-th cycle of finding non-overlapping BCSs. cliques:listoflistofsetofstr-
Information on the unraveled cliques.
cliques[i][j]is the set of the names of the vertices in thej-th clique obtained by thei-th cycle of finding non-overlapping cliques. unravel_bcs_first:bool- Whether BCSs are unraveled first or not.
Expand source code
def unravel_graph(self, unravel_bcs_first='random', plot=False, verbose=False): """ Unravel bipartitely-complete subgraphs (BCSs) and cliques of the graph. The unraveled graph is saved in `self.unraveled_graph` as [`igraph.Graph`](https://python.igraph.org/en/stable/api/igraph.Graph.html). Parameters ---------- unravel_bcs_first : one of [True, False, 'random'] (default: 'random') - `True`: BCSs are unraveled first, then clqiues are unraveled. - `False`: cliques are unraveled first, then BCSs are unraveled.<br> - `'random'`: the order is randomly chosen. plot : bool (default: False) Whether to plot the unraveled graph after unraveling. verbose : bool (default: False) Whether to print logs and plot the intermediate graphs during the unraveling process. Returns ------- bcss : list of list of 2-tuple of list of str Information on the unraveled BCSs. `bcss[i][j][k][l]` (`k`=0 or 1) is the name of the `l`-th vertex in the `k`-th part of the `j`-th BCS obtained by the `i`-th cycle of finding non-overlapping BCSs. cliques : list of list of set of str Information on the unraveled cliques. `cliques[i][j]` is the set of the names of the vertices in the `j`-th clique obtained by the `i`-th cycle of finding non-overlapping cliques. unravel_bcs_first : bool Whether BCSs are unraveled first or not. """ if unravel_bcs_first == 'random': unravel_bcs_first = np.random.choice([True, False]) if unravel_bcs_first: bcss = self.unravel_bcss(verbose=verbose) cliques = self.unravel_cliques(verbose=verbose) else: cliques = self.unravel_cliques(verbose=verbose) bcss = self.unravel_bcss(verbose=verbose) if plot or verbose: if verbose: print('[Final]') self.plot_graph(unraveled=True) plt.show() self.data['unravel'] = True self.data['unravel_bcs_first'] = unravel_bcs_first return bcss, cliques, unravel_bcs_first
- Given explicitly by