routing

A toolkit for the SABRE algorithm.

Classes:

Name	Description
SabreRouting	SABRE-based routing pass for quantum circuit transpilation.

Functions:

Name	Description
extract_qubits	Extracts qubit indices from the node name string.
update_v2p_and_p2v_mapping	Update v2p and p2v mappings based on the given SWAP gate.

SabreRouting(subgraph: nx.Graph, initial_mapping: Literal['random', 'trivial'] | list = 'trivial', do_random_choice: bool = False, iterations: int = 5, heuristic: Literal['basic', 'lookahead', 'basic_decay', 'lookahead_decay'] = 'lookahead_decay', max_extended_set_weight: float = 0.5)

Bases: TranspilerPass

SABRE-based routing pass for quantum circuit transpilation.

Parameters:

Name	Type	Description	Default
TranspilerPass	class	The base class that provides the infrastructure for the transpiler pass functionality.	required

Initializes the SabreRouting class with the specified settings.

Parameters:

Name	Type	Description	Default
subgraph	Graph	A subgraph of the hardware's coupling graph, containing only the physical qubits relevant for the current circuit.	required
initial_mapping	Literal['random', 'trivial']	Strategy for initializing the virtual-to-physical qubit mapping. Options: - 'trivial': Maps virtual qubits to physical qubits sequentially. - 'random': Maps virtual qubits to physical qubits randomly. Defaults to 'trivial'.	'trivial'
do_random_choice	bool	If True, randomly chooses a SWAP when multiple options have the same score. Defaults to False.	False
iterations	int	The number of iterations for the SABRE routing process. Defaults to 5.	5
heuristic	Literal['basic', 'lookahead', 'basic_decay', 'lookahead_decay']	The heuristic strategy used to evaluate candidate SWAP gates.Defaults to 'lookahead_decay'.	'lookahead_decay'
max_extended_set_weight	float	The max weight of extended set. Defaults to 0.5.	0.5

Methods:

Name	Description
run	Routing based on the Sabre algorithm.

Source code in quark/circuit/routing.py

def __init__(self,
             subgraph:nx.Graph,
             initial_mapping:Literal['random','trivial']|list = 'trivial',
             do_random_choice:bool = False,
             iterations: int = 5,
             heuristic: Literal['basic','lookahead','basic_decay','lookahead_decay']='lookahead_decay',
             max_extended_set_weight:float = 0.5, # validate when heuristic='lookahead'|'lookahead' 
             ):
    """Initializes the SabreRouting class with the specified settings.

    Args:
        subgraph (nx.Graph): A subgraph of the hardware's coupling graph, containing 
            only the physical qubits relevant for the current circuit.
        initial_mapping (Literal['random','trivial'], optional): Strategy for initializing 
            the virtual-to-physical qubit mapping. Options:
            - 'trivial': Maps virtual qubits to physical qubits sequentially.
            - 'random': Maps virtual qubits to physical qubits randomly.
            Defaults to 'trivial'.
        do_random_choice (bool, optional): If True, randomly chooses a SWAP when 
            multiple options have the same score. Defaults to False.
        iterations (int, optional): The number of iterations for the SABRE routing process. Defaults to 5.
        heuristic (Literal['basic', 'lookahead', 'basic_decay', 'lookahead_decay'], optional):
            The heuristic strategy used to evaluate candidate SWAP gates.Defaults to 'lookahead_decay'.

        max_extended_set_weight (float, optional): The max weight of extended set. Defaults to 0.5.
    """
    super().__init__()
    self.coupling_graph = subgraph
    self.distance_matrix = floyd_warshall_numpy(subgraph)
    if 'normal_order' not in subgraph.graph:
        subgraph.graph['normal_order'] = list(subgraph.nodes())
    self.physical_qubits = subgraph.graph['normal_order'] # list(sorted(subgraph.nodes()))
    self.physical_qubits_index = dict(zip(list(subgraph.nodes),range(len(subgraph.nodes))))
    self.initial_mapping = initial_mapping
    self.do_random_choice = do_random_choice
    self.iterations = iterations
    self.heuristic = heuristic
    self.extended_successor_set = []
    self.max_extended_set_weight = max_extended_set_weight
    self.decay_parameter = {}

    self._cache = OrderedDict()

run(qc: QuantumCircuit)

Routing based on the Sabre algorithm. Args: iterations (int, optional): The number of iterations. Defaults to 1. Returns: Transpiler: Update self information.

Source code in quark/circuit/routing.py

