量子计算（六）——量子傅里叶变换与相位估计

一、离散傅里叶变换简介

注意

这一节的内容可以跳过，直接观看 “二、量子傅里叶变换” ！
这一节的内容仅仅是对数值分析及信号系统内容的极其粗略的概括，会忽略大量严谨的细节，细节内容请翻阅或移步与数值分析或信号系统相关的教材或文章。

1.函数的范数与内积

不妨思考一个问题：我们知道对于向量来说存在正交分解——也就是可以将 $𝑛$ 维向量表示为 $𝑛$ 个正交基分量的线性和，甚至只要几个分量线性无关即可——那么对于函数来说是否也有类似的操作，可以分解为几个正交函数呢？

这个问题首先要解决的是：如何将函数视作一个向量(这样才能定义函数的正交)？或者说，向量应当具有什么性质？我们常说，向量是具有方向的数量，因此为了将函数向量化，就应当有某种手段衡量其方向与数量。不妨首先介绍衡量数量的手段，这意味着我们必须将一个函数整体映射为一个实数。对于我们所熟知的向量，其数量(一般会称之为长度)是：

\begin{aligned} | 𝒙 | = & {(𝑥_{1}^{2} + 𝑥_{2}^{2} + \dots + 𝑥_{𝑛}^{2})}^{\frac{1}{2}} \\ = & {(\sum_{𝑘 = 1}^{𝑛} 𝑥_{𝑘}^{2})}^{\frac{1}{2}} \end{aligned}

在线性空间中更规范的称呼是 2-范数，记为 ${‖ 𝒙 ‖}_{2}$ ，特点是将其在各分量上的大小平方累加后再开方。对于函数 $𝑓 (𝑥)$ 就能以类似的方法定义其 2-范数，只要将函数在各点上与 $𝑥$ 轴围成的面积视作分量大小即可——当然这也意味着我们必须事先指定函数的定义域，其 2-范数才是有意义的：

定义 1.（函数的2-范数）

\begin{aligned} {‖ 𝑓 (𝑥) ‖}_{2} = & lim_{Δ 𝑥 \to 0} {(\sum_{𝑘 = 1}^{\frac{𝑏 - 𝑎}{Δ 𝑥}} 𝑓^{2} (𝑎 + 𝑘 Δ 𝑥) \cdot Δ 𝑥)}^{\frac{1}{2}} \\ = & {(\int_{𝑎}^{𝑏} 𝑓^{2} (𝑥) 𝑑 𝑥)}^{\frac{1}{2}} \end{aligned}

现在可以思考如何衡量函数的方向了——当然在这里我们只关心如何确定函数正交。在熟知的线性空间中，向量的 2-范数也可视作自内积后开方，而两个向量正交则是由内积后是否为 $0$ 来判断的！由此仿照向量内积、结合函数 2-范数的形式，即可定义两个函数 $𝑓 (𝑥), 𝑔 (𝑥)$ 的内积 $(𝑓, 𝑔)$ ：

定义 2.（函数的内积）

(𝑓, 𝑔) = \int_{𝑎}^{𝑏} 𝑓 (𝑥) \cdot 𝑔 (𝑥) 𝑑 𝑥

当内积为 $0$ 时，就可以称 $𝑓 (𝑥), 𝑔 (𝑥)$ 是正交的了。

2.正交函数系与三角拟合

与向量类似，我们或许会热衷于将函数分解为正交函数的线性叠加。定义在 $[- 𝜋, 𝜋]$ 上 ¹¹ 定义在 $[0, 2 𝜋]$ 上也是可以的的三角函数系 $[1, cos 𝑘 𝑥, sin 𝑘 𝑥], 𝑘 = 1, 2, \dots$ 正是这样一种性质优异的正交函数系，因为：

\begin{matrix} \int_{- 𝜋}^{𝜋} cos 𝑘 𝑥 𝑑 𝑥 = \int_{- 𝜋}^{𝜋} sin 𝑘 𝑥 𝑑 𝑥 = 0 \\ \int_{- 𝜋}^{𝜋} cos 𝑘 𝑥 \cdot sin 𝑛 𝑥 𝑑 𝑥 = 0, 𝑘 \neq 𝑛 \\ \int_{- 𝜋}^{𝜋} cos 𝑘 𝑥 \cdot cos 𝑛 𝑥 𝑑 𝑥 = 0, 𝑘 \neq 𝑛 \\ \int_{- 𝜋}^{𝜋} sin 𝑘 𝑥 \cdot sin 𝑛 𝑥 𝑑 𝑥 = 0, 𝑘 \neq 𝑛 \end{matrix}

因此某些函数 $𝑓 (𝑥)$ 应当能被表示为这些三角函数的线性叠加——或者至少能利用最小二乘法被最佳逼近！这便是三角拟合，也即我们常说的傅里叶级数(的三角形式)了：

𝑓 (𝑥) = \frac{𝑎_{0}}{2} + \sum_{𝑘 = 1}^{+ \infty} 𝑎_{𝑘} cos 𝑘 𝜔_{0} 𝑥 + 𝑏_{𝑘} sin 𝑘 𝜔_{0} 𝑥

这意味着函数 $𝑓 (𝑥)$ 有无穷多的、 $𝑘 𝜔_{0}$ 频率的谐波，无论 $𝑘$ 多大。当然为了计算上的方便、形式上的美观，利用欧拉公式，我们更喜爱傅里叶级数的复指数形式：

