Quantum Complexity of Permutations

Abstract: Let

S_{n}

be the symmetric group of all permutations of

1, c d o t s, n

with two generators: the transposition switching

1

with

2

and the cyclic permutation sending

k

to

k + 1

for

1 l e q k l e q n - 1

and

n

to

1

(denoted by

s i g m a

and

a u

). In this article, we study quantum complexity of permutations in

S_{n}

using

s i g m a, a u, a u^{- 1}

as logic gates. We give an explicit construction of permutations in

S_{n}

with quadratic quantum complexity lower bound

f r a c n^{2} - 2 n - 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 i g h t a r r o w i n f t y

.

This page was built for publication: Quantum Complexity of Permutations