快速傅里叶变换（Fast Fourier Transform, FFT）支持着现代数字生活，在这个处处需要连接设备万物互联的世界中，它使数据处理和信号传输成为现实。像抖音这样的流行的小视频每一分钟，都需要计算数百个FFT。

1994年Peter Shor发现的量子计算首款杀手级应用程序——质因数分解，其核心就是量子傅里叶变换（Quantum Fourier Transform, QFT）子程序。

最近，东京理科大学物理系的研究团队提出了QFFT——量子快速傅里叶变换，Quantum Fast Fourier Transform，论文发表在Quantum Information Processing（Arxiv）。一作是研一学生Ryo Asaka，通信作者Kazumitsu Sakai。

论文摘要：

We propose an implementation of the algorithm for the fast Fourier transform (FFT) as a quantum circuit consisting of a combination of some quantum gates. In our implementation, a data sequence is expressed by a tensor product of vector spaces. Namely, our FFT is defined as a transformation of the tensor product of quantum states. It is essentially different from the so-called quantum Fourier transform (QFT) defined to be a linear transformation of the amplitudes for the superposition of quantum states. The quantum circuit for the FFT consists of several circuits for elementary arithmetic operations such as a quantum adder, subtractor and shift operations, which are implemented as effectively as possible. Namely, our circuit does not generate any garbage bits. The advantages of our method compared to the QFT are its high versatility, and data storage efficiency in terms, for instance, of the quantum image processing. 我们提出了一种用于快速傅立叶变换（FFT）算法的实现，是由一些量子门的组合组成的量子电路。 在我们的实现中，数据序列由向量空间的张量积表示。 即，我们的FFT被定义为量子态张量积的变换。 它与所谓的量子傅里叶变换（QFT）本质上不同，QFT被定义为振幅的线性变换，以叠加量子态。 用于FFT的量子电路由几个用于基本算术运算的电路组成，例如量子加法器、减法器和移位运算，这些电路应尽可能有效地实现。 也就是说，我们的电路不会产生任何垃圾位。 与QFT相比，我们的方法的优势在于它的多功能性以及数据存储效率（例如量子图像处理中）。

伦敦帝国学院的Walmsley表示，QFFT受现实世界条件的约束，在量子计算机上运行的表现，目前还是未知的。

波兰华沙大学的物理学家Magdalena Stobińska指出，QFFT新的量子算法的开发，是一个备受关注的主题。她认为，这项工作的真正价值在于，它提出了一种不同的数据编码方式，这种方式可以在量子计算机上进行FFT的计算。而且其创新思维，为其他新的量子算法打开了大门。

部分文字来自知乎上Qtumist量子客的文章：跃马扬鞭，看量子计算机如何加速傅里叶变换 另可参见东京理科大学官网新闻稿：Bringing a Power Tool from Math into Quantum Computing

内容中包含的图片若涉及版权问题，请及时与我们联系删除