𝑓 (𝑥) = \sum_{𝑘 = - \infty}^{+ \infty} 𝑐_{𝑘} e^{i 𝑘 𝜔_{0} 𝑥}

必须指出，上面的级数只能拟合周期为 $\frac{2 𝜋}{𝜔_{0}}$ 的连续函数，但不局限于实函数。而对于周期为 $𝑁 = \frac{2 𝜋}{𝜔_{0}}$ 离散函数 $𝑓 [𝑥]$ ，如果研究离散的复指数函数 $e^{i 𝑘 𝜔_{0} 𝑥}$ ，你会发现每当 $𝑘$ 增加一个周期 $𝑁$ ，却依然变回自身即 $e^{i 𝑘 𝜔_{0} 𝑥}$ ——这意味着周期离散函数的谐波频率具有上界，故离散函数的傅里叶级数是：

𝑓 [𝑥] = \sum_{𝑘 = ⟨ 𝑁 ⟩} 𝑐_{𝑘} e^{i 𝑘 𝜔_{0} 𝑥} = \sum_{𝑘 = ⟨ 𝑁 ⟩} 𝑐_{𝑘} e^{i 𝑘 \frac{2 𝜋}{𝑁} 𝑥}

²² 这里在求和号下的 $𝑘 = ⟨ 𝑁 ⟩$ 表示：只要是在一个周期 $𝑁$ 上对 $𝑘$ 进行的求和即是合法的。同时也能求出：

𝑐_{𝑛} = \frac{1}{𝑁} \sum_{𝑘 = ⟨ 𝑁 ⟩} 𝑓 [𝑘] e^{- i 𝑘 \frac{2 𝜋}{𝑁} 𝑛}

2.对复向量的离散傅里叶变换

对傅里叶级数系数的计算：

𝑐_{𝑛} = \frac{1}{𝑁} \sum_{𝑘 = ⟨ 𝑁 ⟩} 𝑓 [𝑘] e^{- i 𝑘 \frac{2 𝜋}{𝑁} 𝑛}

实际上彰显了各谐波在函数 $𝑓 [𝑥]$ 中的强度(也就是我们常说的从时域到频域)——这不就是对函数的正交分解么！但是现在我们又回归到了向量身上，因为对于周期为 $𝑁$ 的离散函数而言，只要采样确定 $𝑁$ 个取值就已经获得了函数的所有信息。不妨重新记这连续的 $𝑁$ 个函数值 $𝑓 [𝑘]$ 为复向量：

𝒙 = [𝑥_{0}, 𝑥_{1}, \dots, 𝑥_{𝑁 - 1}]

³³ 当然您会说：为什么不需要记录各函数值对应的时间点？首先，我们总能定义开始观察的时间点为零点；其次，时间平移操作作用到傅里叶级数系数上时只会使其附加一个 $e^{- i 𝑘 𝜔_{0} 𝑡_{0}}$ 的相位系数，其中 $𝑡_{0}$ 是时间平移的量，而这个系数的模为 $1$ ，并不会影响到我们评估谐波分量的强度。并记输出为复向量 $𝒚$ ，于是有：

𝑦_{𝑘} = \frac{1}{𝑁} \sum_{𝑗 = ⟨ 𝑁 ⟩} 𝑥_{𝑗} e^{- i 𝑗 \frac{2 𝜋}{𝑁} 𝑘}

当发生时间反演时也不改变谐波分量的强度，因此不妨假定我们总反转一下时间即取 $𝑗 \to - 𝑗$ ，这样可以去掉复指数函数上烦人的负号：

𝑦_{𝑘} = \frac{1}{𝑁} \sum_{𝑗 = ⟨ 𝑁 ⟩} 𝑥_{𝑗} e^{i 𝑗 \frac{2 𝜋}{𝑁} 𝑘}

另一方面，式前的系数 $\frac{1}{𝑁}$ 取什么也并不重要，或者说只在特定的场景下重要(其实际作用是为了归一化)——而在量子傅里叶变换中，只有取 $\frac{1}{\sqrt{𝑁}}$ 才是重要的。这样我们终于得到在量子傅里叶变换中我们所期望的离散傅里叶变换形式：

定义 3.（离散傅里叶变换）

𝑦_{𝑘} = \frac{1}{\sqrt{𝑁}} \sum_{𝑗 = 0}^{𝑁 - 1} 𝑥_{𝑗} \cdot e^{i \frac{2 𝜋}{𝑁} 𝑗 𝑘}

二、量子傅里叶变换

1.离散傅里叶变换的量子化

已知离散傅里叶变换的形式是：

𝑦_{𝑘} = \frac{1}{\sqrt{𝑁}} \sum_{𝑗 = 0}^{𝑁 - 1} 𝑥_{𝑗} \cdot e^{i \frac{2 𝜋}{𝑁} 𝑗 𝑘}

其中， $𝑥_{𝑗}$ 是复向量 $𝒙 = [𝑥_{0}, 𝑥_{1}, \dots, 𝑥_{𝑁 - 1}]$ 中的元素， $𝑦_{𝑘}$ 是复向量 $𝒚 = [𝑦_{0}, 𝑦_{1}, \dots, 𝑦_{𝑁 - 1}]$ 中的元素，两个复向量应当且必然具有相同数量的元素。现在不妨将上式量子化。既然已知 $𝑦_{𝑘}$ 的计算式，那么复向量 $𝒚$ 也就轻易写出：

