量子计算机使用一种称为**量子傅里叶变换 (QFT)**的量子电路来执行傅里叶变换。QFT 是一种线性变换，它将表示数据的量子态映射到基于频率的表示，类似于经典的快速傅里叶变换 (FFT)。然而，QFT 处理的是量子振幅而不是经典数据，这使其能够高效处理叠加态。其核心机制涉及将一系列量子门（主要是 Hadamard 门和受控相位旋转门）应用于纠缠的量子比特。这些操作将输入态分解为振荡分量的组合，从而揭示量子数据中的周期性模式。
QFT 电路是通过迭代输入寄存器中的每个量子比特构建的。对于位置为 j 的给定量子比特（从最低有效位开始），首先应用一个 Hadamard 门，将其置于叠加态。然后，在一系列受控相移门（例如 R_k 门，其中 R_k 应用 2π/2^k 的相位）施加到量子比特 j 和所有更高索引的量子比特 k > j 之间。这些相位旋转将频率信息编码到量子比特的相对相位中。例如，在一个 3 量子比特系统中，第一个量子比特 (j=0) 将经历一个 Hadamard 门，接着与量子比特 1 之间施加一个受控 R_2 门（相位 π/2），与量子比特 2 之间施加一个受控 R_3 门（相位 π/4）。这个过程对量子比特 1 和 2 重复，相移递减。最后，量子比特被重新排序（例如通过交换操作），以考虑 QFT 固有的位反转输出顺序。
QFT 的效率源于其在量子比特数量方面的对数深度。对于 n 个量子比特，电路需要 O(n²) 个门，而经典 FFT 需要 O(n2ⁿ) 次操作，这为某些任务提供了指数级的加速。然而，这种优势是依赖于上下文的：QFT 在用作 Shor 质因数分解算法等算法的子程序时最强大，因为它可以在量子态中识别周期性。开发者应该注意，QFT 的输出不是直接可读的；它必须结合测量或进一步处理才能提取有用的经典信息。实际实现通常涉及优化门序列以最大限度地减少误差，特别是在噪声量子硬件上。