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 res

Sub-modules

optgraphstate.graph_tools
optgraphstate.utils
optgraphstate.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:

  1. Given explicitly by igraph.Graph or networkx.Graph.
  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 ith-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 get_graph_from_edges() or 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, it is internally converted to igraph.Graph.

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, it is internally converted to igraph.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 copy

Class 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 None before 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 None before 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(), and GraphState.unravel_cliques() must be executed beforehand.

The constructed fusion network is saved in GraphState.fusion_network as igraph.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, 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.
The calculated overhead and number of steps can be obtained from data['overhead'] and data['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 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']).
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(), 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.

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

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.
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 : 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.
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 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.
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.
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 : 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.

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, 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.
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 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.
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_graph as igraph.Graph.

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.

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_graph as igraph.Graph.

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.

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_graph as igraph.Graph.

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.
  • '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.
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