\begin{aligned} 𝒚 & = 𝑦_{0} [1, 0, \dots, 0] + 𝑦_{1} [0, 1, \dots, 0] + \dots + 𝑦_{𝑁 - 1} [0, 0, \dots, 1] \\ * Using Dirac Notation * \\ = \sum_{𝑘 = 0}^{𝑁 - 1} 𝑦_{𝑘} | 𝑘 ⟩ \\ = \frac{1}{\sqrt{𝑁}} \sum_{𝑘 = 0}^{𝑁 - 1} {\sum_{𝑗 = 0}^{𝑁 - 1} 𝑥_{𝑗} \cdot e^{i \frac{2 𝜋}{𝑁} 𝑗 𝑘}} | 𝑘 ⟩ \\ = ℱ︀ {𝒙} \end{aligned}

那么，当复向量 $𝒙$ 恰为计算基态 $| 𝑗 ⟩$ 时，此时 $𝒙$ 中只有第 $𝑗$ 位为 $1$ 而其余为 $0$ ，这意味着大括号中只剩下 $e^{i \frac{2 𝜋}{𝑁} 𝑗 𝑘}$ ，代入得到：

ℱ︀ {| 𝑗 ⟩} = \frac{1}{\sqrt{𝑁}} \sum_{𝑘 = 0}^{𝑁 - 1} e^{i \frac{2 𝜋}{𝑁} 𝑗 𝑘} | 𝑘 ⟩

从而量子化了离散傅里叶变换，所得到的形式是针对计算基态的傅里叶变换。当然不妨进一步改写：对于量子傅里叶变换来说显然有一些 $𝑁$ 值是不能取到的，例如 $5$ ——因为当有 $𝑁$ 个量子位时，将产生 $2^{𝑁}$ 个计算基态。故将上式中的 $𝑁$ 全部替换为 $2^{𝑁}$ 得：

ℱ︀ {| 𝑗 ⟩} = \frac{1}{2^{\frac{𝑁}{2}}} \sum_{𝑘 = 0}^{2^{𝑁} - 1} e^{i \frac{2 𝜋}{2^{𝑁}} 𝑗 𝑘} | 𝑘 ⟩

2.量子傅里叶变换的直积态形式

由于量子态可以叠加，只要实现了对计算基态的量子傅里叶变换，就实现了对任意量子态的量子傅里叶变换。为了得到计算基态之傅里叶变换的量子电路图，我们必须进一步改写上式。

注意到上式左边是以直积态形式写出的计算基态，而右边却以附带相位的计算基态之线性和写出。为了更加契合两边的形式，同时为了确认每一个量子最后所处的量子态，需要将右边改写为直积态形式。为此，首先将 $𝑗$ 展开写为二进制形式， $𝑘$ 也展开写为二进制形式，于是上式右边可以重新计算——首先是对 $𝑘$ 从 $0$ 到 $2^{𝑁} - 1$ 的遍历，按二进制展开可得：

\sum_{𝑘 = 0}^{2^{𝑁} - 1} e^{i \frac{2 𝜋}{2^{𝑁}} 𝑗 𝑘} | 𝑘 ⟩ = \sum_{𝑘_{1} = 0}^{1} \dots \sum_{𝑘_{𝑁} = 0}^{1} e^{i 2 𝜋 𝑗 \cdot \sum_{𝑙 = 1}^{𝑁} 𝑘_{𝑙} 2^{- 𝑙}} | 𝑘_{1} 𝑘_{2} \dots 𝑘_{𝑁} ⟩

其中，将指数部分的分母重新组合，使得指数中的 $𝑘$ 重写为二进制小数的形式：

\begin{aligned} \frac{𝑘}{2^{𝑁}} & = \frac{𝑘_{1} 𝑘_{2} \dots 𝑘_{𝑛}}{2^{𝑁}} \\ = 0 . 𝑘_{1} 𝑘_{2} \dots 𝑘_{𝑁} \\ = 𝑘_{1} \cdot \frac{1}{2^{1}} + 𝑘_{2} \cdot \frac{1}{2^{2}} + \dots + 𝑘_{𝑁} \cdot \frac{1}{2^{𝑁}} \\ = \sum_{𝑙 = 1}^{𝑁} 𝑘_{𝑙} 2^{- 𝑙} \end{aligned}

显然这样改写之后，大求和号之后的部分可以重写为直积态形式：

e^{i 2 𝜋 𝑗 \cdot \sum_{𝑙 = 1}^{𝑁} 𝑘_{𝑙} 2^{- 𝑙}} | 𝑘_{1} 𝑘_{2} \dots 𝑘_{𝑁} ⟩ = ⨂_{𝑙 = 1}^{𝑁} e^{i 2 𝜋 𝑗 \cdot 𝑘_{𝑙} 2^{- 𝑙}} | 𝑘_{𝑙} ⟩

于是：

