“快速傅里叶变换的量子加速？”

研究人员数十年来一直在探索量子计算机的理论潜力。然而，直到最近，真正的系统才开始实现准确性和规模，使其未来的影响似乎成为可能。

吸引人们关注和投资的一个主要动力是彼得·肖尔（Peter Shor）在麻省理工学院提出的革命性方法，该方法可能使量子计算机能够破解当前的公钥加密方案。传统技术在分解数字所需的时间等资源随输入位数的增加呈指数级增长。肖尔的量子算法的需求仅以多项式函数增长，可能使加密数据在未来的量子计算机面前容易受到攻击。

这种方法的一个关键要素是在数据序列中快速确定主要重复频率的量子傅里叶变换的量子实现，而这指向一个大数的质因数。事实上，量子傅里叶变换（QFT）是许多指数级强大的量子算法的核心，这些算法迄今已被提出。（洛夫·格罗弗（Lov Grover）开发的另一类算法可以加快非结构化量子搜索，但只能以问题规模的幂增长。）

傅里叶变换已经广泛用于诸如图像处理等任务，但QFT并不能直接解决这些重要的应用问题。因此，旨在解决这一情况的研究人员开发了一种非常不同的量子方法，这可能成为更广泛的量子计算工具包的一部分。然而，到目前为止，量子优势似乎不太明显。

返回顶部

FFT：快速傅里叶变换

傅里叶变换将输入数据（例如随时间变化的一系列值）转换为频谱（幅度为复数）。在大多数数字应用中，输入包含某个数量N的离散样本，输出频谱包含N个空间或时间频率。频谱与原始数据完全等价，可以使用类似的过程重新构建。

此变换还提供了一种简单的方式来压缩数据，例如通过使用较低分辨率表示幅度或舍弃高频组件。例如，JPEG（联合图像专家组）格式可以让用户在保留最重要特征的同时缩小文件大小。傅里叶变换的变体“离散余弦变换”从二维像素数据计算空间频率分量。

在数学上，每个频率的振幅是通过在“旋转”之后相加所有输入点的值来计算的，乘以一个取决于频率和点索引的因子。因此，N个点和N个频率似乎需要N 2个乘积。然而，正如詹姆斯·库利（James Cooley）和约翰·图基（John Tukey）在1965年广为流传的，通过一种被称为快速傅里叶变换（FFT）的分治策略，计算过程可以大大加快。例如，如果N是2的幂，完整的变换可以通过不断将矩阵分成四个子矩阵来计算。此算法所需的资源仅随着N略微超线性增长（以N log N为例），而不是与N 2成比例。

返回顶部

QFT：量子傅里叶变换

量子计算的全部能力通过对傅里叶变换进行更强大的加速得到了证明，但其输出比FFT更受限制。例如，肖尔的分解算法确定了一个序列的主要周期（或频率），但不能确定其他频率的振幅。

肖尔指出，傅里叶变换是一种调查幅度中相关信息的自然方法，但“在最后，你必须找到一种提取你想要的信息的方法。”

为了确定周期，量子位或量子比特的状态被转换，就像在傅里叶变换中一样。在此操作之后，量子比特仍然包含所有输入信息。然而，通常情况下，这些操作涉及“微小微小的旋转，可能很快就会被噪声淹没出去，”法国格勒诺布尔阿尔卑斯大学Inria（法国计算机科学与自动化研究所）中心的阿拉斯泰尔·阿博特（Alastair Abbott）警告说，“找到一种稳健地执行这些操作的方法是困难的。”

从关键角度来说，提取这些信息只产生一个答案。当其值被测量时，每个量子比特必须取一个0或1的值，就像经典比特一样。更微妙的“量子信息”，例如表示多个可能结果，会在测量中消失。

阿博特说，傅立叶变换是一种询问幅度中相对信息的自然方式，但是“你必须最终找到一种提取你想要的信息的方法，这是非平凡的部分。”QFT的巧妙之处在于创建一个状态，其测量几乎可以确定地将表示目标周期性的量子比特测量为1，而其他量子比特则测量为0。

返回顶部

QFFT：量子快速傅立叶变换

尽管QFT的重要性毋庸置疑，但是QFT并不能提供广泛使用的FFT算法从中获得全部频谱信息的途径。为了解决这个问题，日本东京理科大学（TUS）的物理学家们提出了一个用于执行FFT的量子电路，他们称之为QFFT（尽管这个名字可能与QFT混淆）。

据称，该电路不太可能在经典FFT上展现量子加速效果，至少对于单个输入（例如图像）而言。然而，研究人员认为他们的电路可以并行地在多个图像上进行计算，而不需要额外的资源。

