Quantum Fourier transform over symmetric groups --- improved result
Quantum Fourier transform over symmetric groups --- improved result
复制标题
对称群上的量子傅里叶变换——改进的结果
DOI：
10.1016/j.jsc.2015.11.016
复制
发表时间：
2016
影响因子：
0.7
通讯作者：
Yasuhito Kawano and Hiroshi Sekigawa
中科院分区：
文献类型：
--
作者：
Yuichi Asahiro;Yuya Doi;Eiji Miyano;Hirotaka Shimizu;八木田剛，朝廣雄一，宮野英次;朝廣雄一，ジェスパージャンソン，宮野英次，小野廣隆;竹田圭佑，朝廣雄一，宮野英次;Yasuhito Kawano and Hiroshi Sekigawa
本文描述了目前求解对称群上量子傅里叶变换（QFT）的最快量子算法。我们提供了一个新的FFT（经典）算法在对称群，然后将其转换为一个量子算法。我们的QFT算法的复杂度为O（n3 log n），比现有的O（n4 log n）QFT算法快。此外，我们表明，该算法可以在O（n 3），如果使用阈值门是允许的。
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 3 log n), faster than the existing O (n 4 log n) QFT algorithm. In addition, we show that the algorithm can be performed in O (n 3) if the use of threshold gates is allowed.