\begin{aligned} ℱ︀ {| 𝑗 ⟩} & = \frac{1}{2^{\frac{𝑁}{2}}} \sum_{𝑘 = 0}^{2^{𝑁} - 1} e^{i \frac{2 𝜋}{2^{𝑁}} 𝑗 𝑘} | 𝑘 ⟩ \\ = \frac{1}{2^{\frac{𝑁}{2}}} \sum_{𝑘_{1} = 0}^{1} \dots \sum_{𝑘_{𝑁} = 0}^{1} ⨂_{𝑙 = 1}^{𝑁} e^{i 2 𝜋 𝑗 \cdot 𝑘_{𝑙} 2^{- 𝑙}} | 𝑘_{𝑙} ⟩ \\ = \frac{1}{2^{\frac{𝑁}{2}}} ⨂_{𝑙 = 1}^{𝑁} \sum_{𝑘_{𝑙} = 0}^{1} e^{i 2 𝜋 𝑗 \cdot 𝑘_{𝑙} 2^{- 𝑙}} | 𝑘_{𝑙} ⟩ \\ = \frac{1}{2^{\frac{𝑁}{2}}} ⨂_{𝑙 = 1}^{𝑁} (| 0 ⟩ + e^{i 2 𝜋 𝑗 \cdot 2^{- 𝑙}} | 1 ⟩) \end{aligned}

再展开一次，可以更加直观：

ℱ︀ {| 𝑗 ⟩} = \frac{1}{2^{\frac{𝑁}{2}}} (| 0 ⟩ + e^{i 2 𝜋 \cdot 0 . 𝑗_{𝑁}} | 1 ⟩) (| 0 ⟩ + e^{i 2 𝜋 \cdot 0 . 𝑗_{𝑁 - 1} 𝑗_{𝑁}} | 1 ⟩) \dots (| 0 ⟩ + e^{i 2 𝜋 \cdot 0 . 𝑗_{1} 𝑗_{2} \dots 𝑗_{𝑁}} | 1 ⟩)

也就是说，在对计算基态 $| 𝑗 ⟩$ 傅里叶变换之后，第 $𝑘$ 号量子所处的量子态是：

\frac{1}{\sqrt{2}} (| 0 ⟩ + e^{i 2 𝜋 \cdot 0 . 𝑗_{𝑁 - 𝑘} \dots 𝑗_{𝑁 - 1} 𝑗_{𝑁}} | 1 ⟩)

3.构建量子线路

为了构建量子线路，我们首先引入相位矩阵 $𝑅_{𝑘}$ ：

𝑅_{𝑘} = [\begin{matrix} 1 & 0 \\ 0 & e^{i \frac{2 𝜋}{2^{𝑘}}} \end{matrix}]

这个量子门的作用是显然的，它为 $| 1 ⟩$ 附加了 $\frac{2 𝜋}{2^{𝑘}}$ 的相对相位，也就是使量子态在布洛赫球上绕 $𝑧$ 轴旋转 $\frac{2 𝜋}{2^{𝑘}}$ ，因此它是 $𝑍$ 旋转门的特殊形式： $𝑅_{𝑘} = 𝑅_{𝑍} (\frac{2 𝜋}{2^{𝑘}})$ 。

接下来开始构建线路。注意到变换后每个量子都处于均匀的叠加态(意为 $| 0 ⟩, | 1 ⟩$ 的振幅的模相等)，因此首先在 $1$ 号量子上作用一个 $𝐻$ 门使其变为叠加态。之后，注意到相位是按二进制写出的：

\begin{aligned} 2 𝜋 \cdot 0 . 𝑗_{𝑁 - 𝑘} \dots 𝑗_{𝑁 - 1} 𝑗_{𝑁} & = 2 𝜋 \cdot (\frac{𝑗_{𝑁 - 𝑘}}{2} + \frac{𝑗_{𝑁 - 𝑘 + 1}}{2^{2}} + \dots + \frac{𝑗_{𝑁}}{2^{𝑘 + 1}}) \\ = \frac{2 𝜋}{2} 𝑗_{𝑁 - 𝑘} + \frac{2 𝜋}{2^{2}} 𝑗_{𝑁 - 𝑘 + 1} + \dots + \frac{2 𝜋}{2^{𝑘 + 1}} 𝑗_{𝑁} \end{aligned}

也就是说， $𝑗_{𝑁 - 𝑘 + 𝑙}$ 表示了是否要为 $| 1 ⟩$ 附加 $\frac{2 𝜋}{2^{𝑙 + 1}}$ 的相位。这说明在线路中应当存在以 $𝑁 - 𝑘 + 𝑙$ 号量子作为控制位，控制 $𝑁 - 𝑘$ 号量子是否作用 $𝑅_{𝑙 + 1}$ 的受控量子门。对于同一个量子，作用 $𝑅_{𝑘}$ 门的顺序并不重要。并且在此之前， $𝑁 - 𝑘 + 𝑙$ 号量子不能进入叠加态，否则会在系统中产生纠缠态。由此分析，可以得到量子傅里叶变换的线路应当如图 1 所示。

图 1 量子傅里叶变换的量子电路图

当然值得注意的是，如果只考虑之前文字所述的操作，将产生的量子态是：

\frac{1}{2^{\frac{𝑁}{2}}} (| 0 ⟩ + e^{i 2 𝜋 \cdot 0 . 𝑗_{1} 𝑗_{2} \dots 𝑗_{𝑁}} | 1 ⟩) \dots (| 0 ⟩ + e^{i 2 𝜋 \cdot 0 . 𝑗_{𝑁 - 1} 𝑗_{𝑁}} | 1 ⟩) (| 0 ⟩ + e^{i 2 𝜋 \cdot 0 . 𝑗_{𝑁}} | 1 ⟩)

这个顺序与我们所期望的恰好是相反的。因此需要在线路最后，再执行一次重排以调整顺序。只需要在序号对称的两个量子位上作用 $SWAP$ 门即可。

4.量子傅里叶变换的几何意义

