Quantum Fourier transform over symmetric groups — improved result. (July 2016)

• Record Type: Journal Article
• Authors: Kawano, Yasuhito; Sekigawa, Hiroshi
• Is Part Of: Journal of symbolic computation. Volume 75(2016)
• Page Start: 219
• Page End: 243
• Publication Date: 2016-07
• Subjects: Quantum Fourier transform -- Fast Fourier transform -- Symmetric group -- Representation theory -- Non-abelian group; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2015.11.016
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: 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.