Abstract
We introduce a novel transpiler for the placement and routing of quantum circuits on arbitrary target hardware architectures. We use finite-horizon, and optionally discounted, reward functions to heuristically find a suitable placement and routing policy. We employ a finite lookahead to refine the reward functions when breaking a tie between multiple policies. We benchmark our transpiler against multiple alternative solutions and on various test sets of quantum algorithms to demonstrate the benefits of our approach.
Introduction: The Challenge of Quantum Transpilation
Quantum algorithms are typically designed for "logical" qubits that are assumed to be fully connected. However, real-world quantum hardware, such as superconducting processors, features "physical" qubits arranged in specific topologies where only adjacent qubits can interact directly. To execute a logical circuit on such hardware, a transpiler must solve two primary problems: placement (mapping logical qubits to physical ones) and routing (inserting SWAP gates to move qubits into interacting range).
Because every SWAP gate introduces noise and increases the overall circuit depth, minimizing their count is critical for the success of Near-Intermediate Scale Quantum (NISQ) devices. This optimization problem is known to be NP-hard, forcing existing tools to rely on "greedy" heuristics that often fail to account for the long-term consequences of immediate routing decisions.
Methodology: The Nuwa Framework
Nuwa addresses the limitations of greedy transpilation by finding a middle ground between local heuristics and computationally expensive global optimization. Its core innovations include:
Finite-Horizon Heuristics and Discounted Rewards
Instead of evaluating only the immediate next gate, Nuwa considers a "horizon" ($\lambda$) of future gates. It calculates placement and edge scores based on how a specific move facilitates upcoming operations. Borrowing from reinforcement learning, Nuwa applies a discount factor ($\delta$) to these rewards. This allows the algorithm to prioritize immediate gates while remaining "aware" of future constraints, effectively avoiding local optima that a purely greedy approach might fall into.
Commutation-Aware Layering
Nuwa enhances routing flexibility by grouping gates into "coarse layers." By identifying gates that commute—meaning their order can be swapped without changing the circuit's output—Nuwa can reorder operations to find more efficient routing paths.
Lookahead Tie-Breaking
In highly structured circuits, multiple routing moves often appear equally beneficial to a simple heuristic. Nuwa employs a deeper lookahead search ($D$) specifically to break these ties, selecting the path that leads to the most advantageous placement state several steps into the future.
Experimental Evaluation
The researchers benchmarked Nuwa against industry-standard competitors, including SABRE (Qiskit), tket (Quantinuum), and arct. The evaluation spanned algorithm-specific circuits (Quantum Signal Processing, Quantum Fourier Transform), standard benchmark sets (e.g., rd84, sym6), and random circuits. These were tested on various topologies, including the 20-qubit IBM Q20 Tokyo graph and generic grid layouts.
Key Results
Nuwa demonstrated significant improvements in reducing SWAP gate overhead across all test categories:
- Algorithm-Specific Performance: For QSP circuits, Nuwa used 9.0% fewer SWAPs than
tketand 51.8% fewer thanarct. For QFT circuits, it showed a 22.4% improvement overtket. - General Benchmarks: In a head-to-head comparison on 21 standard circuits with commutation rules enabled, Nuwa achieved the lowest SWAP count in 20 out of 21 cases.
- Average Scaling: Without commutation rules, Nuwa averaged ~34% fewer SWAPs than
tketand ~66% fewer thanSABRE.
Conclusion and Future Directions
Nuwa represents a significant step forward in quantum circuit transpilation, proving that a finite-horizon lookahead can substantially outperform greedy methods. While the current implementation is computationally more intensive than simpler tools, it scales well for NISQ-era circuits. Future work will focus on optimizing for circuit depth and hardware-specific noise models, as well as integrating Nuwa with more advanced initial placement techniques to further minimize error rates in quantum execution.
Summary updated