⁴⁴ 由于技术所限，这里只能以语言的形式表达其几何意义，敬请见谅。由前两节我们知道了在对计算基态 $| 𝑗 ⟩$ 傅里叶变换之后，第 $𝑘$ 号量子所处的量子态是：

\frac{1}{\sqrt{2}} (| 0 ⟩ + e^{i 2 𝜋 \cdot 0 . 𝑗_{𝑁 - 𝑘} \dots 𝑗_{𝑁 - 1} 𝑗_{𝑁}} | 1 ⟩)

在量子计算（三）——布洛赫球中介绍布洛赫球时还知道，单个量子的纯态可以表示为：

| 𝜓 ⟩ = cos \frac{𝜃}{2} | 0 ⟩ + e^{i 𝜑} sin \frac{𝜃}{2} | 1 ⟩

对比可知，显然单个量子在傅里叶变换后对应 $𝜃 = 90^{⚬} = 𝜋$ 的情况，也就是在球面的赤道上；而在变换之前要么是 $| 0 ⟩$ 要么是 $| 1 ⟩$ ，即北极点和南极点，因此量子傅里叶变换显然是将计算基态由南北极点的交错表示变换为了赤道上的频率表示。

何谓南北极点的交错表示？举个三量子的简单例子，对于计算基态 $| 010 ⟩$ 来说，各量子在布洛赫球面上的排列是 [北极,南极,北极] ，对于其它计算基态也是类似地按二进制数指向南北极点，这便是南北极点的交错表示。

而赤道上的频率表示又是如何？在上节也已提到过，变换后的量子具有的相对相位是：

2 𝜋 \cdot 0 . 𝑗_{𝑁 - 𝑘} \dots 𝑗_{𝑁 - 1} 𝑗_{𝑁} = \frac{2 𝜋}{2} 𝑗_{𝑁 - 𝑘} + \frac{2 𝜋}{2^{2}} 𝑗_{𝑁 - 𝑘 + 1} + \dots + \frac{2 𝜋}{2^{𝑘 + 1}} 𝑗_{𝑁}

因此对于计算基态 $| 010 ⟩$ ， $1$ 号量子在变换后具有相对相位：

\frac{2 𝜋}{2} \cdot 0 + \frac{2 𝜋}{2^{2}} \cdot 1 + \frac{2 𝜋}{2^{3}} \cdot 0 = \frac{𝜋}{2}

$2, 3$ 号则分别是：

\frac{2 𝜋}{2} \cdot 1 + \frac{2 𝜋}{2^{2}} \cdot 0 = 𝜋 \frac{2 𝜋}{2} \cdot 0 = 0

因此，对于三位量子态，每变化到下一计算基态，那么变换后的 $𝑖$ 号量子的相对相位将会增加 $\frac{2 𝜋}{2^{3 - 𝑖 + 1}}$ ，这反映了变化的幅度，也反映了每个位的频率。对于 $𝑛$ 位量子态也是类似地，序号越小，每次增加的相位越小。这就是所谓赤道上的频率表示。

三、相位反冲(Phase Kick-back)

在量子计算（五）——Deutsch-Jozsa算法与Simon算法中介绍的算法都利用了相位反冲。但相位反冲的产生条件与原理究竟是什么？接下来我们讨论这个问题。

1.量子门的相位

量子门作为矩阵，自然是具有特征值与特征向量的。由于量子门是酉矩阵，它显然不会改变向量的模长——因此其本征值(特征值)必然具有形式 $e^{i 2 𝜋 𝜃}$ 。从而对于量子门 $𝑈$ ，必然存在本征态(特征向量) $| 𝜓 ⟩$ 使得：

𝑈 | 𝜓 ⟩ = e^{i 2 𝜋 𝜃} | 𝜓 ⟩

这意味着对于本征态，量子门仅仅是为其附加了一个全局相位。对于现实世界的观测者而言，这多出的全局相位显然是不重要的。

2.相位反冲的原理

但是，如果这个量子门 $𝑈$ 是作为受控门呢？以最普通的受控 $𝑈$ 门为例，不妨首先构造这个受控矩阵 $C 𝑈$ 。既然当控制位为 $0$ 时 $𝑈$ 不作用，反之为 $1$ 时作用，因此：

\begin{aligned} C 𝑈 & = (| 0 ⟩ ⟨ 0 | \otimes 𝐼) + (| 1 ⟩ ⟨ 1 | \otimes 𝑈) \\ = [\begin{matrix} 𝐼 & 𝑂 \\ 𝑂 & 𝑈 \end{matrix}] \end{aligned}

那么，假设控制位处于量子态 $| 𝜑 ⟩ = 𝛼 | 0 ⟩ + 𝛽 | 1 ⟩$ 而受控位恰为 $𝑈$ 的本征态 $| 𝜓 ⟩$ 。经过 $C 𝑈$ 作用之后：

\begin{aligned} C 𝑈 (| 𝜑 ⟩ | 𝜓 ⟩) & = (| 0 ⟩ ⟨ 0 | \otimes 𝐼) (| 𝜑 ⟩ | 𝜓 ⟩) + (| 1 ⟩ ⟨ 1 | \otimes 𝑈) (| 𝜑 ⟩ | 𝜓 ⟩) \\ = | 0 ⟩ ⟨ 0 | 𝜑 ⟩ \otimes | 𝜓 ⟩ + | 1 ⟩ ⟨ 1 | 𝜑 ⟩ \otimes 𝑈 | 𝜓 ⟩ \\ = 𝛼 | 0 ⟩ | 𝜓 ⟩ + e^{i 2 𝜋 𝜃} 𝛽 | 1 ⟩ | 𝜓 ⟩ \\ = (𝛼 | 0 ⟩ + e^{i 2 𝜋 𝜃} 𝛽 | 1 ⟩) | 𝜓 ⟩ \end{aligned}

可以发现，本应由受控位独占的全局相位，却被控制位吸收为局部相位；而应当改变的受控位反而没有发生变化。 ⁵⁵ 笔者个人的理解是：对于控制位而言，其包含的 $| 0 ⟩$ 态与 $| 1 ⟩$ 态并不是平权的。例如，当控制位为 $1$ 时，那么在作用之后恰好是 $e^{i 2 𝜋 𝜃} 𝛽 | 1 ⟩ | 𝜓 ⟩$ ，此时引入了全局相位；而控制位为 $0$ 时，则不会引入相位改变。于是由于叠加态原理，控制位的两个计算基态间的相位差发生改变，也就导致了相对相位的产生或改变。

现在让我们考虑当受控位不是本征态的情况。由于 $𝑈$ 是酉矩阵，其各本征态自然是正交的，因此任意(等量子位数的)量子态 $| 𝜙 ⟩$ 都可以表示为其本征态之线性和：

| 𝜙 ⟩ = \sum 𝑤_{𝑘} | 𝜓_{𝑘} ⟩

从前述可知，要知道相位改变多少，只需要计算当控制位为 $1$ 时的结果：

\begin{aligned} (| 1 ⟩ ⟨ 1 | \otimes 𝑈) (| 1 ⟩ | 𝜙 ⟩) & = | 1 ⟩ \otimes 𝑈 | 𝜙 ⟩ \\ = | 1 ⟩ \otimes \sum 𝑤_{𝑘} e^{i 2 𝜋 𝜃_{𝑘}} | 𝜓_{𝑘} ⟩ \\ = \sum 𝑤_{𝑘} e^{i 2 𝜋 𝜃_{𝑘}} | 1 ⟩ | 𝜓_{𝑘} ⟩ \end{aligned}

从而：

\begin{aligned} C 𝑈 (| 𝜑 ⟩ | 𝜓 ⟩) & = 𝛼 \sum 𝑤_{𝑘} | 0 ⟩ | 𝜓_{𝑘} ⟩ + 𝛽 \sum 𝑤_{𝑘} e^{i 2 𝜋 𝜃_{𝑘}} | 1 ⟩ | 𝜓_{𝑘} ⟩ \\ = \sum 𝑤_{𝑘} (𝛼 | 0 ⟩ + e^{i 2 𝜋 𝜃_{𝑘}} 𝛽 | 1 ⟩) | 𝜓_{𝑘} ⟩ \end{aligned}

可见， $| 𝜑 ⟩$ 将会以概率 ${| 𝑤_{𝑘} |}^{2}$ 获得相对相位 $2 𝜋 𝜃_{𝑘}$ 。

四、相位估计

1.算法思路

在现实世界中，量子门往往仅是个黑箱——这意味着我们并不知道这个量子门的具体形式，也就更不必提求出它的本征值了。而相位估计就是为了解决这个问题。

显然对于本征态来说，无论是否利用相位反冲，量子门 $𝑈$ 都只能引入一个对观测概率不产生影响的相位，因此这对我们估计量子门的本征值没有任何作用。但是注意到：我们之前介绍的量子傅里叶变换，就是让计算基态进入具有相对相位的叠加态；而量子电路可逆，相反地也自然能将相对相位转换为计算基态——而计算基态被测量到的概率就是 $100 %$ ！这就给了我们相位估计的思路：只要利用相位反冲，让相位作用到控制位上，最后让控制位逆傅里叶变换一次即可。

2.线路构建

为了分析简便，取受控位为 $𝑈$ 的本征态 $| 𝜓 ⟩$ 。在相位反冲之前，我们要让控制位都进入叠加态——否则要么不引入相位、要么引入全局相位。为此首先让控制位从初始零态做一次量子傅里叶变换，如图 2 所示。 ⁶⁶ 值得注意的是，对 $| 0^{𝑛} ⟩$ 做 QFT 与在每个量子位上作用 $𝐻$ 门的效果是等价的。因为此时受控 $𝑅_{𝑘}$ 门均不起作用，可以直接从量子傅里叶变换的线路图中删去。此时控制位进入均匀叠加态。

现在考虑如何使 $𝑈$ 的相位反冲到控制位上。我们再次将本征值 $e^{i 2 𝜋 𝜃}$ 中的 $𝜃$ 也写为二进制小数形式：

𝜃 = 0 . 𝜃_{1} 𝜃_{2} \dots 𝜃_{𝑛 - 1} 𝜃_{𝑛} \dots

因此 $𝑈^{2}$ 的本征值就会是 ${(e^{i 2 𝜋 𝜃})}^{2} = e^{i 2 𝜋 2 𝜃} = e^{i 2 𝜋 0 . 𝜃_{2} 𝜃_{3} \dots 𝜃_{𝑛 - 1} 𝜃_{𝑛} \dots}$ ，同理 $𝑈^{2^{𝑘}}$ 中的 $𝜃$ 值为 $0 . 𝜃_{𝑘} 𝜃_{𝑘 + 1} \dots$ 。这样我们就构造出与量子傅里叶变换中各量子位相对相位相似的排列了。因此这个量子线路将如下构造：

图 3 相位估计的量子电路图

