Almost-Optimal Computational Basis State Transpositions

Abstract

We give an explicit construction to perform any $n$-qubit computational basis state transposition using $\hat{I}˜(n)$ gates. This nearly coincides with the lower bound $\hat{I}\text{c◯}(n/\log (nd))$ on worst-case and average-case gate complexity to perform transpositions using a $d$-element gate-set, which we also prove.

Newest version corrects some minor errors in previous version