为了实现傅立叶变换，TUS团队使用了一种称为基编码的策略，他们说这是与QFT中的有效模拟测量操作基本不同的策略。通过将每个输入数据直接表示为量子比特的振幅的方式，输入数据被转化为二进制表示。然后，将二进制表示转移到多个量子比特的状态中。

量子电路的设计旨在对这些比特进行类似于经典电路的计算。其中的一个区别是，额外的输入流可以同时以量子“叠加”的形式嵌入到配置中，并同时对它们进行FFT计算。

“一些问题可能会变得更容易，而其他问题如果没有容错计算，你就没有多少希望。”

最终，测量转换后的输出只会产生一个结果。然而，如果延迟测量，该方案可以作为一个子程序嵌入到另一个可能利用完整傅立叶变换的量子计算中。TUS的研究生Ryo Asaka表示：“可以对QFFT的输出应用算术运算，比如加法和减法，但不能对QFT进行这样的操作。这是QFFT的一个优点。”然而，目前的大多数应用并不需要在多个图像之间进行比较，这很可能是保留傅立叶变换的多个量子表示最有力的方式。

重要的是，所需的资源应该包括用于计算输入所需的资源，这一点有时候被忽视。Asaka指出：“如果输入准备的时间与[输入]数量成比例增加，QFFT的优势就会消失。”为了避免这种结果，他设想准备一个复杂的量子比特配置，并将它们存储在量子随机存储器中。这样的“qRAM”在2000年代提出，但目前还没有实用化。

返回顶部

寻找量子优势

其他研究人员也试图想象如何将量子计算机用于主流任务。然而，尽管目前的量子计算机系统投入了大量的投资，但其中的量子比特太嘈杂，它们的精细量子状态会迅速丧失，而且数量太少，尽管系统越来越大、越来越好。 2019年，谷歌的一个团队宣布他们的系统执行了一个经典系统需要耗费数量级更长时间的任务，后来中国的研究人员描述了类似的实验证明。然而，所选择的任务并没有展示实际重要的能力。

从长远来看，大多数观察家预计大多数有趣的实际问题将依赖于量子纠错，这是一种可能需要更多量子比特的微妙技术。Abbott说：“某些问题可能会变得更容易。”但是许多“其他问题，如果没有适当的容错计算，你基本上没有什么希望可以解决。大多数量子傅立叶变换算法都属于后者的情况。”他补充说：“目前甚至不能将其做得糟糕。”

研究人员已经在当前“噪音中间规模量子”（NISQ）时代使用可用系统探索量子算法。其中一些最有前景的候选问题包括分子和材料的量子模拟。小型量子系统也可以用少量量子比特重演，比如最近有声称使用仅七个量子比特来模拟信息通过时空中的虫洞传输。

对于连低技术企业都引起高度关注的另一类问题是优化复杂系统的普遍挑战，例如制造资源或财务的分配。在存在大量噪声的情况下，通过混合经典-量子算法可能会找到最佳解决方案，例如（D-Wave Systems还推出了面向这些问题的拥有更多量子比特的机器，但许多研究人员质疑其操作是否真正量子力学，与更常见的基于门的架构不同。）

全球各国的公司和政府继续探索量子的可能算法、架构和物理实现。然而，具有成千上万个量子位的可靠、大规模容错计算系统可能仍然是几年后的事情，如果有的话。

进一步阅读

Asaka, R., Sakai, K., and Yahagi, R. “Quantum circuit for the fast Fourier transform,” Quantum Information Processing 19 , 277 (2020). DOI: https://doi.org/10.1007/s11128-020-02776-5

Arute, F. et al. “Quantum supremacy using a programmable superconducting processor,” Nature 574 , 505 (2019) DOI: https://doi.org/10.1038/s41586-019-1666-5

Hoefler, T., Thomas Häner, T, and Matthias Troyer, M. “Disentangling hype from practicality: On realistically achieving quantum advantage,” Communications 66 , 82 (2023). DOI: https://doi.org/10.1145/3571725

返回顶部

作者

Don Monroe是一位居住在美国佛蒙特州米德尔伯里的科学和技术作家。

未经费用授权，可以在个人或课堂使用的范围内制作部分或全部的数字或纸质副本，前提是不为获利或商业优势而制作或分发副本，并且在第一页上标明此通知和完整引文。必须尊重ACM之外持有此作品组成部分版权的人。抄录并署名是允许的。复制其他内容，重新发布，服务器上发布或分发到列表，需要事先特别许可和/或支付费用。请通过permissions@acm.org或传真（212）869-0481申请出版许可。