Qubit Routing under Hardware Topology Constraints

608 concepts385 papers4 proposals

When designing quantum algorithms, we typically operate under a convenient fiction: the assumption of universal, all-to-all qubit connectivity. In this idealized model, any logical qubit can instantly interact with any other logical qubit via a multi-qubit gate.

The physical reality of quantum processing units (QPUs) is radically different. Due to the material and geometric limits of hardware fabrication, physical qubits are bound to fixed, localized coupling graphs. In superconducting architectures, qubits are often arranged in sparse 2D grids or heavy-hex patterns. In these setups, a two-qubit gate can only execute if its target qubits are immediate physical neighbors.

This discrepancy creates a fundamental compilation challenge: how do we execute an abstract quantum circuit on a hardware topology that cannot natively support its connectivity requirements?

The Cost of Realism: SWAP Gates and Circuit Depth

To perform a gate between two non-adjacent physical qubits, the compiler must dynamically alter the layout of the data. The primary mechanism for doing this is the insertion of SWAP gates. A SWAP gate exchanges the quantum states of two adjacent physical qubits, effectively moving a piece of information one step across the hardware graph. By chaining multiple SWAP gates together, the compiler can route distant quantum states into adjacent positions, execute the desired logical operation, and optionally route them back.

However, this routing comes at a steep price. Physical quantum gates are noisy and slow relative to the fragile coherence times of qubits. Because a single logical SWAP gate is typically decomposed into three physical CNOT gates, inserting routing operations rapidly inflates the circuit's depth and gate count. As Botea et al. and Borujeni et al. demonstrate, this overhead introduces substantial noise and decoherence, which can easily degrade the fidelity of the computation below usable thresholds.

Optimizing this process is exceptionally difficult. A foundational theoretical result from the authors of Algorithmic Theory of Qubit Routing proves that finding the absolute minimum number of SWAP gates required to route a circuit is an NP-hard problem, even when restricted to a simple one-dimensional path architecture. As a result, the field relies heavily on a mix of exact optimization techniques for small scales and scalable heuristics for larger devices.

Layout Synthesis: Mapping and Routing Strategies

The process of translating an abstract circuit to a physical topology is broadly termed layout synthesis, which unifies three interdependent tasks: placement (assigning logical qubits to physical sites), routing (inserting SWAPs to bring interacting qubits together), and scheduling (ordering gates to maximize parallelism).

Exact Optimization

For smaller quantum circuits, compilers prioritize minimizing gate overhead at all costs. To achieve this, exact synthesizers translate the routing problem into mathematical constraints that can be solved using classical optimization engines. For example, Bochen Tan et al. developed frameworks like OLSQ and TB-OLSQ, which encode the hardware topology and gate sequences into Satisfiability Modulo Theories (SMT) formulations. By solving these formulas globally, the compiler guarantees an optimal or near-optimal layout that minimizes circuit depth. However, because the underlying problem is NP-hard, these exact methods become computationally intractable as the number of qubits scales.

Physics-Inspired and Genetic Heuristics

To compile circuits for larger QPUs, researchers turn to heuristic algorithms that trade guaranteed optimality for rapid execution times. One intuitive approach is to model the routing problem as a physical system. In the "Route-Forcing" method proposed by Escofet et al., logical qubits are treated as particles subject to virtual "attraction forces." When two qubits share an upcoming gate in the circuit, an attractive force pulls them closer together across the physical grid, guiding the heuristic to select SWAP paths that naturally minimize future routing bottlenecks.

Other compilers leverage evolutionary strategies. Rasconi et al. introduced a genetic algorithm framework that treats alternative routing paths as chromosomes. By iteratively mutating and combining these paths based on a fitness function (such as total circuit depth), the compiler searches the massive solution space efficiently, avoiding the exponential slowdowns of exact solvers while outperforming naive greedy routing.

Beyond Fixed Grids: Dynamic Topologies

While superconducting chips rely on static physical connections, alternative hardware modalities introduce dynamic topologies where qubits can physically move during execution. Compilers for these systems must optimize mechanical transport alongside logical gates.

Neutral Atom Architectures

Neutral atom quantum computers trap individual atoms using optical tweezers. Instead of using SWAP gates to pass quantum states through an intermediary chain of qubits, these systems can physically move the atoms themselves into interaction range.

This capability enables "zero-SWAP" compilation, but it introduces unique mechanical and geometric constraints. As Ludmir et al. explain in their work on the PARALLAX compiler, moving atoms via Acousto-Optic Deflectors (AODs) requires coordinating rows and columns of traps that often move in tandem. Furthermore, atoms cannot cross paths during execution without causing catastrophic data loss. Compiling for neutral atoms therefore shifts the problem from discrete graph routing to continuous, collision-free geometric motion planning.

Trapped-Ion QCCDs

A similar paradigm exists in Quantum Charge-Coupled Device (QCCD) architectures for trapped ions, where ions are physically shuttled between distinct specialized trap zones (such as processing zones and storage zones). Traditional compilation pipelines treat physical shuttling and logical SWAP operations as entirely separate layers. To eliminate this inefficiency, Zhu et al. developed S-SYNC, a compiler that models the hardware as a unified spatio-temporal graph. By co-optimizing shuttling trajectories and logical gate placements simultaneously, the compiler exploits the natural hardware transport mechanisms to bypass the rigid constraints of static topologies.

Managing Physical Realities: Crosstalk and Spacing

A final, critical dimension of topology-constrained routing is that physical proximity breeds interference. When two independent quantum operations are executed simultaneously on adjacent regions of a chip, parasitic coupling can cause crosstalk, introducing correlated errors that ruin the computation. As noted by Botea et al., scheduling algorithms must balance the desire for high gate parallelism against the physical necessity of isolating active qubits.

To address this at the hardware design and compilation boundary, tools must handle fine-grained physical placement. Junyao Zhang et al. developed the qGDP framework, which introduces a "legalization" phase to chip layout. By intelligently spacing physical components and minimizing the intersections of control lines (resonator crossings), these techniques ensure that the physical topology itself is optimized to suppress crosstalk, providing a cleaner, more reliable graph for routing algorithms to navigate.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 393 papers
  2. Version 1 · 2026-10-04 · 439 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_hardware_topology_constraints_2de4c884,
  title = {hardware topology constraints},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/hardware-topology-constraints/rdr_2de4c884dcf34f478c0286a5b2695402},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 2, frozen text):

@misc{lacuna_hardware_topology_constraints_2de4c884_v2,
  title = {hardware topology constraints},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/hardware-topology-constraints/rdr_2de4c884dcf34f478c0286a5b2695402/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake