快速傅里叶变换

快速傅里叶变换(Fast Fourier Transform, FFT)是现代生活中的幕后数字主力,在这个处处需要连接设备万物互联的世界中,它使人们的信号传输成为现实,是一条不折不扣的数字捷径。

虽然人们随手打开的小视频诸如抖音、微信视频等很短,但其中的每一分钟,都需要计算数百个FFT。在这个数字时代,FFT是数据处理的基本工具。

这就解释了为什么一些研究人员,开始探索使用量子计算机,来更有效运行FFT算法的可能性。

伦敦帝国学院的物理学家Ian Walmsley表示,快速傅里叶变换是一种极为重要的算法,在经典计算的世界里,产生了很多应用。

跃马扬鞭,看量子计算机如何加速傅里叶变换-量子客
图1|Ian Walmsley(来源:伦敦帝国学院)

当然,不管是经典计算的世界,在量子时代中,我们也期冀FFT的应用。因此,现在最核心的是,找到实践它的有效途径。

 

量子傅里叶变换

1994年,Peter Shor发现了量子计算机的首款杀手级应用程序——质因数分解。因此,Shor设计的算法,比以往任何人在任何经典计算机上设计的算法,都能更有效、更快速的进行数字因式分解。

而这款令人惊叹量子引擎的核心是一个子程序——量子傅里叶变换(Quantum Fourier Transform, QFT)

FFT——快速傅里叶变换,Fast Fourier Transform

QFT——Shor的算法中心子程序,量子傅里叶变换,Quantum Fourier Transform

QFFT——量子快速傅里叶变换,Quantum Fast Fourier Transform

尽管以上的术语代表了不同的算法,并会相应产生不同的计算结果。但它们都基于相同的核心数学概念,即离散傅里叶变换(Discrete Fourier Transform,DFT)。

虽然无法断言哪个会成为下一个FFT,但QFT有望最先找到技术应用程序。而QFT和QFFT,似乎更有可能为新一代量子应用程序提供所需动力。

 

魔术表演的戏台搭设

东京理科大学的研究人员称,一旦攻破QFFT的量子电路,它便会为未来的量子算法奠定基础

跃马扬鞭,看量子计算机如何加速傅里叶变换-量子客
图2|东京理科大学的量子研究人员(来源:东京理科大学)

QFFT算法处理单个数据流的速度,与经典的FFT相同。然而,QFFT的优势不在于独自处理单个数据流,而是同时处理多个数据流。

量子叠加使之成为可能,它允许一组量子比特同时对多种信息状态进行编码。因此,QFFT在高性能和节能信息处理之间,找到了平衡。

东京研究人员高效利用量子比特设计了量子电路,没有产生所谓的冗余比特,这种冗余比特会干扰量子计算。而研究人员的下一步就是开发量子随机存取存储器,用于大量数据的预处理[2]。

东京理科大学的物理系研究生,也是本次研究的主要作者Ryo Asaka表示,QFFT和本文中的算术运算,只有在与其他部分作为子程序组合使用时,才能发挥其实力

加利福尼亚大学戴维斯分校的数学家Greg Kuperberg表示,日本团队的工作为未来的量子算法奠定了基础。本身并不能成为一个神奇的解决方案,更像是在为他人的魔术表演,搬运所需设备。

 

魔法世界的入场券

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

但他认为,QFFT在不同量子计算机上的运行表现可能会不一样(例如磁光阱与钻石中的氮空位),并且最终可能会成为量子-经典混合计算系统专用协处理器

波兰华沙大学的物理学家Magdalena Stobińska,是欧盟委员会AppQInfo(Applications and Hardware for Photonic Quantum Information Processing)项目[3]的主要协调员。

跃马扬鞭,看量子计算机如何加速傅里叶变换-量子客
图3|Magdalena Stobińska(来源:Warszawa)

该项目从2021年开始,就针对青年研究人员进行量子信息处理方面的培训。她指出,QFFT新的量子算法的开发,是一个备受关注的主题。

她认为,这项工作的真正价值在于,它提出了一种不同的数据编码方式,这种方式可以在量子计算机上进行FFT的计算。而且其创新思维,为其他新的量子算法打开了大门。

 

参考链接:

[1]https://spectrum.ieee.org/computing/software/quantum-computers-will-speed-up-the-internets-most-important-algorithm

[2]https://link.springer.com/article/10.1007/s11128-020-02776-5

[3]https://cordis.europa.eu/project/id/956071

 

声明:此文出于传递高质量信息之目的,若来源标注错误或侵权,请作者持权属证明与我们联系,我们将及时更正、删除,所有图片的版权归属所引用组织机构,此处仅引用,原创文章转载需授权。

|编  辑:王嘉雯      |审  校:丁艳