论文标题
排列的量子复杂性
Quantum Complexity of Permutations
论文作者
论文摘要
令$ s_n $为$ \ {1，\ cdots，n \} $的所有排列的对称组，带有两个生成器：转换切换$ 1 $，$ 2 $，$ 2 $，循环排列将$ k $发送到$ k+1 $ to $ k+1 $ for $ 1 $ $ 1 \ leq k \ leq k \ leq n-1 $ and $ n $ $ $ $ $ 1 $（$ 1 $ $ 1 $ $ $ $ $ $ $ $ $ $ and）和$ 1 $（$ 1）。在本文中，我们使用$ \ {σ，τ，τ^{ - 1} \} $作为逻辑门研究$ s_n $中排列的量子复杂性。我们在$ s_n $中对二次量子复杂性的明确构造$ \ frac {n^2-2n-7} {4} $。我们还证明，$ s_n $中的所有排列都具有二次量子复杂度上限$ 3（n-1）^2 $。最后，我们表明，当$ n \ rightarrow \ infty $时，几乎所有$ s_n $中的排列都具有二次量子复杂性。
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 $σ$ and $τ$). In this article, we study quantum complexity of permutations in $S_n$ using $\{σ, τ, τ^{-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$.
