Quantum complexity of permutations

Quantum complexity of a unitary measures the runtime of quantum computers. In this article, we study the complexity of a special type of unitaries, permutations. Let $S_n$ be the symmetric group of all permutations of ${\lbrace 1, \dotsc , n \rbrace}$ with two generators: the transposition and the cyclic permutation (denoted by $\sigma$ and $\tau$). The permutations ${\lbrace \sigma, \tau, \tau^{-1} \rbrace}$ serve 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 \infty$. The method described in this paper may shed light on the complexity problem for general unitaries in quantum computation.

Full Text (PDF format)

The author was supported by ARO MURI grant W911NF-20-1-0082.

Received 6 August 2022

Received revised 22 August 2022

Accepted 18 September 2022

Published 7 April 2023