Quantum Fourier transform over symmetric groups — improved result

详细信息    查看全文

• 作者：Yasuhito Kawano^a ; ^{kawano.yasuhito@lab.ntt.co.jp" class="auth_mail" title="E-mail the corresponding author} ; Hiroshi Sekigawa^b ; ^{sekigawa@rs.tus.ac.jp" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Quantum Fourier transform ; Fast Fourier transform ; Symmetric group ; Representation theory ; Non-abelian group
• 刊名：Journal of Symbolic Computation
• 出版年：2016
• 出版时间：July-August 2016
• 年：2016
• 卷：75
• 期：Complete
• 页码：219-243
• 全文大小：833 K

文摘

This paper describes the fastest quantum algorithm at this moment for the quantum Fourier transform (QFT) over symmetric groups. We provide a new FFT (classical) algorithm over symmetric groups and then transform it to a quantum algorithm. The complexity of our QFT algorithm is O(n³log⁡n)$O(n^3\log n)$, faster than the existing O(n⁴log⁡n)$O(n^4\log n)$ QFT algorithm. In addition, we show that the algorithm can be performed in O(n³)$O(n^3)$ if the use of threshold gates is allowed.