视频字幕
量子傅里叶变换是经典傅里叶变换在量子计算中的对应版本。经典傅里叶变换能够将时域信号转换为频域表示，揭示信号的频率成分。而量子傅里叶变换则在量子计算机上实现类似的功能，但具有指数级的计算优势。它是许多重要量子算法的核心组件，包括著名的Shor算法和量子相位估计算法。
量子傅里叶变换的数学定义是将计算基态j变换为所有基态的叠加，其中每个基态k的振幅包含复数相位因子。QFT可以用一个酉矩阵表示，其中矩阵元素由复数单位根ω的幂次构成。这里ω等于e的2πi除以N次方，它们在复平面上均匀分布在单位圆上。QFT具有重要的数学性质：它是酉变换，因此可逆且保持量子态的归一化；它利用了复数单位根的周期性；相比经典离散傅里叶变换，QFT能够实现指数级的计算加速。
量子傅里叶变换可以通过量子电路来实现。QFT电路主要由三种量子门构成：Hadamard门、受控相位门和量子比特交换门。Hadamard门将量子比特置于叠加态，其矩阵表示为二分之一倍的一一、一负一矩阵。受控相位门在控制比特为1时对目标比特施加相位旋转，相位角度为2π除以2的k次方。对于n个量子比特的QFT，电路深度为O(n²)，总共需要O(n²)个量子门。电路的构建过程是：首先对每个量子比特应用Hadamard门，然后应用一系列受控相位门来建立量子比特间的相位关系，最后通过交换门来调整量子比特的顺序，得到正确的QFT输出。
让我们通过一个2量子比特的具体例子来理解QFT的计算过程。从输入态|00⟩开始，首先对第0个量子比特应用Hadamard门，将其变为叠加态，得到二分之一倍的|00⟩加|10⟩。接下来应用受控相位门CR₂，由于控制位和目标位都不是|1⟩，所以状态保持不变。然后对第1个量子比特应用Hadamard门，最终得到四分之一倍的所有计算基态的等权叠加。在复数平面上，我们可以看到量子态从单一方向的向量逐步演化为四个等长向量的叠加，体现了QFT将局域化的量子态转换为完全去局域化叠加态的特性。
量子傅里叶变换在多个重要的量子算法中发挥核心作用。首先是著名的Shor算法，用于大整数的质因数分解。在Shor算法中，QFT负责从量子叠加态中提取周期信息，这是破解RSA加密的关键步骤。其次是量子相位估计算法，它能够估计酉算子的本征值相位，是许多量子算法的重要子程序，在量子机器学习和优化问题中有广泛应用。QFT还被用于量子搜索算法的加速、量子模拟中的哈密顿演化，以及量子化学计算等领域。与经典的快速傅里叶变换相比，量子傅里叶变换实现了真正的指数级加速：经典FFT的复杂度是O(N log N)，而量子QFT只需要O(log²N)，这种巨大的计算优势正是量子计算威力的体现。