Exhaustive K-SWAP-sequence search for qubit mapping

Abstract

Quantum computing promises to solve certain problems more efficiently than classical computation. Realizing this potential on noisy, intermediate-scale quantum (NISQ) devices remains challenging. Among other things, hardware connectivity constraints necessitate additional routing operations that degrade circuit fidelity. The qubit mapping problem - assigning logical qubits to physical qubits while minimizing inserted SWAP gates - is thus critical in quantum circuit transpilation. Exact methods scale poorly, and heuristic approaches like the SABRE algorithm, though efficient, rely on local decisions that can miss globally optimal solutions. In this thesis, we propose K-SWAP SABRE that integrates bounded exhaustive search over sequences of up to k SWAPs into the SABRE algorithm. A modified heuristic ensures global progress while maintaining comparability between explored branches. Experiments on benchmark circuits show that increasing k reduces required SWAP gates, especially on highly connected devices, though at the cost of longer runtime. Our results demonstrate that K-SWAP SABRE can improve heuristic qubit mapping quality without sacrificing scalability, offering a practical approach for mapping circuits to near-term and emerging quantum architectures. Quantencomputing bietet das Potenzial, bestimmte Probleme effizienter zu lösen als klassische Computer. Die Umsetzung auf Noisy, Intermediate-scale Quantum (NISQ) Computern ist jedoch herausfordernd. Unter anderem, weil Hardware-Beschränkungen zusätzliche Routing-Operationen erfordern, die die Ergebnisqualität verringern. Das Qubit-Mapping - die Zuordnung logischer zu physischen Qubits bei minimalen SWAP-Gattern - ist daher ein entscheidender Schritt in der Transpilation von Quanten-Schaltungen. Exakte Methoden skalieren schlecht, während heuristische Ansätze wie SABRE effizient, aber lokal begrenzt sind und globale Optimierungen übersehen können. In dieser Arbeit wird K-SWAP SABRE vorgestellt, der begrenzte erschöpfende Suche über Sequenzen von bis zu k SWAP-Gattern in den SABRE Algorithmus integriert. Eine modifizierte Heuristik gewährleistet globalen Fortschritt, während die Vergleichbarkeit der Lösungszweige erhalten bleibt. Experimente auf Benchmark-Schaltungen zeigen, dass längere Sequenzen k die Anzahl benötigter SWAP-Gatter reduzieren können, insbesondere bei Quantencomputern mit hoher Konnektivität, jedoch auf Kosten längerer Laufzeiten. Die Ergebnisse verdeutlichen, dass K-SWAP SABRE die Qualität heuristischer Qubit-Zuordnung verbessern kann, ohne die Skalierbarkeit zu verlieren und einen praktikablen Ansatz für die Transpilation von Quanten-Schaltungen darstellt.