Skip to content

shortest_path_router

ShortestPathRouter

Bases: Router

Source code in opensquirrel/passes/router/shortest_path_router.py 
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class ShortestPathRouter(Router):
    def __init__(self, connectivity: dict[str, list[int]], **kwargs: Any) -> None:
        super().__init__(**kwargs)
        self.connectivity = connectivity

    def _insert_and_propagate_swaps(self, ir: IR, statement_index: int, shortest_path: list[int]) -> None:
        for start_qubit_index, end_qubit_index in zip(shortest_path[:-2], shortest_path[1:-1]):
            ir.statements.insert(statement_index, SWAP(start_qubit_index, end_qubit_index))
            # Update subsequent statements to reflect the swap
            for statement in ir.statements[statement_index + 1 :]:
                if isinstance(statement, Instruction):
                    for qubit in statement.get_qubit_operands():
                        if qubit.index == start_qubit_index:
                            qubit.index = end_qubit_index
                        elif qubit.index == end_qubit_index:
                            qubit.index = start_qubit_index
            statement_index += 1

    def route(self, ir: IR) -> IR:
        """
        Routes the circuit by inserting SWAP gates along the shortest path between qubits which can not
        interact with each other, to make it executable given the hardware connectivity.
        Args:
            ir: The intermediate representation of the circuit.
        Returns:
            The intermediate representation of the routed circuit (including the additional SWAP gates).
        """
        graph_data = {int(start_node): end_nodes for start_node, end_nodes in self.connectivity.items()}
        graph = nx.Graph(graph_data)
        statement_index = 0
        while statement_index < len(ir.statements):
            statement = ir.statements[statement_index]
            if isinstance(statement, Gate) and len(statement.get_qubit_operands()) == 2:
                q0, q1 = statement.get_qubit_operands()
                if not graph.has_edge(q0.index, q1.index):
                    try:
                        shortest_path = nx.shortest_path(graph, source=q0.index, target=q1.index)
                        # -2 because we skip inserting a swap for the last edge in the path:
                        # len(path) - 1 edges in total
                        num_swaps_inserted = len(shortest_path) - 2
                        self._insert_and_propagate_swaps(ir, statement_index, shortest_path)
                        statement_index += num_swaps_inserted
                    except nx.NetworkXNoPath as e:
                        msg = f"No routing path available between qubit {q0.index} and qubit {q1.index}"
                        raise NoRoutingPathError(msg) from e
            statement_index += 1
        return ir

route(ir)

Routes the circuit by inserting SWAP gates along the shortest path between qubits which can not interact with each other, to make it executable given the hardware connectivity. Args: ir: The intermediate representation of the circuit. Returns: The intermediate representation of the routed circuit (including the additional SWAP gates).

Source code in opensquirrel/passes/router/shortest_path_router.py 
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
def route(self, ir: IR) -> IR:
    """
    Routes the circuit by inserting SWAP gates along the shortest path between qubits which can not
    interact with each other, to make it executable given the hardware connectivity.
    Args:
        ir: The intermediate representation of the circuit.
    Returns:
        The intermediate representation of the routed circuit (including the additional SWAP gates).
    """
    graph_data = {int(start_node): end_nodes for start_node, end_nodes in self.connectivity.items()}
    graph = nx.Graph(graph_data)
    statement_index = 0
    while statement_index < len(ir.statements):
        statement = ir.statements[statement_index]
        if isinstance(statement, Gate) and len(statement.get_qubit_operands()) == 2:
            q0, q1 = statement.get_qubit_operands()
            if not graph.has_edge(q0.index, q1.index):
                try:
                    shortest_path = nx.shortest_path(graph, source=q0.index, target=q1.index)
                    # -2 because we skip inserting a swap for the last edge in the path:
                    # len(path) - 1 edges in total
                    num_swaps_inserted = len(shortest_path) - 2
                    self._insert_and_propagate_swaps(ir, statement_index, shortest_path)
                    statement_index += num_swaps_inserted
                except nx.NetworkXNoPath as e:
                    msg = f"No routing path available between qubit {q0.index} and qubit {q1.index}"
                    raise NoRoutingPathError(msg) from e
        statement_index += 1
    return ir