Qubit Routing and Connectivity

Decomposition assumes any two qubits can interact. Real hardware breaks that assumption: a device's coupling map lists which physical qubit pairs support a two-qubit gate, and it is almost never all-to-all. A superconducting chip might be a grid or a heavy-hex lattice; an early line is just a chain. When a program calls a two-qubit gate on a non-adjacent pair, the transpiler must route the qubits until they sit on a connected edge.

The routing problem

Routing has two intertwined parts:

• Placement (initial mapping): assign each logical qubit to a physical qubit, trying to put frequently-interacting logical qubits on coupled physical ones.
• Movement (routing proper): when a required interaction is between non-adjacent qubits, insert SWAP gates to slide the logical states along the coupling graph until they meet.

Both are computationally hard in general — optimal routing is NP-hard — so transpilers use heuristics such as SABRE that look ahead a few gates and greedily choose swaps that reduce total routing distance.

SWAP as transport

A SWAP exchanges the full states of two wires, so it physically relocates a logical qubit by one edge. To make qubits $a$ and $b$ interact when they are distance $d$ apart on the coupling graph, you swap one of them step by step along a shortest path — $d-1$ swaps to make them adjacent, the target gate, then optionally swaps back to restore the layout.

The cost of limited connectivity

Connectivity directly inflates circuit depth and error. A circuit that is shallow on an idealized all-to-all machine can balloon once routed onto a sparse graph: an algorithm needing many long-range interactions on a line accumulates swaps quadratically in the number of qubits. This is why connectivity is a headline spec for quantum processors, and why some architectures (trapped ions with all-to-all coupling) trade other costs for routing-free execution.

Try it

The device is a line $0\!-\!1\!-\!2$ with no direct $0\!-\!2$ link. Realize the forbidden $\mathrm{CX}(0,2)$ by swapping qubit through the middle, applying an allowed CNOT, and swapping back. The grader checks the full three-qubit unitary, so the routed circuit must equal $\mathrm{CX}(0,2)$ exactly.

Sign in on the full site to ask questions and join the discussion.