Qubit Routing
Qubit routing maps a circuit's logical qubits onto hardware with limited connectivity, inserting SWAP gates so every two-qubit gate acts on physically adjacent qubits.
Circuits meet connectivity
A written circuit assumes any two qubits can interact. Real devices do not: superconducting chips and other hardware connect each qubit only to a few neighbors. Qubit routing is the compilation step that reconciles the two -- placing logical qubits on physical ones and moving them so that each two-qubit gate lands on connected hardware.
The role of SWAP
When a gate needs two non-adjacent qubits, the compiler inserts SWAP gates to shuttle their states next to each other. Since a SWAP decomposes into three CNOTs, every inserted SWAP adds depth and error. Routing is the search for a schedule of SWAPs that keeps this overhead small.
Hard problem, real cost
- Optimal routing is NP-hard; compilers use heuristics and look-ahead search.
- Routing overhead can multiply gate count several-fold on sparse topologies.
- On noisy hardware, the added SWAP depth is often the difference between a usable and a useless result.
Better connectivity, smarter routers, and error mitigation all attack the same bottleneck. Routing is a quiet but decisive part of whether a circuit runs well on today's machines.