layout

This module contains the Layout class, which is designed to select suitable layouts for quantum circuits on hardware backends.

Classes:

Name	Description
Layout	Responsible for selecting suitable qubit layouts from a given chip for a quantum circuit.

Layout(chip_backend: Backend)

Responsible for selecting suitable qubit layouts from a given chip for a quantum circuit.

This class generates qubit layouts based on the required number of qubits, performance metrics, and the topology of the chip. It is designed to help map and execute quantum circuits on specific quantum hardware.

Initialize the Layout class with the required number of qubits and chip backend.

Parameters:

Name	Type	Description	Default
nqubits	int	The number of qubits needed in the layout.	required
chip_backend	Backend	An instance of the Backend class that contains the information	required

Methods:

Name	Description
get_one_node_subgraph	Generates all possible subgraph combinations for a given node up to a specified number of nodes.
collect_all_subgraph_in_parallel	Collects all possible subgraph combinations for all nodes in the graph in parallel.
get_one_subgraph_info	Retrieves information about a specified subgraph.
collect_all_subgraph_info_in_parallel	Collects information about all subgraphs in parallel.
classify_all_subgraph_according_topology	Classify the collected subgraphs based on their topological structure into four categories.
sort_subgraph_according_mean_fidelity	Sort each of the four subgraph categories based on the main of fidelity on the edges (couplers),
sort_subgraph_according_var_fidelity	Sort each of the four subgraph categories based on the variance of fidelity on the edges (couplers),
select_few_qubits_from_backend	Select a qubit layout based on the given performance metric and topology.
select_much_qubits_from_backend	Perform a breadth-first search (BFS) on the graph starting from the start node,

Source code in quark/circuit/layout.py

def __init__(self, chip_backend: Backend):
    """Initialize the Layout class with the required number of qubits and chip backend.

    Args:
        nqubits (int): The number of qubits needed in the layout.
        chip_backend (Backend): An instance of the Backend class that contains the information 
        about the quantum chip to be used for layout selection
    """
    self.priority_qubits = chip_backend.priority_qubits
    self.graph = chip_backend.edge_filtered_graph(thres=0.6)
    self.ncore = os.cpu_count() // 2 
    self.fidelity_mean_threshold = 0.9
    self.edge_fidelitys = nx.get_edge_attributes(self.graph,'fidelity') #提前存下边信息节约计算资源
    self.algorithm_switch_threshold = 10

get_one_node_subgraph(node: int, nqubits: int)

Generates all possible subgraph combinations for a given node up to a specified number of nodes.

Parameters:

Name	Type	Description	Default
node	int	The starting node for generating subgraph combinations.	required

Returns:

Type	Description
	list[tuple]:A list of tuples, each representing a unique combination of nodes that form a subgraph up to the specified nqubits in size.

Source code in quark/circuit/layout.py

def get_one_node_subgraph(self,node:int,nqubits:int):
    """Generates all possible subgraph combinations for a given node up to a specified number of nodes.

    Args:
        node (int): The starting node for generating subgraph combinations.

    Returns:
        list[tuple]:A list of tuples, each representing a unique combination of nodes that form
          a subgraph up to the specified `nqubits` in size.
    """

    def post_combinations(mid,dd,cut):
        rr = set([elem for node in mid if node in dd for elem in dd[node]])
        cc = []
        mm = min(cut,len(dd)) +1
        for idx in range(1,mm):
            cc +=  [list(comb) for comb in combinations(rr, idx)]
        return cc

    dd = self._get_node_connect_dict(node,nqubits)
    collect = []
    init = [{'pre':[],'mid':[node],'post':post_combinations([node],dd,nqubits-1)}]
    for _ in range(nqubits):
        update = []
        for c0 in init:
            new_pre = c0['pre'] + c0['mid']
            new_pre.sort()
            new_pre = list(set(new_pre))
            if len(new_pre) == nqubits:
                new_pre.sort()
                collect.append(tuple(new_pre))
            elif len(new_pre) < nqubits:
                if c0['post'] == []:
                    continue
                else:
                    for mid0 in c0['post']:
                        mid = [i for i in mid0 if i not in new_pre]
                        c1 = {'pre':new_pre,'mid':mid,'post':post_combinations(mid,dd,nqubits-len(new_pre+mid))}
                        update.append(c1)
        init = update
    return list(set(collect))

