Quantum Fourier transform over symmetric groups — improved result

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(n3log⁡n), faster th...

Full description

Saved in:
Bibliographic Details
Published in:Journal of symbolic computation 2016-07, Vol.75, p.219-243
Main Authors: Kawano, Yasuhito, Sekigawa, Hiroshi
Format: Article
Language:English
Subjects:
Fast Fourier transform
Non-abelian group
Quantum Fourier transform
Representation theory
Symmetric group
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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(n3log⁡n), faster than the existing O(n4log⁡n) QFT algorithm. In addition, we show that the algorithm can be performed in O(n3) if the use of threshold gates is allowed.
ISSN:0747-7171
1095-855X
DOI:10.1016/j.jsc.2015.11.016