量子傅里叶变换（QFT）是经典离散傅里叶变换的量子模拟。它作用于量子态，将一组振幅（编码信息）转换为频域表示。数学上，它对量子比特应用特定的酉变换，将状态 (|j\rangle) 映射到由复数单位根加权的状态叠加。与按顺序处理数据的经典快速傅里叶变换（FFT）不同，QFT 利用量子叠加作用于所有振幅，实现并行处理。其电路实现使用一系列 Hadamard 门和受控相位旋转，其结构随量子比特数量呈二次方缩放（对于 n 个量子比特，需要 O(n²) 个门）。这种效率是它在量子算法中发挥作用的关键。
QFT 通过实现对周期性或结构化数据的有效分析来加速量子算法。例如，Shor 因数分解算法使用 QFT 来识别函数的周期，这是将大数分解为质数的关键步骤。经典方法中，寻找此类周期需要检查指数级数量的值，但 QFT 允许量子态相长干涉，放大正确周期的信号。QFT 同时处理所有可能状态（通过叠加）并提取全局模式（通过干涉）的能力，将计算步骤从指数级降低到多项式级。这是可能的，因为 QFT 避免了显式遍历所有输入，而是以一种将测量结果坍缩为有用信息的方式变换量子态。
Shor 算法就是一个具体例子，其中 QFT 在模幂运算步骤后应用。QFT 将累积的相位信息转换为可测量的频率，揭示函数的周期。类似地，量子相位估计算法（许多算法中的子程序）依赖于 QFT 来确定量子算符的本征值。这些应用利用了 QFT 以最少的操作处理编码在量子态中的大型数据集的能力。虽然经典 FFT 需要对 N 个数据点进行 O(N log N) 次操作，但 QFT 对 n 个量子比特（编码 N=2ⁿ 个值）的操作只需 O(n²) 个门，这使得它对于符合此结构的许多问题具有指数级的速度优势。这种效率是 QFT 成为许多量子加速基础的原因，尽管它并非普遍适用——它在周期性或相位关系是核心的问题上表现出色。