  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\leq k\leq 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\rightarrow \infty$.