collect_all_subgraph_in_parallel(nqubits)

Collects all possible subgraph combinations for all nodes in the graph in parallel.

Returns:

Type	Description
	list[tuple]: A list of tuples, each representing a unique combination of nodes that form subgraphs for all nodes in the graph.

Source code in quark/circuit/layout.py

def collect_all_subgraph_in_parallel(self,nqubits):
    """Collects all possible subgraph combinations for all nodes in the graph in parallel.

    Returns:
        list[tuple]:  A list of tuples, each representing a unique combination of nodes that 
                 form subgraphs for all nodes in the graph.
    """
    collect_all = []
    with Pool(processes = self.ncore) as pool:
        res = pool.map(partial(self.get_one_node_subgraph,nqubits=nqubits),self.graph.nodes())
    for collect in res:
        collect_all += collect
    return collect_all

get_one_subgraph_info(nodes: tuple | list)

Retrieves information about a specified subgraph.

This method generates a subgraph from the given list of nodes, calculates the degree of each node within the subgraph, and computes the mean and variance of the edge weights (fidelity) in the subgraph.It returns the subgraph information only if the mean fidelity meets the specified threshold.

Parameters:

Name	Type	Description	Default
nodes	tuple | list	A list of nodes that define the subgraph.	required

Returns:

Type	Description
	tuple or None: A tuple containing the nodes, their degrees, mean fidelity, and variance of fidelity if the mean fidelity is greater than or equal to fidelity_mean_threshold. Otherwise, returns None.

Source code in quark/circuit/layout.py

def get_one_subgraph_info(self,nodes:tuple|list):
    """Retrieves information about a specified subgraph.

    This method generates a subgraph from the given list of nodes, calculates the degree of each node within the subgraph, 
    and computes the mean and variance of the edge weights (fidelity) in the subgraph.It returns the subgraph information 
    only if the mean fidelity meets the specified threshold.

    Args:
        nodes (tuple|list): A list of nodes that define the subgraph.

    Returns:
        tuple or None: A tuple containing the nodes, their degrees, mean fidelity, and variance of fidelity 
                       if the mean fidelity is greater than or equal to `fidelity_mean_threshold`. Otherwise, returns None.
    """
    subgraph = self.graph.subgraph(nodes)
    subgraph_degree = dict(subgraph.degree())
    subgraph_fidelity = np.array([self.edge_fidelitys[(min(edge),max(edge))] for edge in subgraph.edges])
    fidelity_mean = np.mean(subgraph_fidelity)
    fidelity_var  = np.var(subgraph_fidelity)  
    if fidelity_mean >= self.fidelity_mean_threshold:
        if set(subgraph_degree.values()) == {1, 2}: #simple linear
            topology = 'linear'
            end_start_nodes = [k for k,v in subgraph_degree.items() if v==1]
            ordered_nodes = nx.shortest_path(subgraph,end_start_nodes[0],end_start_nodes[1])                
            nodes_info = (ordered_nodes,topology,fidelity_mean,fidelity_var)
        elif set(subgraph_degree.values()) == {2}: #simple circular
            topology = 'circular'
            nodes_info = (nodes,topology,fidelity_mean,fidelity_var)
        else:
            simple_cycles = list(nx.simple_cycles(subgraph))
            cycles = sorted(simple_cycles,key=len)
            if cycles and len(cycles[-1]) == len(subgraph_degree):
                topology = 'circular'
                nodes_info = (nodes,topology,fidelity_mean,fidelity_var)
            else:
                topology = 'nonlinear'
                nodes_info = (nodes,topology,fidelity_mean,fidelity_var)                                      
        # if max(subgraph_degree.values()) <= 2:
        #     end_start_nodes = [k for k,v in subgraph_degree.items() if v==1]
        #     if len(end_start_nodes) == 2:
        #         topology = 'linear'
        #         ordered_nodes = nx.shortest_path(subgraph,end_start_nodes[0],end_start_nodes[1])                
        #         nodes_info = (ordered_nodes,topology,fidelity_mean,fidelity_var)
        #     else:
        #         topology = 'circular'
        #         nodes_info = (nodes,topology,fidelity_mean,fidelity_var)
        # else:
        #     topology = 'nonlinear'
        #     nodes_info = (nodes,topology,fidelity_mean,fidelity_var)
        return nodes_info
    else:
        return None

