Swap Network

Cost and decomposition

The Swap network can be decomposed using exactly b(2^n - 1) Controlled-Swap gates, where

• n is the number of control qubits (such that N = 2^n), and
• b is the number of qubits composing each state register |\phi_j\rangle.

The strategy consists of shifting the target register toward the "zero position" (the output register) through a cascade of swaps controlled by the binary representation of the selection index.

• First control qubit: If this bit is active, a swap is performed between the first half of the registers \{0, \dots, N/2 - 1\} and the second half \{N/2, \dots, N-1\}.

• Second control qubit: Performs a swap between the sub-blocks \{0, \dots, N/4 - 1\} and \{N/4, \dots, N/2 - 1\}.

• The j-th control qubit: Swaps the registers in the ranges:

  \{0, \dots, 2^{n-j}-1\} \longleftrightarrow \{2^{n-j}, \dots, 2^{n-j+1}-1\}

This ensures that a register is "bubbled up" to the top, based on its binary index.

 0: ─╭●────╭●────╭●────╭●──────────────────────┤  State
 1: ─│─────│─────│─────│─────╭●────╭●──────────┤  State
 2: ─│─────│─────│─────│─────│─────│─────╭●────┤  State
 3: ─├SWAP─│─────│─────│─────├SWAP─│─────├SWAP─┤  State
 4: ─│─────├SWAP─│─────│─────│─────├SWAP─╰SWAP─┤  State
 5: ─│─────│─────├SWAP─│─────╰SWAP─│───────────┤  State
 6: ─│─────│─────│─────├SWAP───────╰SWAP───────┤  State
 7: ─╰SWAP─│─────│─────│───────────────────────┤  State
 8: ───────╰SWAP─│─────│───────────────────────┤  State
 9: ─────────────╰SWAP─│───────────────────────┤  State
10: ───────────────────╰SWAP───────────────────┤  State