



01358nas a2200181   4500008004100000245003900041210003900080260001300119520083800132653002700970653003100997100002301028700001901051700002101070700002301091700002501114856003701139       2022                        eng d00aQuantum Routing with Teleportation0 aQuantum Routing with Teleportation  c4/8/20223 a<p>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(NlogN&minus;&minus;&minus;&minus;&minus;&minus;&minus;&radic;) upper bound on the separation in routing time for any interaction graph - and give tighter bounds for some common classes of graphs.</p>10aFOS: Physical sciences10aQuantum Physics (quant-ph)1 aDevulapalli, Dhruv1 aSchoute, Eddie1 aBapat, Aniruddha1 aChilds, Andrew, M.1 aGorshkov, Alexey, V.  uhttps://arxiv.org/abs/2204.04185