量子傅里叶变换（QFT）把一个数写进相位里。在 n 个量子比特上，它把基态 |x⟩ 变成 Σᵧ e^{2πi·xy/2ⁿ} |y⟩ / √2ⁿ： 每个结果等可能，信息全部在相对相位之中。这条线路只需 n(n+1)/2 个门：每个量子比特上一个 Hadamard 门、成对量子比特之间的受控相位旋转 `cp(π/2ᵏ)`，以及最后把量子比特顺序倒过来的交换门。 在相位估计中，正是 QFT 这一步把相位变成可以读出的数，因而在因数分解中也是如此。相位估计反过来使用它：*逆* QFT。 这道练习的意图是 *equivalent*（等价）：你的整个程序必须与恒等线路在相差一个全局相位的意义下是同一条线路。引擎在全部 8 个基态上逐一判定，由证明检查。角度 π/2 和 π/4 是二进分数（dyadic），所以这个程序也能逐位精确地运行。