Table of Contents
- Introduction
- What Is Qubit Routing?
- The Need for Compilation in Quantum Computing
- Logical vs Physical Qubit Mapping
- Coupling Constraints in Hardware
- Overview of Routing Algorithms
- SWAP Insertion Strategies
- Routing Cost Metrics
- Compilation Workflow in Qiskit
- Layout Selection Techniques
- SABRE: Swap-Based Adaptive Routing
- Lookahead Routing and Heuristics
- Commutativity and Gate Reordering
- Circuit Rewriting for Optimization
- Hardware-Aware Compilation Tools
- Mapping and Routing in t|ket>
- Compilation for Trapped Ions vs Superconducting Qubits
- Impact of Routing on Fidelity and Execution Time
- Visualization and Debugging of Routing Paths
- Conclusion
1. Introduction
Qubit routing is the process of adapting an ideal quantum circuit to the specific physical constraints of a quantum device, ensuring valid gate execution paths. It’s a crucial step in the compilation process for real hardware.
2. What Is Qubit Routing?
Routing finds a mapping from logical qubits to physical qubits while satisfying coupling constraints, often involving inserting SWAP operations to move qubit states.
3. The Need for Compilation in Quantum Computing
- Logical circuits assume full connectivity
- Physical hardware is constrained
- Compilation ensures valid and optimized execution
4. Logical vs Physical Qubit Mapping
- Logical qubits: defined by algorithm
- Physical qubits: actual device layout
Routing establishes the best mapping between the two.
5. Coupling Constraints in Hardware
Qubits are not fully connected. Only certain pairs can perform two-qubit gates. Devices expose these constraints via a coupling map.
6. Overview of Routing Algorithms
- Exact (search-based): optimal but slow
- Heuristic: scalable and fast
- Examples: SABRE, Greedy, Beam search
7. SWAP Insertion Strategies
When qubits are non-adjacent:
- Insert SWAP gates to move states closer
- Prioritize gates with early deadlines or high weight
8. Routing Cost Metrics
- Circuit depth
- Number of SWAPs
- Fidelity impact
- Total gate count
9. Compilation Workflow in Qiskit
from qiskit import transpile
transpiled = transpile(circuit, backend, optimization_level=3)10. Layout Selection Techniques
- Trivial layout: assign qubits in order
- Dense layout: place connected logical qubits close
- Noise-aware layout: prefer higher-fidelity qubits
11. SABRE: Swap-Based Adaptive Routing
Qiskit’s default heuristic for routing:
- Balances SWAP cost vs lookahead
- Adapts dynamically to gate queue
12. Lookahead Routing and Heuristics
Evaluates future gate needs to plan optimal current SWAPs.
13. Commutativity and Gate Reordering
Reorders gates that commute to expose better parallelism and reduce SWAP overhead.
14. Circuit Rewriting for Optimization
- Gate merging
- Cancellation (e.g., CX followed by CX = I)
- Rebase to native gates
15. Hardware-Aware Compilation Tools
- Qiskit: PassManager, transpiler stages
- t|ket>: RoutingPass, MappingPass
- Q#: ResourceEstimator
16. Mapping and Routing in t|ket>
- Uses advanced cost models and placement strategies
- Provides visual feedback on routing
17. Compilation for Trapped Ions vs Superconducting Qubits
- Trapped ions: all-to-all but slow gates
- Superconducting: fast gates but strict topology
18. Impact of Routing on Fidelity and Execution Time
Poor routing = more SWAPs = more errors
Optimized routing = shorter time and higher success
19. Visualization and Debugging of Routing Paths
Use:
circuit.draw('mpl')To compare pre- and post-routing layouts and gate placement.
20. Conclusion
Qubit routing and compilation bridge the gap between abstract quantum algorithms and real hardware execution. Understanding the routing process helps developers create efficient, hardware-compatible quantum circuits and minimize execution errors.