Pure and Applied Mathematics Quarterly

Volume 19 (2023)

Number 2

Quantum complexity of permutations

Pages: 575 – 595

DOI: https://dx.doi.org/10.4310/PAMQ.2023.v19.n2.a6


Andrew Yu (Harvard University, Cambridge, Massachusetts, U.S.A.; and Phillips Academy, Andover, Massachusetts, U.S.A.)


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.

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