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