SWAP Network

A SWAP network is a sequence of SWAP gates inserted into a quantum circuit to move qubit states between physically non-adjacent locations on a quantum processor. Most quantum hardware has limited connectivity: each physical qubit can interact directly with only a few neighbors. When an algorithm requires a two-qubit gate between qubits that are not physically adjacent, the compiler must insert SWAP gates to bring the relevant quantum states next to each other. The collection of these routing operations forms a SWAP network, and minimizing its size is a central challenge in quantum circuit transpilation.

The SWAP gate

The SWAP gate exchanges the states of two qubits:

$\text{SWAP} = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}$

It maps $|01\rangle \to |10\rangle$ and $|10\rangle \to |01\rangle$, leaving $|00\rangle$ and $|11\rangle$ unchanged. Each SWAP gate decomposes into three CNOT gates:

q0: ──●──X──●──
      │  │  │
q1: ──X──●──X──

This decomposition means every SWAP costs 3 CNOTs, which on most hardware is the dominant source of noise. If a hardware platform uses a different native gate set (e.g., the CZ gate or iSWAP gate), the decomposition changes but the cost remains roughly equivalent: 3 two-qubit native gates per SWAP.

Why SWAP networks are necessary

Consider IBM’s heavy-hex topology, where each qubit connects to at most 3 neighbors. If a circuit requires a CNOT between qubit 0 and qubit 15, and these qubits are separated by 5 edges on the connectivity graph, at least 5 SWAP operations (15 CNOTs) may be needed just to bring the two states adjacent. This routing overhead can dominate the total circuit cost.

Different hardware topologies create different routing challenges:

• Linear chain: Qubits in a line. Worst case: $O(n)$ SWAPs to connect the two ends of an $n$-qubit chain.
• Grid (square lattice): Qubits on a 2D grid. Worst case: $O(\sqrt{n})$ SWAPs for an $n$-qubit grid.
• Heavy-hex (IBM): A modified hexagonal lattice. Moderate connectivity, requiring nontrivial routing.
• All-to-all (trapped ions): Any qubit can interact with any other directly. No SWAPs needed, which is a significant advantage of trapped-ion platforms.

Routing algorithms

The problem of minimizing SWAP insertions is NP-hard in general, so practical transpilers use heuristic algorithms:

• SABRE (SWAP-based Bidirectional heuristic search): The default routing algorithm in Qiskit. It alternates between forward and reverse passes through the circuit, greedily inserting SWAPs to reduce the distance between qubits that need to interact.

• Noise-aware routing: Some transpilers account for the fact that different physical connections have different error rates, routing through higher-fidelity links even if the path is longer in terms of SWAP count.

• Initial layout optimization: Choosing which logical qubit maps to which physical qubit at the start of the circuit can dramatically affect the total SWAP count. Good initial layouts reduce routing overhead.

Impact on circuit depth and fidelity

SWAP insertion has two costs:

1. Depth overhead: Each SWAP adds 3 layers of two-qubit gates to the circuit depth, increasing the total execution time and the window for decoherence.

2. Fidelity overhead: Each additional two-qubit gate introduces errors. If two-qubit gate fidelity is $99.5\%$, five SWAP operations (15 CNOTs) reduce the fidelity of that portion of the circuit to approximately $(0.995)^{15} \approx 92.7\%$.

For NISQ algorithms, SWAP overhead often determines whether a circuit can run successfully. This is why qubit connectivity is such an important hardware specification, and why trapped-ion processors with all-to-all connectivity can sometimes outperform superconducting processors with more qubits but limited connectivity.

Why it matters for learners

SWAP networks bridge the gap between abstract quantum algorithms (where any two qubits can interact freely) and real hardware (where connectivity is constrained). Understanding SWAP routing helps explain why transpilation matters, why hardware topology affects algorithm performance, and why “more qubits” does not automatically mean “more capability.” When evaluating quantum hardware, the connectivity graph is as important as the qubit count or gate fidelity.

See also

• CNOT Gate
• Transpilation
• Circuit Depth
• Native Gate Set