AbstractCurrent quantum compilers inject lossy SWAP gates to satisfy heavy-hex connectivity, incurring15-30% fidelity penalties per routed operation. We present a hardware-compliant routing paradigmbased on the Z6 topological bus that achieves zero SWAP overhead by constraining entanglementto nearest-neighbor CX chains. Combined with parity compression into a single terminal anchorqubit and thermodynamic dark-memory mapping, the framework was executed across 57,344shots on IBM Heron r2 with 95.2% average GHZ fidelity and 0 compiler-inserted SWAPs.
AbstractCurrent quantum compilers inject lossy SWAP gates to satisfy heavy-hex connectivity, incurring15-30% fidelity penalties per routed operation. We present a hardware-compliant routing paradigmbased on the Z6 topological bus that achieves zero SWAP overhead by constraining entanglementto nearest-neighbor CX chains. Combined with parity compression into a single terminal anchorqubit and thermodynamic dark-memory mapping, the framework was executed across 57,344shots on IBM Heron r2 with 95.2% average GHZ fidelity and 0 compiler-inserted SWAPs.
Despite rapid advances in quantum computing technologies, the qubit connectivity limitation remains to be a critical challenge. Both near-term NISQ quantum computers and relatively long-term scalable quantum architectures do not offer full connectivity. As a result, quantum circuits may not be directly executed on quantum hardware, and a quantum compiler needs to perform qubit routing to make the circuit compatible with the device layout. During the qubit routing step, the compiler inserts SWAP gates and performs circuit transformations. Given the connectivity topology of the target hardware, there are typically multiple qubit routing candidates. The state-of-the-art compilers use a cost function to evaluate the number of SWAP gates for different routes and then select the one with the minimum number of SWAP gates. After qubit routing, the quantum compiler performs gate optimizations upon the circuit with the newly inserted SWAP gates.In this paper, we observe that the aforementioned qubit routing is not optimal, and qubit routing should not be independent on subsequent gate optimizations. We find that with the consideration of gate optimizations, not all of the SWAP gates have the same basis-gate cost. These insights lead to the development of our qubit routing algorithm, NASSC (Not All Swaps have the Same Cost). NASSC is the first algorithm that considers the subsequent optimizations during the routing step. Our optimization-aware qubit routing leads to better routing decisions and benefits subsequent optimizations. We also propose a new optimization-aware decomposition for the inserted SWAP gates. Our experiments show that the routing overhead compiled with our routing algorithm is reduced by up to 69.30% (21.30% on average) in the number of CNOT gates and up to 43.50% (7.61% on average) in the circuit depth compared with the state-of-the-art scheme, SABRE.
Mapping quantum programs to restricted physical chips requires SWAP operations, incurring depth and error penalties. In symmetric programs, this routing overhead breaks theoretical symmetry because identical logical roles experience unequal shuffling. While often attributed to hardware topology alone, we show this is a two-level phenomenon. A qubit patch's shape dictates if it can host a balanced assignment. When balance is possible, the actual imbalance is set by the logical-to-physical assignment, meaning a balanced assignment can distribute routing costs perfectly evenly at no extra depth. Through exhaustive search on a 57-qubit "heavy-hex" lattice, we prove these topological constraints. For a four-part ring, 108 of 124 connected patches admit a cost-free balanced assignment, with the 16 exceptions being star-shaped. For a six-part ring, cost-free balance is impossible on compact patches. For a fully connected four-part symmetry, balance is structurally impossible at any depth. Simulations using realistic error rates show that, relative to the worst-case concentrated assignment, balanced assignments reduce symmetry-breaking by 92.7% (95% CI [+89.8%, +95.3%]) for the raw metric and 87.0% (95% CI [+79.6%, +94.1%]) for the decoherence-corrected measure (p = 2.45 x 10^-32). Substrate error heterogeneity accounts for at most 10.8% of this effect. Notably, switching to the compiler's highest generic optimization level did not yield a statistically significant change in routing imbalance, highlighting the need for targeted symmetry-aware passes. When patch geometry permits, routing imbalance is a compiler choice rather than a hardware limitation. Thus, symmetry-aware assignment should be a primary objective for compiler optimization and chip design.
Quantum circuit routing is a key step in compiling programs for noisy intermediate-scale quantum processors, particularly superconducting devices whose sparse fixed coupling makes routing a central compilation cost. Routes that appear efficient by standard overhead metrics such as SWAP count, routed two-qubit count, and depth can still lose fidelity when they pass through poorly calibrated couplers. We study a calibration-aware graph reinforcement-learning router that uses same-day calibration data from superconducting IBM Heron r2 processors to choose hardware-edge SWAPs. We train the policy with proximal policy optimization and evaluate it with exact simulated fidelity across nine Munich Quantum Toolkit (MQT) Bench circuits and three calibration snapshots. Across these evaluations, pooled mean exact fidelity is 0.727, compared with 0.440 for SWAP-based bidirectional heuristic search (SABRE)-best20 and 0.481 for target-aware SABRE. We observe that fidelity gains come with higher routed two-qubit counts and are concentrated in 5 qubit and 8 qubit circuit families; under the fixed tree action graph, all 10 qubit families favor SABRE-best20. Overall, our results show that calibration-aware learned routing can improve fidelity beyond gate-count-driven compilation, by roughly 0.25 to 0.29 in absolute mean fidelity over the SABRE-family baselines.
Limited connectivity makes nonlocal quantum gates expensive on near-neighbor hardware, where compilation typically relies on SWAP transport, inheriting both depth overhead and path congestion. We present a swap-free routing framework in which higher levels of a qudit act as orthogonal spectral buses that transport control information without moving the computational state. We show that exact congestion relief in nearest-neighbor architectures requires local Hilbert-space expansion. In this model, a nonlocal operation over a path of length L requires 2L+1 logical routing primitives, compared to the 3L baseline. Overlapping routes remain distinguishable through bus labels encoded in the same physical qudits. This routing algebra extends to Boolean fan-in at a common target: multiple controls arriving on distinct buses trigger a local unitary based on an arbitrary Boolean function of bus digits, yielding multi-control operations of depth 2L+Dg+O(1) for fan-in size K and target-synthesis cost Dg. We prove decodability, reversibility, and correctness for CNOT and Boolean fan-in, along with a state-count lower bound d≥2K+1 for exact overlap routing. Cirq simulations confirm single-control correctness and zero crosstalk. Compiler-level benchmarks on QFT, QAOA, and mirror-interaction circuits verify the predicted congestion law and transport reduction. Noisy QuTiP simulations show that the architectural advantage depends on higher-level coherence and speed. These results identify spectral qudit routing as a congestion-relief architecture that separates nonlocal control delivery from local target-side aggregation, providing a minimal mechanism for overcoming qubit routing limitations.
Quantum computers with a limited qubit connectivity require inserting SWAP gates for qubit routing, which increases gate execution errors and the impact of environmental noise due to an overhead in circuit depth. In this work, we benchmark various routing techniques considering random quantum circuits on one-dimensional and square lattice connectivities, employing both analytical and numerical methods. We introduce circuit fidelity as a comprehensive metric that captures the effects of SWAP and circuit depth overheads. Leveraging a novel approach based on the SABRE algorithm, we achieve up to 84% higher average circuit fidelity for large devices within the NISQ range, compared to previously existing methods. Additionally, our results highlight that the optimal routing choice critically depends on the qubit count and the hardware characteristics, including gate fidelities and coherence times.
Qubit mapping/routing is a critical stage in compilation for both near-term and fault-tolerant quantum computers, yet existing scalable methods typically impose several times the routing overhead in terms of circuit depth or duration. This inefficiency stems from a fundamental disconnect: compilers rely on an abstract routing model (e.g., three-CX-unrolled SWAP insertion) that completely ignores the idiosyncrasies of native gates supported by physical devices.
Recent hardware breakthroughs have enabled high-precision implementations of diverse instruction set architectures (ISAs) beyond standard CX-based gates. Advanced ISAs involving gates such as iSWAP and ZZ(θ) gates offer superior circuit synthesis capabilities and can be realized with higher fidelities. However, systematic compiler optimization strategies tailored to these advanced ISAs are lacking.
To address this, we propose Canopus, a unified qubit mapping/routing framework applicable to diverse quantum ISAs. Built upon the canonical representation of two-qubit gates, Canopus centers on qubit routing to perform deep co-optimization in an ISA-aware approach. Canopus leverages the two-qubit canonical representation and the monodromy polytope theory to model the synthesis cost for more intelligent SWAP insertion during qubit routing. We also formalize the commutation relations between two-qubit gates through the canonical form, providing a generalized approach to commutativity-based optimization. Experiments show that Canopus consistently reduces routing overhead by 15%-35% compared to state-of-the-art methods across various backend ISAs and device topologies. More broadly, this work establishes a coherent method for co-exploration of program patterns, quantum ISAs, and hardware topologies, yielding concrete guidelines for hardware-software co-design.