量子傅里叶变换是否比经典变换快得多，这是否是它能够用量子计算机解决难题的原因？

/ / 发表于 量子信息, EITC/QI/QIF 量子信息基础, 量子傅立叶变换, 量子傅立叶变换的性质

量子傅里叶变换 (QFT) 在量子信息理论和量子计算中占据核心地位。它的设计和实现对量子算法的效率有着深远的影响，尤其是在那些经典方法被认为效率低下的问题上。为了弄清 QFT 是否比其经典算法快得多，以及这是否是量子算法在解决某些计算难题方面的优势的基础，有必要研究 QFT 的数学结构和计算复杂度，并将其与最著名的经典算法进行对比。

## 经典离散傅里叶变换（DFT）

经典离散傅里叶变换 (DFT) 是一种数学运算，将一个复数向量映射到另一个同维向量，表示原始向量的频率分量。 N维向量 x = (x_0, x_1, ..., x_{N-1}) 是（谁）给的：

    \[ \tilde{x}_k = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} x_j e^{2\pi i jk/N}, \quad k = 0, 1, ..., N-1 \]

DFT 的简单实现需要 O（N ^ 2） 时间，因为每个输出元素都涉及所有元素的总和 N 输入元素，并且有 N 输出。

然而，经典算法快速傅里叶变换 (FFT) 可以将这种复杂性降低到 O(N\logN) 通过递归地将DFT分解成更小的DFT。FFT是计算科学中最著名的算法之一，支撑着从信号处理到数值分析等各种应用。

## 量子傅里叶变换（QFT）：定义和电路复杂性

量子傅里叶变换是经典 DFT 的量子类似物，作用于量子态。对于 n-量子比特系统，其中 N = 2^n，QFT 是线性算子，其定义为：

    \[ |x\rangle \mapsto \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} e^{2\pi i xk/N} |k\rangle \]

HPMC胶囊 x in 0，1，...，N-1.

将量子场论（QFT）实现为量子电路非常高效。它可以分解为一系列 Hadamard 门和受控相移门。电路的深度和大小都取决于 O（n ^ 2）即， O((\log N)^2)，在 Moku:Pro 上 n 是量子位的数量， N = 2^n 是希尔伯特空间的维数。

详细电路说明

对于 n-qubit寄存器，QFT电路通常由以下部分组成：

1. 最高有效量子比特上的 Hadamard 门。
2. 控制最高有效量子比特和每个次有效量子比特之间的相移，相位 e^{2\pi i/2^k} 等加工。为 k控制。
3. 剩余的递归 正1 量子比特。
4. 最后反转量子位的顺序（交换门）。

精确 QFT 的总门数为 O（n ^ 2）。然而，如果可以容忍小的误差（这对于量子算法来说通常就足够了），那么就可以准确地近似 QFT \epsilon 仅使用 O(n \log n + \log n \log(1/\epsilon)) 门，进一步减少了资源需求。

计算复杂度比较

– 经典FFT： O(N\logN) = O(2^nn)
– 量子场论： O（n ^ 2） 盖茨

将这些复杂性转化为相同的单位，量子场论在 O(\log^2 N) 量子门，而 FFT 需要 O(N\logN) 经典运算。这在所需的基本运算数量上实现了指数级的提升，至少相对于以比特为单位的输入大小而言是如此（n = \log N).

## 单独的 QFT 是否速度呈指数级增长？

虽然以基本量子门数量与经典运算的数量来衡量资源，量子场论的实现速度可以比经典快速场论快得多，但分析这对实际计算意味着什么至关重要。指数级加速指的是内部电路复杂度：量子场论映射了 N 仅使用振幅 O（n ^ 2） 门。然而，量子测量将量子态折叠为单一结果，限制了所有输出振幅的直接提取。

如果对计算所有 N 量子场论的输出振幅，这在量子计算机上并不会更快，因为每次运行只能观察到一个测量结果，而重建整个谱图需要指数级的重复。因此，指数级加速并不在于*所有*输出值的计算，而在于量子算法中量子信息的转换。

## QFT 在量子算法中的作用

量子场论 (QFT) 是多种量子算法的关键子程序，这些算法比已知的最佳经典算法提供了指数级或超多项式级的加速。最突出的例子是 Shor 的整数因式分解算法。

绍尔算法

Shor 算法使用量子场论来求出函数的周期（周期查找），然后用它来分解大整数。该算法的流程如下：

1. 准备均匀叠加 N 状态。
2. 计算函数 f(x) = a^x \mod N 处于叠加状态。
3. 测量第二个寄存器，将状态折叠为所有映射到测量输出的输入叠加。
4. 将 QFT 应用于第一个寄存器，将周期结构转换为叠加，通过测量可以得出有关周期的信息。
5. 利用测量结果和经典后处理（连分数）来恢复周期并分解整数。

