Quantum routing with fast reversals

Understand

We present methods for implementing arbitrary permutations of qubits under interaction constraints.

• Our protocols make use of previous methods for rapidly reversing the order of qubits along a path.
• Given nearest-neighbor interactions on a path of length $n$, we show that there exists a constant $\epsilon \approx 0.034$ such that the quantum routing time is at most $(1-\epsilon)n$, whereas any swap-based protocol needs at least time $n-1$.
• This represents the first known quantum advantage over swap-based routing methods and also gives improved quantum routing times for realistic architectures such as grids.