Connectivity and Qubit Routing
Connectivity is which qubits can directly interact; limited connectivity forces extra SWAP operations that add error and depth.
Who can talk to whom
A quantum algorithm assumes it can apply a two-qubit gate to any pair, but hardware rarely allows that. Connectivity describes which physical qubits are directly coupled. Superconducting chips usually offer only nearest-neighbor coupling on a 2D lattice; trapped ions in a chain offer all-to-all; neutral atoms can be physically rearranged to change connectivity.
The routing problem
When an algorithm needs a gate between two qubits that are not directly coupled, the compiler must move their states together using SWAP gates, each of which is typically three two-qubit gates. Choosing an initial placement and a schedule of SWAPs to minimize this overhead is the qubit-routing (or qubit-mapping) problem, which is computationally hard and handled by heuristics in the compiler.
Cost of limited connectivity
- Each SWAP adds error and increases circuit depth
- Deeper circuits accumulate more decoherence
- Poor mapping can multiply the two-qubit gate count several-fold
Approaches
Denser coupling maps (heavy-hex, square, or with tunable couplers) reduce routing but can worsen crosstalk and frequency crowding, so architectures trade connectivity against control complexity. All-to-all modalities avoid routing but face their own scaling limits. Movable qubits, as in neutral-atom arrays and ion shuttling, let the hardware reconfigure connectivity on the fly, a middle path.
Because routing overhead directly reduces the effective size of runnable circuits, connectivity is a first-order design choice, not a detail, and it strongly influences benchmarks like quantum volume that reward all-to-all-friendly hardware.