量子 Fourier 变换 | Codeboy's Blog

形式陈述

令 $K=2^m$ 。固定寄存器顺序 $C_{m-1}\otimes\cdots\otimes C_0$ ，以 $|x\rangle=|x_{m-1}\cdots x_0\rangle$ 编码整数 $x=\sum_{j=0}^{m-1}2^jx_j$ 。本页采用正指数 convention：量子 Fourier 变换是

F_K|x\rangle=\frac1{\sqrt K}\sum_{y=0}^{K-1}e^{2\pi ixy/K}|y\rangle.

逆变换 $F_K^\dagger$ 将指数改成负号。它在量子态的振幅上作用；其输出仍是一个量子态，不能把全部 $K$ 个复数坐标直接读取出来。电路的张量顺序、时间顺序与局部门语义沿用量子电路。

为什么它是合法的量子操作

用复数的单位根求和，对任意 $x,x'$ ，

\langle F_Kx'|F_Kx\rangle =\frac1K\sum_{y=0}^{K-1}e^{2\pi i(x-x')y/K} =\begin{cases}1,&x=x',\\0,&x\ne x'.\end{cases}

第二种情形令 $z=e^{2\pi i(x-x')/K}$ ，则 $z\ne1$ 、 $z^K=1$ ，和为 $(1-z^K)/(1-z)=0$ 。因此列向量构成标准正交基， $F_K^\dagger F_K=I$ ，满足酉矩阵的条件。这里的归一化系数必须是 $1/\sqrt K$ 。

二进制分解与精确电路

写 $y=\sum_r2^ry_r$ ，指数中的各个 $y_r$ 可以分别求和，得到按从高位到低位排列的乘积态

F_K|x\rangle =\bigotimes_{r=m-1}^{0} \frac{|0\rangle+e^{2\pi ix/2^{m-r}}|1\rangle}{\sqrt2}.

记 $0.b_1\cdots b_\ell=\sum_{q=1}^\ell b_q2^{-q}$ 。上式各因子的相位从左到右是 $0.x_0,0.x_1x_0,\ldots,0.x_{m-1}\cdots x_0$ 。只有计算基输入的 Fourier 像保证这种乘积分解；任意输入叠加经过线性延拓，未必仍为乘积态。

定义 $R_\ell=\operatorname{diag}(1,e^{2\pi i/2^\ell})$ 。按下列顺序操作便得到精确电路：依次取 $j=m-1,m-2,\ldots,0$ ，先在 $C_j$ 做 $H$ ，再对每个 $k=j-1,\ldots,0$ ，以 $C_k$ 控制、在 $C_j$ 上做 $R_{j-k+1}$ 。所有这些步骤结束后，交换 $C_j$ 与 $C_{m-1-j}$ ，共 $\lfloor m/2\rfloor$ 次，完成位反转。

证明可逐条线检查。处理 $C_j$ 时，尚未处理的低位 $C_k$ 仍是计算基 $|x_k\rangle$ ，因而受控旋转给该线的 $|1\rangle$ 分量增加 $2\pi x_k/2^{j-k+1}$ 。连同 $H|x_j\rangle$ 的符号 $e^{\pi ix_j}$ ，总相位恰为 $2\pi(0.x_j\cdots x_0)$ 。反转前，因子从高位线到低位线为 $0.x_{m-1}\cdots x_0,\ldots,0.x_0$ ；末尾交换使它们与公式一致。对每个基向量成立，便对所有输入成立。

直觉

Fourier 基用不同的“相位转速”给振幅序列贴标签。 $F_K|x\rangle$ 的每个坐标模长都相同，区别藏在相邻坐标的相位差 $2\pi x/K$ 。因此对它直接做计算基测量会得到均匀分布，而施加逆变换则让相位相长集中到标签 $x$ 。

二进制电路把这个转速分散到 $m$ 条线上：最低精度的一条只区分半圈，下一条区分四分之一圈，最后一条保存到 $1/K$ 圈的细节。末尾位反转是在约定的张量顺序下对齐这些不同精度，不能在公式、代码和测量解释之间无声省略。

例子与边界

三位输入逐项验算

取 $m=3,x=5$ ，即 $|101\rangle$ 。处理高位 $C_2$ ： $H$ 给出半圈相位， $C_1=0$ 不加相位， $C_0=1$ 经 $R_3$ 再加 $1/8$ 圈，故该线相位为 $5/8$ 。处理 $C_1$ 得相位 $0+1/4=1/4$ ；处理 $C_0$ 得相位 $1/2$ 。交换 $C_2,C_0$ 后，

F_8|101\rangle =\frac{|0\rangle-|1\rangle}{\sqrt2} \otimes\frac{|0\rangle+i|1\rangle}{\sqrt2} \otimes\frac{|0\rangle+e^{5\pi i/4}|1\rangle}{\sqrt2}.

例如坐标 $y=3=011_2$ 的振幅为 $e^{2\pi i(1/4+5/8)}/\sqrt8=e^{2\pi i15/8}/\sqrt8$ ，与定义一致。逆电路必须先撤销交换，再将其余门按反序执行并把 $R_\ell$ 换成 $R_\ell^\dagger$ ；单独把旋转角取负而不倒转门序，不能一般地得到逆变换。

门数小不等于输出全部 Fourier 系数

上述电路有 $m$ 个 Hadamard、 $m(m-1)/2$ 个受控旋转以及 $\lfloor m/2\rfloor$ 个交换，门数为 $O(m^2)$ 。这个精确计数假定相应角度的旋转可作为门使用；若只允许固定有限门集，还要计入近似合成的误差和开销。

经典快速 Fourier 变换处理并输出整个长度 $K$ 的数值向量。QFT 的 $O((\log K)^2)$ 门数处理的是已经制备好的振幅编码，既不包含任意数据的装载成本，也不提供全部系数的经典列表。因此两种复杂度回答的任务不同，不能据此直接声称对经典 FFT 的指数加速。

推论与应用

量子相位估计先制造 $K^{-1/2}\sum_xe^{2\pi ix\varphi}|x\rangle$ ，再用 $F_K^\dagger$ 解码。当 $K\varphi$ 是整数时，相位标签被精确读出；否则多个 Fourier 标签共同承载概率。这也解释了为什么读取相位时应采用逆变换，而不能只凭“需要 Fourier 变换”选择正负号。

若 QFT 后立即测量，有时可通过重新解释经典输出位序省去最后的交换；若后面还要接门，则必须同步修改后续连线或保留交换。省门成立的依据是整体电路的等价，而不是位序没有物理意义。

参考资料

Andrew M. Childs, Lecture Notes on Quantum Algorithms，2025-04-17 版，§§4.1–4.2，印刷页 17–18：归一化 Fourier 变换、二进制因子分解与门电路。
Richard Cleve, Artur Ekert, Chiara Macchiavello, Michele Mosca, “Quantum Algorithms Revisited”，arXiv v1，1997-08-08，§4，特别是式 (4.5)–(4.6)。本文固定正指数 convention，并显式写出末尾位反转。

形式陈述 ​

为什么它是合法的量子操作 ​

二进制分解与精确电路 ​

三位输入逐项验算 ​

门数小不等于输出全部 Fourier 系数 ​

反向链接

形式陈述

为什么它是合法的量子操作

二进制分解与精确电路

三位输入逐项验算

门数小不等于输出全部 Fourier 系数