collect_all_subgraph_info_in_parallel(nqubits: int)

Collects information about all subgraphs in parallel.

Returns:

Name	Type	Description
list		A list of results, where each entry corresponds to the information of a subgraph.

Source code in quark/circuit/layout.py

def collect_all_subgraph_info_in_parallel(self,nqubits:int):
    """Collects information about all subgraphs in parallel.

    Returns:
        list: A list of results, where each entry corresponds to the information of a subgraph. 
    """
    all_subgraph = self.collect_all_subgraph_in_parallel(nqubits)
    with Pool(processes = self.ncore) as pool:
        res = pool.map(partial(self.get_one_subgraph_info),all_subgraph)
    return res  

classify_all_subgraph_according_topology(nqubits: int) -> tuple[list, list, list, list]

Classify the collected subgraphs based on their topological structure into four categories.

This function sorts the subgraphs into the following four categories: 1. Linear and connected, with all nodes in the same row of the chip. 2. Linear and connected, with nodes not in the same row. 3. Contains a cycle within the subgraph. 4. Non-linear and connected, where some nodes have more than three edges.

Returns:

Type	Description
list	tuple[list, list, list, list]: A tuple containing four lists, each corresponding
list	to one of the four categories of subgraphs.

Source code in quark/circuit/layout.py

def classify_all_subgraph_according_topology(self,nqubits:int) -> tuple[list,list,list,list]:
    """
    Classify the collected subgraphs based on their topological structure into four categories.

    This function sorts the subgraphs into the following four categories:
    1. Linear and connected, with all nodes in the same row of the chip.
    2. Linear and connected, with nodes not in the same row.
    3. Contains a cycle within the subgraph.
    4. Non-linear and connected, where some nodes have more than three edges.

    Returns:
        tuple[list, list, list, list]: A tuple containing four lists, each corresponding 
        to one of the four categories of subgraphs.
    """

    linear_subgraph_list  = []
    nonlinear_subgraph_list = []
    all_subgraph_info = self.collect_all_subgraph_info_in_parallel(nqubits)

    for subgraph_info in filter(lambda x: x is not None, all_subgraph_info):
        nodes,topology,fidelity_mean,fidelity_var = subgraph_info
        nodes_info = (nodes, fidelity_mean, fidelity_var)
        if topology == 'linear' or topology == 'circular':
            linear_subgraph_list.append(nodes_info)
        elif topology == 'nonlinear':
            nonlinear_subgraph_list.append(nodes_info)
    return linear_subgraph_list,nonlinear_subgraph_list

sort_subgraph_according_mean_fidelity(nqubits: int, num: int = 1, printdetails: bool = True)

Sort each of the four subgraph categories based on the main of fidelity on the edges (couplers), in ascending order.

Parameters:

Name	Type	Description	Default
printdetails	bool	If True, print details of the sorting process. Defaults to True.	True

Returns:

Type	Description
	tuple[list, list, list, list]: Four sorted lists, each corresponding to one of the four
	subgraph categories, with subgraphs sorted by edge fidelity variance.

Source code in quark/circuit/layout.py

def sort_subgraph_according_mean_fidelity(self, nqubits:int, num:int=1,  printdetails: bool = True):
    """Sort each of the four subgraph categories based on the main of fidelity on the edges (couplers), 
    in ascending order.

    Args:
        printdetails (bool, optional): If True, print details of the sorting process. Defaults to True.

    Returns:
        tuple[list, list, list, list]: Four sorted lists, each corresponding to one of the four 
        subgraph categories, with subgraphs sorted by edge fidelity variance.
    """
    linear_subgraph_list, nonlinear_subgraph_list = self.classify_all_subgraph_according_topology(nqubits)
    linear_subgraph_list_sort = sorted(linear_subgraph_list,key=lambda x: x[1],reverse=True)
    nonlinear_subgraph_list_sort = sorted(nonlinear_subgraph_list,key=lambda x: x[1],reverse=True)
    if printdetails:
        print(len(linear_subgraph_list_sort),len(nonlinear_subgraph_list_sort))
        print('The average fidelity is arranged in descending order,only print the first ten.')
        length = nqubits*5+22

        print('{:<3} | {:^{}} | {:^{}} '.format(\
            'idx','subgraph with linear topology',length,'subgraph with nonlinear topology',length))
        for i, (linear,nonlinear) in enumerate(zip_longest(linear_subgraph_list_sort,nonlinear_subgraph_list_sort, fillvalue=' ')):
            if i >= len(linear_subgraph_list_sort):
                linear = ('(                  )',0.0,0.0)
            if i >= len(nonlinear_subgraph_list_sort):
                nonlinear = ('(                  )',0.0,0.0)
            if i <= num:
                print('{:<3} | {:<{}} {:<10.6f} {:<10.6f} | {:<{}} {:<10.6f} {:<10.6f} '\
                      .format(i, \
                              str(linear[0]),nqubits*5,linear[1],linear[2],\
                              str(nonlinear[0]),nqubits*5,nonlinear[1],nonlinear[2])\
                              )

    return linear_subgraph_list_sort[:num],nonlinear_subgraph_list_sort[:num]

