



@article {2751,
	title = {Quantum routing with fast reversals},
	journal = {Quantum},
	volume = {5},
	year = {2021},
	month = {8/24/2021},
	chapter = {533},
	abstract = {<p>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 ϵ\&asymp;0.034 such that the quantum routing time is at most (1\&minus;ϵ)n, whereas any swap-based protocol needs at least time n\&minus;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(k2) on paths and at most 2r/3+O(k2) on general graphs with radius r.</p>},
	doi = {https://doi.org/10.22331/q-2021-08-31-533},
	url = {https://arxiv.org/abs/2103.03264},
	author = {Aniruddha Bapat and Andrew M. Childs and Alexey V. Gorshkov and Samuel King and Eddie Schoute and Hrishee Shastri}
}
