Abstract
Let S_n be the symmetric group of all permutations of {1, …, n} with two generators: the transposition switching 1 with 2 and the cyclic permutation sending k to k+1 for 1≤ k≤ n-1 and n to 1 (denoted by σ and τ). In this article, we study quantum complexity of permutations in S_n using {σ, τ, τ⁻¹} as logic gates. We give an explicit construction of permutations in S_n with quadratic quantum complexity lower bound n²-2n-7/4. We also prove that all permutations in S_n have quadratic quantum complexity upper bound 3(n-1)². Finally, we show that almost all permutations in S_n have quadratic quantum complexity lower bound when n→ ∞.