@article { WOS:000691579200002,
title = {Quantum routing with fast reversals},
journal = {Quantum},
volume = {5},
year = {2021},
month = {AUG 31},
publisher = {VEREIN FORDERUNG OPEN ACCESS PUBLIZIERENS QUANTENWISSENSCHAF},
type = {Article},
abstract = {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 approximate to 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 <= 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.},
issn = {2521-327X},
author = {Bapat, Aniruddha and Childs, Andrew M. and V. Gorshkov, Alexey and King, Samuel and Schoute, Eddie and Shastri, Hrishee}
}