Almost-optimal computational-basis-state transpositions

Abstract

We give an explicit construction to perform any $n$-qubit computational-basis-state transposition using $\mathrm{\ensuremath{\Theta}}(n)$ gates. This nearly coincides with the lower bound $\mathrm{\ensuremath{\Omega}}[n/log(nd)]$ on worst-case and average-case gate complexities to perform transpositions using a $d$-element gate set, which we also prove.

Topics & Concepts