SWAP Networks: Routing on Linear Topology

SWAP Networks: Routing on Linear Topology

Real superconducting hardware has limited qubit connectivity. When your algorithm needs a gate between non-adjacent qubits, the compiler inserts SWAP gates to move the qubit state to an adjacent position. This is called qubit routing or qubit mapping and is one of the largest sources of overhead in NISQ circuits.

Why Connectivity Limits Matter

Any algorithm requiring a gate between q0 and q3 must route: SWAP q1/q2 (or q2/q3) to bring the target qubits adjacent. Each SWAP costs 3 CNOTs.

Building GHZ on Linear Topology

The 4-qubit GHZ state $(|0000⟩+|1111⟩)/\sqrt{2}$ can be built efficiently on linear topology:

This cascades the entanglement along the chain, each CX using only adjacent qubits. Total: 1 H + 3 CX = 4 gates, depth 4.

The Non-Adjacent Problem

Now try to create a controlled interaction between q0 and q3 (distance 3 on the chain). You need to route q3 to be adjacent to q0 via SWAPs:

Method: SWAP q3 to position q2 (3 CNOTs), then SWAP to q1 (3 CNOTs), now q3's state is at position q1 and can interact with q0. Total: 2 SWAPs x 3 CNOTs = 6 extra CNOTs before the actual gate.

For an algorithm with many such long-range interactions, SWAP overhead can 3-5x the circuit depth.

Routing Heuristics