  We study the problem of implementing arbitrary permutations of qubits under
interaction constraints in quantum systems that allow for arbitrarily fast
local operations and classical communication (LOCC). In particular, we show
examples of speedups over swap-based and more general unitary routing methods
by distributing entanglement and using LOCC to perform quantum teleportation.
We further describe an example of an interaction graph for which teleportation
gives a logarithmic speedup in the worst-case routing time over swap-based
routing. We also study limits on the speedup afforded by quantum teleportation
- showing an $O(\sqrt{N \log N})$ upper bound on the separation in routing time
for any interaction graph - and give tighter bounds for some common classes of
graphs.