当然，我们应该更喜欢下面这种简便的画法：

3.误差与概率分析

看到这里，您可能会惊叹于相位估计对量子傅里叶变换的巧妙运用。但有必要提醒您重新仔细阅读“由二进制本征值构造量子线路”这一部分。我们给出的线路图是可以正常正确运行的，但却刻意忽略了一个细节——图中相位反冲之后的相位是被高位截断了的！而在之前将 $𝜃$ 写为 $0 . 𝜃_{1} \dots 𝜃_{𝑛} \dots$ 时后面还有省略号。

这意味着相位测量算法是存在精确性问题的。如果 $𝜃$ 在二进制表示下是有穷的，那么使用足够多的量子确实可以精准得到其数值；但显然还有很多二进制无穷的 $𝜃$ 只能得到近似值。而这尚未穷尽的相位输入到逆傅里叶变换后会带来不确定性。现在我们的问题是：在无穷的情况下，测量得到的 $\tilde{𝜃}$ 与真实的 $𝜃$ 之间有多少误差？在给定误差限的情况下，测量结果又能以多大概率落在误差限内？

记 $𝑗 = ⌊ 2^{𝑛} 𝜃 ⌋$ ，因为在有截断的情况下 $2^{𝑛} 𝜃$ 依然是小数， $𝑗$ 才是真正测量的结果。考虑控制位在相位反冲后、逆傅里叶变换前的状态是：

\frac{1}{2^{\frac{𝑛}{2}}} \sum_{𝑘 = 0}^{2^{𝑛} - 1} e^{i 2 𝜋 𝑘 𝜃} | 𝑘 ⟩

所以在逆傅里叶变换之后的状态是：

\begin{aligned} \frac{1}{2^{𝑁}} [\begin{matrix} 1 & 1 & 1 & \dots & 1 \\ 1 & 𝜔^{- 1} & 𝜔^{- 2} & \dots & 𝜔^{- (2^{𝑁} - 1)} \\ 1 & 𝜔^{- 2} & 𝜔^{- 4} & \dots & 𝜔^{- 2 (2^{𝑁} - 1)} \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ 1 & 𝜔^{- (2^{𝑁} - 1)} & 𝜔^{- 2 (2^{𝑁} - 1)} & \dots & 𝜔^{- {(2^{𝑁} - 1)}^{2}} \end{matrix}] [\begin{matrix} e^{i 2 𝜋 \cdot 0 𝜃} \\ e^{i 2 𝜋 \cdot 1 𝜃} \\ e^{i 2 𝜋 \cdot 2 𝜃} \\ ⋮ \\ e^{i 2 𝜋 \cdot (2^{𝑁} - 1) 𝜃} \end{matrix}] \\ = \frac{1}{2^{𝑁}} [\sum_{𝑘 = 0}^{2^{𝑁} - 1} e^{i 2 𝜋 𝑘 𝜃}, \sum_{𝑘 = 0}^{2^{𝑁} - 1} 𝜔^{- 𝑘} e^{i 2 𝜋 𝑘 𝜃}, \sum_{𝑘 = 0}^{2^{𝑁} - 1} 𝜔^{- 2 𝑘} e^{i 2 𝜋 𝑘 𝜃}, \dots, \sum_{𝑘 = 0}^{2^{𝑁} - 1} 𝜔^{- (2^{𝑁} - 1) 𝑘} e^{i 2 𝜋 𝑘 𝜃}] \\ = \frac{1}{2^{𝑁}} \sum_{𝑘 = 0}^{2^{𝑁} - 1} \sum_{𝑗 = 0}^{2^{𝑁} - 1} 𝜔^{- 𝑗 𝑘} e^{i 2 𝜋 𝑘 𝜃} | 𝑗 ⟩ \\ = \frac{1}{2^{𝑁}} \sum_{𝑘 = 0}^{2^{𝑁} - 1} \sum_{𝑗 = 0}^{2^{𝑁} - 1} e^{i 2 𝜋 (𝑘 𝜃 - \frac{𝑘 𝑗}{2^{𝑁}})} | 𝑗 ⟩ \\ = \sum_{𝑗 = 0}^{2^{𝑁} - 1} (\frac{1}{2^{𝑁}} \sum_{𝑘 = 0}^{2^{𝑁} - 1} e^{i 2 𝜋 𝑘 (𝜃 - \frac{𝑗}{2^{𝑁}})}) | 𝑗 ⟩ \end{aligned}

注 1.（量子傅里叶逆变换）

但这是为什么呢？虽然之前并未说明过量子傅里叶逆变换如何计算，但是注意到量子傅里叶变换本身可以用矩阵形式写出：

\begin{aligned} ℱ︀ {| 𝑗 ⟩} & = \frac{1}{2^{\frac{𝑁}{2}}} \sum_{𝑘 = 0}^{2^{𝑁} - 1} e^{i \frac{2 𝜋}{2^{𝑁}} 𝑗 𝑘} | 𝑘 ⟩ \\ = \frac{1}{2^{\frac{𝑁}{2}}} [\begin{matrix} 1 & 1 & 1 & \dots & 1 \\ 1 & 𝜔 & 𝜔^{2} & \dots & 𝜔^{2^{𝑁} - 1} \\ 1 & 𝜔^{2} & 𝜔^{4} & \dots & 𝜔^{2 (2^{𝑁} - 1)} \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ 1 & 𝜔^{2^{𝑁} - 1} & 𝜔^{2 (2^{𝑁} - 1)} & \dots & 𝜔^{{(2^{𝑁} - 1)}^{2}} \end{matrix}] | 𝑗 ⟩ \end{aligned}

