Quantum Complexity of Permutations

Let $S_n$ be the symmetric group of all permutations of $\{1,\cdots ,n\}$ with two generators: the transposition switching $1$ with $2$ and the cyclic permutation sending $k$ to $k+1$ for $1\le k\le n-1$ and $n$ to $1$ (denoted by $\sigma$ and $\tau$). In this article, we study quantum complexity of permutations in $S_n$ using $\{\sigma ,\tau ,{\tau }^{-1}\}$ as logic gates. We give an explicit construction of permutations in $S_n$ with quadratic quantum complexity lower bound $\frac{n^2-2n-7}{4}$. We also prove that all permutations in $S_n$ have quadratic quantum complexity upper bound $3(n-1{)}^2$. Finally, we show that almost all permutations in $S_n$ have quadratic quantum complexity lower bound when $n\to \mathrm{\infty }$.