  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. Furthermore,
we show that our algorithm approaches a quantum routing time of $2n/3$ in
expectation for uniformly random permutations, whereas swap-based protocols
require time $n$ asymptotically. Additionally, we consider sparse permutations
that route $k \le n$ qubits and give algorithms with quantum routing time at
most $n/3 + O(k^2)$ on paths and at most $2r/3 + O(k^2)$ on general graphs with
radius $r$.
