# This code is part of Qiskit. # # (C) Copyright IBM 2023. # # This code is licensed under the Apache License, Version 2.0. You may # obtain a copy of this license in the LICENSE.txt file in the root directory # of this source tree or at http://www.apache.org/licenses/LICENSE-2.0. # # Any modifications or derivative works of this code must retain this # copyright notice, and modified files need to carry a notice indicating # that they have been altered from the originals. """Creating Sabre starting layouts.""" import itertools from qiskit.transpiler.basepasses import AnalysisPass from qiskit.transpiler.coupling import CouplingMap from qiskit.transpiler.exceptions import TranspilerError from qiskit.transpiler.passes.layout.vf2_layout import VF2Layout from qiskit.transpiler.target import Target from qiskit._accelerate.error_map import ErrorMap class SabrePreLayout(AnalysisPass): """Choose a starting layout to use for additional Sabre layout trials. Property Set Values Written --------------------------- ``sabre_starting_layouts`` (``list[Layout]``) An optional list of :class:`~.Layout` objects to use for additional Sabre layout trials. **References:** [1] Henry Zou and Matthew Treinish and Kevin Hartman and Alexander Ivrii and Jake Lishman. "LightSABRE: A Lightweight and Enhanced SABRE Algorithm" `arXiv:2409.08368 `__ """ def __init__( self, coupling_map, max_distance=2, error_rate=0.1, max_trials_vf2=100, call_limit_vf2=None, improve_layout=True, ): """SabrePreLayout initializer. The pass works by augmenting the coupling map with more and more "extra" edges until VF2 succeeds to find a perfect graph isomorphism. More precisely, the augmented coupling map contains edges between nodes that are within a given distance ``d`` in the original coupling map, and the value of ``d`` is increased until an isomorphism is found. Intuitively, a better layout involves fewer extra edges. The pass also optionally minimizes the number of extra edges involved in the layout until a local minimum is found. This involves removing extra edges and running VF2 to see if an isomorphism still exists. Args: coupling_map (Union[CouplingMap, Target]): directed graph representing the original coupling map or a target modelling the backend (including its connectivity). max_distance (int): the maximum distance to consider for augmented coupling maps. error_rate (float): the error rate to assign to the "extra" edges. A non-zero error rate prioritizes VF2 to choose original edges over extra edges. max_trials_vf2 (int): specifies the maximum number of VF2 trials. A larger number allows VF2 to explore more layouts, eventually choosing the one with the smallest error rate. call_limit_vf2 (int): limits each call to VF2 by bounding the number of VF2 state visits. improve_layout (bool): whether to improve the layout by minimizing the number of extra edges involved. This might be time-consuming as this requires additional VF2 calls. Raises: TranspilerError: At runtime, if neither ``coupling_map`` or ``target`` are provided. """ self.max_distance = max_distance self.error_rate = error_rate self.max_trials_vf2 = max_trials_vf2 self.call_limit_vf2 = call_limit_vf2 self.improve_layout = improve_layout if isinstance(coupling_map, Target): self.target = coupling_map self.coupling_map = self.target.build_coupling_map() else: self.target = None self.coupling_map = coupling_map super().__init__() def run(self, dag): """Run the SabrePreLayout pass on `dag`. The discovered starting layout is written to the property set value ``sabre_starting_layouts``. Args: dag (DAGCircuit): DAG to create starting layout for. """ if self.coupling_map is None: raise TranspilerError( "SabrePreLayout requires coupling_map to be used with either" "CouplingMap or a Target." ) starting_layout = None cur_distance = 1 while cur_distance <= self.max_distance: augmented_map, augmented_error_map = self._add_extra_edges(cur_distance) pass_ = VF2Layout( augmented_map, seed=-1, max_trials=self.max_trials_vf2, call_limit=self.call_limit_vf2, ) pass_.property_set["vf2_avg_error_map"] = augmented_error_map pass_.run(dag) if "layout" in pass_.property_set: starting_layout = pass_.property_set["layout"] break cur_distance += 1 if cur_distance > 1 and starting_layout is not None: # optionally improve starting layout if self.improve_layout: starting_layout = self._minimize_extra_edges(dag, starting_layout) # write discovered layout into the property set if "sabre_starting_layouts" not in self.property_set: self.property_set["sabre_starting_layouts"] = [starting_layout] else: self.property_set["sabre_starting_layouts"].append(starting_layout) def _add_extra_edges(self, distance): """Augments the coupling map with extra edges that connect nodes ``distance`` apart in the original graph. The extra edges are assigned errors allowing VF2 to prioritize real edges over extra edges. """ nq = len(self.coupling_map.graph) augmented_coupling_map = CouplingMap() augmented_coupling_map.graph = self.coupling_map.graph.copy() augmented_error_map = ErrorMap(nq) for x, y in itertools.combinations(self.coupling_map.graph.node_indices(), 2): d = self.coupling_map.distance(x, y) if 1 < d <= distance: error_rate = 1 - ((1 - self.error_rate) ** d) augmented_coupling_map.add_edge(x, y) augmented_error_map.add_error((x, y), error_rate) augmented_coupling_map.add_edge(y, x) augmented_error_map.add_error((y, x), error_rate) return augmented_coupling_map, augmented_error_map def _get_extra_edges_used(self, dag, layout): """Returns the set of extra edges involved in the layout.""" extra_edges_used = set() virtual_bits = layout.get_virtual_bits() for node in dag.two_qubit_ops(): p0 = virtual_bits[node.qargs[0]] p1 = virtual_bits[node.qargs[1]] if self.coupling_map.distance(p0, p1) > 1: extra_edge = (p0, p1) if p0 < p1 else (p1, p0) extra_edges_used.add(extra_edge) return extra_edges_used def _find_layout(self, dag, edges): """Checks if there is a layout for a given set of edges.""" cm = CouplingMap(edges) pass_ = VF2Layout(cm, seed=0, max_trials=1, call_limit=self.call_limit_vf2) pass_.run(dag) return pass_.property_set.get("layout", None) def _minimize_extra_edges(self, dag, starting_layout): """Minimizes the set of extra edges involved in the layout. This iteratively removes extra edges from the coupling map and uses VF2 to check if a layout still exists. This is reasonably efficiently as it only looks for a local minimum. """ # compute the set of edges in the original coupling map real_edges = [] for x, y in itertools.combinations(self.coupling_map.graph.node_indices(), 2): d = self.coupling_map.distance(x, y) if d == 1: real_edges.append((x, y)) best_layout = starting_layout # keeps the set of "necessary" extra edges: without a necessary edge # a layout no longer exists extra_edges_necessary = [] extra_edges_unprocessed_set = self._get_extra_edges_used(dag, starting_layout) while extra_edges_unprocessed_set: # choose some unprocessed edge edge_chosen = next(iter(extra_edges_unprocessed_set)) extra_edges_unprocessed_set.remove(edge_chosen) # check if a layout still exists without this edge layout = self._find_layout( dag, real_edges + extra_edges_necessary + list(extra_edges_unprocessed_set) ) if layout is None: # without this edge the layout either does not exist or is too hard to find extra_edges_necessary.append(edge_chosen) else: # this edge is not necessary, furthermore we can trim the set of edges to examine based # in the edges involved in the layout. extra_edges_unprocessed_set = self._get_extra_edges_used(dag, layout).difference( set(extra_edges_necessary) ) best_layout = layout return best_layout