Runtime Comparison

[csookim]

Introduction

• Test: 100 random 50-CZ gate on 20 qubits.
• Qibo SABRE is 10x slower than Qiskit Python SABRE.

# output
qibo Trivial + SABRE   avg: 0.40797 std: 0.09014
qiskit Trivial + SABRE avg: 0.04401 std: 0.00765

• Updated some logics and improved the performance.

Implementation

1. Qubit Mapping

Previous Approach

• Used three mapping data structures.

self._graph_qubits_names = [int(key[1:]) for key in self.initial_layout.keys()]
self._circuit_logical = list(range(len(self.initial_layout)))
self._physical_logical = list(self.initial_layout.values())

• self._circuit_logical: Represents the virtual circuit layout starting from [0, 1, 2, ... ].
• self._physical_logical: Represents the logical qubit numbers, where _physical_logical[i] is mapped to the physical qubit i.
• _graph_qubits_names: Stores the physical qubit name for physical qubit i.

Problem

• Two data structures are used to handle only physical to logical (p2l) mapping.
• The values of self._physical_logical are not changed within the code.
• There is no direct logical to physical (l2p) mapping.
• The current code performs l2p mapping using list.index(i), which increases runtime due to list iteration every time.

Updated Approach

• Combine circuit_logical and physical_logical into a single structure _p2l.
• Create _l2p to efficiently handle l2p mapping.
• Save the qubit names of the ith physical qubit as _p_qubit_names.

self._p_qubit_names = list(self.initial_layout.keys())
self._p2l = list(self.initial_layout.values())
self._l2p = [0] * len(self._p2l)
for i, l in enumerate(self._p2l):
    self._l2p[l] = i

• This bidirectional mapping enables both l2p and p2l conversion in $O(1)$.

Example

let
initial_layout = {"q0": 3, "q1":1, "q2":0, "q3":2}

then
_p2l = [3, 1, 0, 2]    # physical qubit number i matches logical qubit number _p2l[i]
_l2p = [2, 1, 3, 0]    # logical qubit number i matches physical qubit number _l2p[i] 
_p_qubit_names = ["q0", "q1", "q2", "q3"]  # physical qubit number i has name _p_qubit_names[i]

2. Temporary Circuit

Previous Approach

• When computing the cost of a candidate swap, the current code creates a temporary CircuitMap which includes all the information of the circuit.

temporary_circuit = CircuitMap(
            initial_layout=self.circuit.initial_layout,
            circuit=Circuit(len(self.circuit.initial_layout)),
            blocks=self.circuit.circuit_blocks,
        )

Problem

• Creating a temporary CircuitMap involves unnecessary operations like block decomposition, circuit object creation, and gate copying, which are not required for calculating the cost of a candidate swap.

Updated Approach

• Introduced a _temporary flag.

        self._temporary = temp
        if self._temporary:     # if temporary circuit, no need to store the blocks
            return

        ...
        ### add the real SWAP gate, not a temporary circuit
        if not self._temporary:
            self._routed_blocks.add_block(
                Block(qubits=physical_swap, gates=[gates.SWAP(*physical_swap)])
            )
            self._swaps += 1

• For temporary CircuitMap instances used only for calculating swap costs, return immediately from init() after initializing the necessary data structures.
• For these temporary CircuitMap instances, prevent gate additions or removals in the update() method.

3. Qubits of a Block in the front_layer

Previous Approach

• In the front_layer, only gate (block) numbers are stored.

def _get_dag_layer(self, n_layer):
        """Return the :math:`n`-topological layer of the dag."""
        # node[0] is the gate number
        return [node[0] for node in self._dag.nodes(data="layer") if node[1] == n_layer]

Problem

• To find the qubit numbers associated with a gate, the code must iterate through the list of gates using search_by_index(block), which increases runtime.

Updated Approach

• Store both the gate number and the qubits on which the gates are acting in the front_layer.
• This allows for retrieving the qubits in $O(1)$ time.

### additionally save the qubit pairs that the gates are acting on
    for i in range(len(gates_qubits_pairs)):
        dag.nodes[i]["qubits"] = gates_qubits_pairs[i]

4. Additional

• Use shallow copy when copying an integer list.

Evaluation

• Test: 100 random 50-CZ gate on 20 qubits.
• Qibo SABRE becomes 6x faster.
• Qibo SABRE is 1.5x slower than Qiskit Python SABRE

qibo Trivial + SABRE   avg: 0.06699 std: 0.0163
qiskit Trivial + SABRE avg: 0.04346 std: 0.00588