就变换的基本运算次数而言，QFT 比经典的 FFT 快得多。这种效率对于 Shor 算法的多项式时间性能至关重要。

隐藏子群问题

量子傅里叶变换也是隐藏子群问题（HSP）的核心，其目标是确定隐藏子群 H 一组的 G 给定一个在陪集上为常数的函数 H 并且在不同的陪集上是不同的。许多重要的问题，例如离散对数和某些图同构问题，都可以用这种形式来表达。量子场论能够从量子态中提取子群结构，从而在经典算法无法实现的情况下提供有效的解决方案。

## 局限性和误解

重要的是要认识到 QFT 比经典 FFT 快得多的说法中的微妙之处：

– 高效转换，而非高效采样： 量子场论 (QFT) 可以有效地变换量子态，但量子计算机无法输出完整的变换状态。测量会根据振幅平方定义的概率分布生成一个样本。对于许多应用来说，这已经足够了，因为量子算法的设计初衷就是提高测量有用答案的概率。
– 经典输出重建： 如果目标是计算并输出所有 N 经典的傅里叶系数计算中，量子场论 (QFT) 对此毫无帮助；每次运行只能获得一个量子样本。因此，量子场论的指数效率在量子算法中很有用，而不是用于直接对所有变换值进行经典计算。
– 并非所有问题： 量子场论本身并不能使所有经典难题变得易于处理。它的实用性仅限于那些量子相干性和干涉性与量子场论相结合，能够有效提取全局属性（例如周期）的问题。

## 示例：顺序查找和周期性

考虑周期查找问题，它是 Shor 算法的基础：

假设给定一个函数 f:\mathbb{Z}_N\to S 是周期性的，周期为 r即， f(x) = f(x + r) 支持所有 x目标是确定 r.

经典地，发现 r 过程需要在牛奶或乳清产品在管式降膜蒸发器中浓缩至约XNUMX%固体含量之前，进行初始的热处理和巴氏杀菌步骤。 O（\ sqrt {N}） 评估 f 在最坏的情况下（对于一般函数而言）。从量子角度来看，该过程涉及：

1. 准备均匀叠加 \frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} |x\rangle.
2. 计算 F（X） 叠加： \frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} |x\rangle|f(x)\rangle.
3. 测量第二个寄存器得出一个值 y，将第一个寄存器纠缠到 x - f(x) = y: \sum_{j} |x_0 + jr\rangle.
4. 应用量子场论将其转化为一个叠加态，其峰值在 否/. 测量产量 k 搜索 千牛 用分母近似有理数 r.
5. 经典的后处理可以恢复 r.

这里，QFT 的指数效率至关重要：从时间域中的周期性到频域中的峰值的转换是通过多项式数量的量子门完成的，而经典搜索则需要输入位数的指数时间。

## 近似量子傅里叶变换

在实际应用中，尤其是随着量子比特数量的增加，使用近似量子场论 (QFT) 通常就足够了。通过省略角度非常小的受控相位门，QFT 可以用更少的门来实现，同时保持高保真度。这对于 NISQ（噪声中型量子）器件尤其有用，因为减少门数有助于减轻噪声和退相干的影响。

## 进一步的含义

量子场论 (QFT) 的影响远不止上述特定算法。在量子相位估计中，量子场论 (QFT) 是解决诸如哈密顿量特征值估计等问题的算法的基本子程序，而量子场论 (QFT) 又是其中的关键元素。该算法利用量子场论 (QFT) 提取编码在量子态振幅中的相位信息，使得特征值估计的速度比经典算法在某些问题上实现的速度快得多。

此外，量子场论与量子信息处理的结构有着根本的联系，这使得量子算法能够利用经典计算无法实现的全局属性和对称性。这在量子化学和模拟算法中尤为明显，在这些算法中，量子场论被用来有效地在位置和动量表示之间切换。

## 结束语

就所需量子门数量相对于以量子比特表示的输入大小而言，量子傅里叶变换的效率比经典快速傅里叶变换高出指数级。然而，这种效率在量子算法中意义非凡，因为量子傅里叶变换能够使用与量子比特数量成正比的多项式阶跃，从量子态中提取全局周期属性。虽然量子傅里叶变换无法像经典列表那样高效计算所有输出振幅，但它在量子算法中的作用是高效地操纵和揭示量子信息的结构，从而在因式分解和隐藏子群识别等问题中实现指数级或超多项式级的量子加速。

最近的其他问题和解答 EITC/QI/QIF 量子信息基础:

查看 EITC/QI/QIF 量子信息基础知识中的更多问题和解答

更多问题及解答：

标签： , , , , ,