def run(self,qc:QuantumCircuit,):
    """Routing based on the Sabre algorithm.
    Args:
        iterations (int, optional): The number of iterations. Defaults to 1.
    Returns:
        Transpiler: Update self information.
    """

    all_qubits = split_qubits(qc)
    virtual_qubits = [x for sub in all_qubits for x in sub]

    self.v2p, self.p2v = self._initialize_v2p_p2v(virtual_qubits)
    init_p2v = {p:v for v,p in self.v2p.items()}

    dag = qc2dag(qc,show_qubits=False)
    rev_qc = qc.deepcopy()
    rev_qc.gates.reverse()
    rev_dag = qc2dag(rev_qc,show_qubits=False)
    self.do_map_node_to_gate = False
    for idx in range(self.iterations):
        if idx == self.iterations-1:
            self.do_map_node_to_gate = True
        if idx%2 == 0:
            self.dag_id = 'forward'
            self.dag = dag
        else:
            self.dag_id = 'reverse'
            self.dag = rev_dag

        new,nswap = self._single_sabre_routing()

        if self.iterations == 1:
            best_p2v = init_p2v
        else:
            if idx == self.iterations-2:
                best_p2v = {p:v for v,p in self.v2p.items()}

    final_p2v = {p:v for v,p in self.v2p.items()}
    print('{:^21} -----> {:^21} -----> {:^21}'.format('initial mapping','best mapping','final mapping'))
    print('{:^10}:{:^10} -----> {:^10}:{:^10} -----> {:^10}:{:^10}'.format('P','V','P','V','P','V'))
    for p in sorted(init_p2v.keys()):
        print('{:^10}:{:^10} -----> {:^10}:{:^10} -----> {:^10}:{:^10}'.format(p,init_p2v[p],p,best_p2v[p],p,final_p2v[p]))
    print('A total of {} swap gates have been added to the circuit.'.format(nswap))
    new_qc = QuantumCircuit(max(self.physical_qubits)+1,qc.ncbits)
    new_qc.gates = new
    new_qc.params_value = qc.params_value
    new_qc.qubits = self.physical_qubits
    return new_qc 

extract_qubits(node_name: str)

Extracts qubit indices from the node name string.

This function parses the node name to find all qubit indices specified within square brackets (e.g., "[0,1]"), using regular expressions. It provides a faster alternative to accessing the 'qubits' attribute from a DAG node (e.g., dag.nodes[node]['qubits']).

Parameters:

Name	Type	Description	Default
node_name	str	The name of the node, expected to contain qubit information in square brackets.	required

Returns:

Type	Description
	List[int]: A list of qubit indices as integers, extracted in order
	of appearance. Returns an empty list if no qubit information is found.

Source code in quark/circuit/routing.py

def extract_qubits(node_name:str):
    """
    Extracts qubit indices from the node name string.

    This function parses the node name to find all qubit indices specified 
    within square brackets (e.g., "[0,1]"), using regular expressions.
    It provides a faster alternative to accessing the 'qubits' attribute 
    from a DAG node (e.g., dag.nodes[node]['qubits']).

    Args:
        node_name (str): The name of the node, expected to contain qubit 
            information in square brackets.

    Returns:
        List[int]: A list of qubit indices as integers, extracted in order 
        of appearance. Returns an empty list if no qubit information is found.
    """
    #qubit0 = dag.nodes[node]['qubits'][0] is too time-consuming
    bracket_content = re.search(r'\[([^\]]*)\]', node_name)
    if not bracket_content:
        return []
    return list(map(int, re.findall(r'\d+', bracket_content.group(1))))

update_v2p_and_p2v_mapping(v2p: dict, swap_gate_info: tuple) -> tuple[dict, dict]

Update v2p and p2v mappings based on the given SWAP gate.

Parameters:

Name	Type	Description	Default
v2p	dict	A dictionary mapping virtual qubits to physical qubits.	required
swap_gate_info	tuple	A tuple containing gate information. The format is (gate_name, vq1, vq2), where vq1 and vq2 are the virtual qubits being swapped.	required

Returns:

Type	Description
tuple[dict, dict]	tuple[dict, dict]: - Updated v2p mapping after applying the SWAP. - Updated p2v mapping.

Source code in quark/circuit/routing.py

def update_v2p_and_p2v_mapping(v2p:dict,swap_gate_info:tuple) -> tuple[dict,dict]:
    """Update v2p and p2v mappings based on the given SWAP gate.

    Args:
        v2p (dict): A dictionary mapping virtual qubits to physical qubits.
        swap_gate_info (tuple): A tuple containing gate information. The format is
            (gate_name, vq1, vq2), where vq1 and vq2 are the virtual qubits being swapped.

    Returns:
        tuple[dict, dict]: 
            - Updated v2p mapping after applying the SWAP.
            - Updated p2v mapping.
    """
    v2p = copy.deepcopy(v2p)
    vq1,vq2 = swap_gate_info[1:]
    v2p[vq1],v2p[vq2] = v2p[vq2],v2p[vq1]
    p2v = {p:v for v,p in v2p.items()}
    return v2p,p2v