其中

𝜔 = e^{i \frac{2 𝜋}{2^{𝑁}}}

。不妨将其中的矩阵也记为

ℱ︀

。这一方面是一个范德蒙矩阵，但另一方面——既然它对应量子傅里叶变换的整体量子门，那么它就是一个酉矩阵。因此要计算量子傅里叶逆变换，只要计算

{ℱ︀}^{- 1} = {ℱ︀}^{†}

，也就是

ℱ︀

的转置共轭即可！

因此测量结果为 $| 𝑗 ⟩$ 的概率就是：

\begin{aligned} 𝑃 (𝑗) & = {| \frac{1}{2^{𝑁}} \sum_{𝑘 = 0}^{2^{𝑁} - 1} e^{i 2 𝜋 𝑘 (𝜃 - \frac{𝑗}{2^{𝑁}})} |}^{2} \\ * Using geometric sequence summation * \\ = \frac{1}{2^{2 𝑁}} {| \frac{e^{i 2 𝜋 (2^{𝑁} 𝜃 - 𝑗)} - 1}{e^{i 2 𝜋 (𝜃 - \frac{𝑗}{2^{𝑁}})} - 1} |}^{2} \end{aligned}

我们记误差 $𝜖 = | 𝜃 - \frac{𝑗}{2^{𝑁}} |$ 。显然误差具有最小值 $\frac{1}{2^{𝑁 + 1}}$ 。在最好的情况下， $𝑗$ 应当是二进制 $𝜃$ 的前 $𝑛$ 位(四舍五入后)，测量得到的概率自然也是最小的，此时 $𝜖$ 的最大值是 $\frac{1}{2^{𝑁}}$ 。为了得到这个概率的下界，自然应取 $𝜖 = \frac{1}{2^{𝑁 + 1}}$ ，首先求分子：

| e^{i 2 𝜋 (2^{𝑁} 𝜃 - 𝑗)} - 1 | = | e^{i 2 𝜋 2^{𝑁} 𝜖} - 1 | = 2

⁷⁷ 对于 $| e^{i 2 𝜃} - 1 |$ ，显然可以将其视作单位圆之实轴右交点与圆上一点所连的弦长，此点与实轴之张角为 $2 𝜃$ 。于是弦长可以简单写为 $2 sin 𝜃$ 。在上面的例子中， $𝜃 = 𝜋 \cdot 2^{𝑁} 𝜖 = \frac{𝜋}{2}$ ，于是弦长为 $2$ 。同理分母为：

| e^{i 2 𝜋 (𝜃 - \frac{𝑗}{2^{𝑁}})} - 1 | = | e^{i 2 𝜋 𝜖} - 1 | = 2 sin \frac{𝜋}{2^{𝑁 + 1}} \approx \frac{2 𝜋}{2^{𝑁 + 1}} = \frac{𝜋}{2^{𝑁}}

所以 $𝑃 (𝑗) = \frac{1}{2^{2 𝑁}} \cdot {(\frac{2}{\frac{𝜋}{2^{𝑁}}})}^{2} = \frac{4}{𝜋^{2}} = 40.53 %$ 。这说明至少有四成的概率测量到最好的结果。也许您会觉得这个概率小得可怜，但这是因为我们只考虑了一个方向的误差，也就是只让结果比期望的小。如果允许测量值在期望值的两侧取值，那么概率就上升到至少八成。

如果允许更大的误差，那么测量值在误差限内的概率将会更大。例如如果允许 $𝑘$ 倍的最小误差，那么测量结果在允许范围内的概率就至少是 $1 - \frac{1}{2 (𝑘 - 1)}$ 。

4.问题重顾——当受控位不是本征态

在这里，希望读者再重新阅读本节 “1.算法思路” 中的第一句话：

提示

在现实世界中，量子门往往仅是个黑箱——这意味着我们并不知道这个量子门的具体形式，也就更不必提求出它的本征值了。

在上面的分析中，我们已提前让受控位进入 $𝑈$ 的本征态。但是，既然我们不知道量子门的具体形式，又怎么可能提前制备本征态呢？这里就需要回到之前已分析过的了。当受控位处于本征态的叠加态时：

C 𝑈 (| 𝜑 ⟩ | 𝜓 ⟩) = \sum 𝑤_{𝑘} (𝛼 | 0 ⟩ + e^{i 2 𝜋 𝜃_{𝑘}} 𝛽 | 1 ⟩) | 𝜓_{𝑘} ⟩

这意味着即便是任意态，利用相位反冲也能将本征值的相位作用到控制位上；并且， $𝜃_{𝑘}$ 与 $| 𝜓_{𝑘} ⟩$ 是绑定的，只要测量受控位得到 $| 𝜓_{𝑘} ⟩$ ，那么算法能得到的也将会是 $𝜃_{𝑘}$ 。

另一方面，由于叠加态性质，经过量子逆傅里叶变换之后，控制位会保留各本征值对应的振幅。因此最后测量控制位时，会以 ${| 𝑤_{𝑘} |}^{2}$ 的概率得到 $𝜃_{𝑘}$ 对应的信息。

综上所述，相位估计是一个有效的算法，不因无法制备本征态而无法运行，而能测量到的 $𝜃_{𝑘}$ 则取决于控制位所使用的位数。量子傅里叶变换也将会是后续许多算法的基础。