14、相位估计、量子傅里叶变换与 Deutsch 算法详解

相位估计、量子傅里叶变换与 Deutsch 算法详解

1. 相位估计与量子傅里叶变换基础

1.1 相位估计运算

对态 $|\psi\rangle$ 应用量子门 $P$，可得：
$P\left( \frac{1}{\sqrt{2^n}} \sum_{y = 0}^{2^n - 1} \exp{2\pi i\omega y}|y\rangle \right)$
最终结果为：
$P\left( \frac{1}{\sqrt{2^n}} \sum_{y = 0}^{2^n - 1} \exp{2\pi i\omega y}|y\rangle \right) = |\omega\rangle$

1.2 量子傅里叶变换（qFT）定义

量子傅里叶变换可通过反转相位估计算法的步骤得到。考虑二进制数 $x > 1$，其二进制展开为：
$x = x_12^{n - 1} + x_22^{n - 2} + \cdots + x_j2^{n - j} + \cdots + x_n2^0$，其中 $x_j = 0, 1$
$\omega = \frac{x}{2^n} = x_1\frac{1}{2} + x_2\frac{1}{2^2} + \cdots + x_n\frac{1}{2^n} \Rightarrow \omega \equiv 0.x_1x_2 \cdots x_n$
$y = y_n2^0 + y_{n - 1}2^1 + \cdots + y_j2^{n - j} + \cdots + y_12^{n - 1}$，其中 $y_j = 0, 1$
对于普通乘法 $xy$，有 $\fr