SabreSwap

class qiskit.transpiler.passes.SabreSwap(*args, **kwargs)

Basen: TransformationPass

Abbildung der Eingangsschaltung auf eine Backend-Topologie durch Einfügen von SWAPs.

Implementierung der SWAP-basierten heuristischen Suche aus dem SABRE-Qubit-Mapping Paper [2] (Algorithmus 1) mit den Änderungen aus dem LightSABRE Paper [1]. Die Heuristik zielt darauf ab, die Anzahl der eingefügten verlustbehafteten SWAPs und die Tiefe der Schaltung zu minimieren.

Dieser Algorithmus geht von einer anfänglichen Anordnung von virtuellen Qubits auf physischen Qubits aus und iteriert über das Schaltkreis-DAG, bis alle Gatter erschöpft sind, wobei er unterwegs SWAPs einfügt. Es werden nur 2-Qubit-Gatter betrachtet, da nur diese für das Abbildungsproblem von Bedeutung sind (es wird angenommen, dass 3+-Qubit-Gatter bereits zerlegt sind).

Bei jeder Iteration wird zunächst geprüft, ob es auf der Website front_layer Gatter gibt, die direkt angewendet werden können. Wenn dies der Fall ist, werden sie angewendet und von front_layer entfernt, und die Schicht wird, wenn möglich, mit neuen Toren aufgefüllt. Andernfalls wird es versuchen, nach SWAPs zu suchen, die SWAPs einzufügen und die Zuordnung zu aktualisieren.

Die Suche nach SWAPs ist in dem Sinne eingeschränkt, dass wir nur physikalische Qubits in der Nachbarschaft der an front_layer beteiligten Qubits betrachten. Diese führen zu einer swap_candidate_list , die nach einer heuristischen Kostenfunktion bewertet wird. Der beste SWAP wird implementiert und current_layout aktualisiert.

Dieser Transpiler-Durchlauf erweitert den SABRE-Algorithmus dahingehend, dass er mehrere Durchläufe des Algorithmus mit unterschiedlichen Startwerten durchführt. Aus den Zufallsversuchen wird die beste Ausgabe ausgewählt, die durch den Versuch mit der geringsten Anzahl an eingefügten SWAPs ermittelt wurde.

Quellenangaben:

[1] Henry Zou und Matthew Treinish und Kevin Hartman und Alexander Ivrii und Jake Lishman. “LightSABRE: Ein leichtgewichtiger und verbesserter SABRE-Algorithmus" arXiv:2409.08368 [2] Li, Gushu, Yufei Ding, und Yuan Xie. "Tackling the qubit mapping problem for NISQ-era quantum devices" ASPLOS 2019. arXiv:1809.02573

SabreSwap initialisierung.

Parameter

• coupling_map (Union[CouplingMap, Target]) – CouplingMap des Ziel-Backends.
• heuristic (str) – Die Art der Heuristik, die bei der Entscheidung über die beste Swap-Strategie verwendet werden soll ("basic" oder "lookahead" oder "decay").
• seed (int) – zufallsgenerator, der für den Tie-Break zwischen den Swap-Kandidaten verwendet wird.
• fake_run (bool) – wenn true, wird nur so getan, als ob ein Routing stattfindet, d.h. es wird kein Swap hinzugefügt.
• trials (int) – Die Anzahl der Saatgutversuche, mit denen Sabre durchgeführt wird. Diese werden parallel ausgeführt (es sei denn, die PassManager läuft bereits parallel). Wenn nicht angegeben, wird die Anzahl der physischen CPUs auf dem lokalen System als Standardwert verwendet. Um reproduzierbare Ergebnisse zu erzielen, wird empfohlen, diesen Wert explizit festzulegen, da die Ausgabe für eine bestimmte Anzahl von Versuchen deterministisch ist.

Erhöht

TranspilerError – Wenn die angegebene Heuristik ungültig ist.

Weitere Informationen:

Der Suchraum möglicher SWAPs auf physischen Qubits wird erkundet, indem dem Layout, das sich aus jedem SWAP ergeben würde, eine Punktzahl zugewiesen wird. Die Güte eines Layouts wird danach beurteilt, inwieweit es die verbleibenden virtuellen Gatter, die angewendet werden müssen, realisierbar macht. Es werden einige heuristische Kostenfunktionen unterstützt

• basis":

Die Summe der Entfernungen für die entsprechenden physikalischen Qubits der wechselwirkenden virtuellen Qubits in der vorderen Schicht.

$$H_{basic} = \sum_{gate \in F} D[\pi(gate.q_1)][\pi(gate.q2)]$$

• vorausschau":

Dies ist die Summe zweier Kosten: Die erste entspricht den Grundkosten. An zweiter Stelle stehen die Grundkosten, die nun jedoch auch für den erweiterten Satz berechnet werden (d. h. $|E|$ Anzahl der nachfolgenden Nachfolger der Gatter in der vorderen Schicht F). Dies wird mit einem Faktor EXTENDED_SET_WEIGHT (W) gewichtet, um zu verdeutlichen, dass nachfolgende Gatter weniger wichtig sind als die vordere Ebene.

$$H_{decay}=\frac{1}{\left|{F}\right|}\sum_{gate \in F} D[\pi(gate.q_1)][\pi(gate.q2)] + W*\frac{1}{\left|{E}\right|} \sum_{gate \in E} D[\pi(gate.q_1)][\pi(gate.q2)]$$

• 'Verfall':

Dies ist dasselbe wie "Lookahead", aber die gesamten Kosten werden mit einem Verfallsfaktor multipliziert. Dies erhöht die Kosten, wenn der SWAP, mit dem das Versuchslayout erstellt wurde, erst kürzlich verwendet wurde (d. h. es bestraft die Zunahme der Tiefe).

$$H_{decay} = max(decay(SWAP.q_1), decay(SWAP.q_2)) { \frac{1}{\left|{F}\right|} \sum_{gate \in F} D[\pi(gate.q_1)][\pi(gate.q2)]\\ + W *\frac{1}{\left|{E}\right|} \sum_{gate \in E} D[\pi(gate.q_1)][\pi(gate.q2)] }$$

Attribute

coupling_map

dist_matrix

is_analysis_pass

is_transformation_pass

Methoden

execute

name

run

update_status