sort_subgraph_according_var_fidelity(nqubits: int, num: int = 1, printdetails: bool = True)

Sort each of the four subgraph categories based on the variance of fidelity on the edges (couplers), in ascending order.

This function sorts the subgraphs within each category (from the previous classification) by the variance of fidelity across the edges in each subgraph, from lowest to highest.

Parameters:

Name	Type	Description	Default
printdetails	bool	If True, print details of the sorting process. Defaults to True.	True

Returns:

Type	Description
	tuple[list, list, list, list]: Four sorted lists, each corresponding to one of the four
	subgraph categories, with subgraphs sorted by edge fidelity variance.

Source code in quark/circuit/layout.py

def sort_subgraph_according_var_fidelity(self, nqubits:int, num:int = 1, printdetails: bool = True):
    """
    Sort each of the four subgraph categories based on the variance of fidelity on the edges (couplers), 
    in ascending order.

    This function sorts the subgraphs within each category (from the previous classification) by the 
    variance of fidelity across the edges in each subgraph, from lowest to highest.

    Args:
        printdetails (bool, optional): If True, print details of the sorting process. Defaults to True.

    Returns:
        tuple[list, list, list, list]: Four sorted lists, each corresponding to one of the four 
        subgraph categories, with subgraphs sorted by edge fidelity variance.
    """
    linear_subgraph_list, nonlinear_subgraph_list = self.classify_all_subgraph_according_topology(nqubits)
    linear_subgraph_list_sort = sorted(linear_subgraph_list,key=lambda x: x[2])
    nonlinear_subgraph_list_sort = sorted(nonlinear_subgraph_list,key=lambda x: x[2])

    if printdetails:
        print(len(linear_subgraph_list_sort),len(nonlinear_subgraph_list_sort))
        print('The average fidelity is arranged in descending order, only print the first ten.')
        length = nqubits*5+22

        print('{:<3} | {:^{}} | {:^{}} '.format(\
            'idx','subgraph with linear topology',length,'subgraph with nonlinear topology',length))
        for i, (linear,nonlinear) in enumerate(zip_longest(linear_subgraph_list_sort, nonlinear_subgraph_list_sort, fillvalue=' ')):
            if i >= len(linear_subgraph_list_sort):
                linear = ('(                  )',0.0,0.0)
            if i >= len(nonlinear_subgraph_list_sort):
                nonlinear = ('(                  )',0.0,0.0)

            if i <= num:
                print('{:<3} | {:<{}} {:<10.6f} {:<10.6f} | {:<{}} {:<10.6f} {:<10.6f} '\
                      .format(i, \
                              str(linear[0]),nqubits*5,linear[1],linear[2],\
                              str(nonlinear[0]),nqubits*5,nonlinear[1],nonlinear[2])\
                              )

    return linear_subgraph_list_sort[:num], nonlinear_subgraph_list_sort[:num]

select_few_qubits_from_backend(nqubits: int, key: Literal['fidelity_mean', 'fidelity_var'] = 'fidelity_var', topology: Literal['linear', 'nonlinear'] = 'linear', printdetails: bool = False)

Select a qubit layout based on the given performance metric and topology.

This function chooses a layout for the quantum circuit from the available subgraphs based on the specified key (performance metric) and topology type.

Parameters:

Name	Type	Description	Default
key	Literal['fidelity_mean', 'fidelity_var']	The performance metric to use for selecting the layout. Either the mean fidelity ('fidelity_mean') or fidelity variance ('fidelity_var'). Defaults to 'fidelity_var'.	'fidelity_var'
topology	Literal['cycle', 'linear1', 'linear', 'nonlinear']	The desired topology of the layout. It can be 'cycle', 'linear1' (connected, in the same row), 'linear' (connected, not necessarily in the same row), or 'nonlinear'. Defaults to 'linear1'.	'linear'
printdetails	bool	If True, prints details about the selected layout. Defaults to False.	False

Returns:

Name	Type	Description
list		A list of qubits representing the selected layout.

Source code in quark/circuit/layout.py

def select_few_qubits_from_backend(self, 
                                     nqubits:int,
                                     key: Literal['fidelity_mean', 'fidelity_var'] = 'fidelity_var',
                                     topology: Literal['linear', 'nonlinear'] = 'linear',
                                     printdetails: bool = False):
    """
    Select a qubit layout based on the given performance metric and topology.

    This function chooses a layout for the quantum circuit from the available subgraphs based on 
    the specified key (performance metric) and topology type.

    Args:
        key (Literal['fidelity_mean', 'fidelity_var'], optional): The performance metric to use for 
            selecting the layout. Either the mean fidelity ('fidelity_mean') or fidelity variance 
            ('fidelity_var'). Defaults to 'fidelity_var'.
        topology (Literal['cycle', 'linear1', 'linear', 'nonlinear'], optional): The desired topology 
            of the layout. It can be 'cycle', 'linear1' (connected, in the same row), 'linear' (connected, 
            not necessarily in the same row), or 'nonlinear'. Defaults to 'linear1'.
        printdetails (bool, optional): If True, prints details about the selected layout. Defaults to False.

    Returns:
        list: A list of qubits representing the selected layout.
    """
    if key == 'fidelity_mean':
        linear_list,nonlinear_list = self.sort_subgraph_according_mean_fidelity(nqubits,printdetails=printdetails)
    elif key == 'fidelity_var':
        linear_list,nonlinear_list = self.sort_subgraph_according_var_fidelity(nqubits, printdetails=printdetails)

    if topology == 'linear':
        layouts = linear_list
    elif topology == 'nonlinear':
        layouts = nonlinear_list

    if len(layouts) == 0:
        raise(ValueError(f'There is no {nqubits} qubits that meets both key = {key} and topology = {topology}. Please change the conditions.'))
    else:
        print(f'Physical qubits layout {layouts[0][0]} are selected by the local algorithm using key = {key} and topology = {topology}.')
        return list(layouts[0][0])

select_much_qubits_from_backend(nqubits)

Perform a breadth-first search (BFS) on the graph starting from the start node, collecting up to nqubits unique nodes including the start node.

Returns:

Name	Type	Description
list		A list of up to nqubits unique nodes, discovered in BFS order.

Source code in quark/circuit/layout.py

def select_much_qubits_from_backend(self,nqubits): #get_BFS_layout(self,nqubits:int):
    """ Perform a breadth-first search (BFS) on the graph starting from the start node,
    collecting up to `nqubits` unique nodes including the start node.

    Returns:
        list: A list of up to `nqubits` unique nodes, discovered in BFS order.
    """
    # self.graph = chip_backend.graph #chip_backend.edge_filtered_graph(thres=0.95)

    one_subgraph = self._get_largest_component()
    if len(one_subgraph.nodes()) < nqubits:
        raise(ValueError(f'The user circuit requires {nqubits} qubits exceeds the qubit capacity of the largest connected subgraph. This triggered by low fidelity filtering, if you insist on using more qubits, please contact the developer.'))
    start_node = np.random.choice(list(one_subgraph.nodes))

    visited = set([start_node])
    queue = [(start_node, 0)]  
    while queue and len(visited) < nqubits:
        current_node, depth = queue.pop(0)  
        if depth >= nqubits - 1:
            continue
        for neighbor in one_subgraph.neighbors(current_node):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, depth + 1))
                if len(visited) == nqubits:
                    break
    print(f'Physical qubits layout {list(visited)} are selected by BFS algorithm.') # with the corresponding coupling being {coupling_map}
    return list(visited)