.ipynb .pdf

repository open issue

文档目录

5.2 相位估计

练习 5.7

练习 5.7

通过证明图 5.2 中那样的受控 \(U\) 运算会将状态 \(|j\rangle |u\rangle\) 转换为 \(|j\rangle U^j |u\rangle\)，从而对图 5.2 线路可以有更为深刻的认识。现在就证明这一点 (注意这并不依赖于 \(|u\rangle\) 是 \(U\) 的本征态)。

这里需要补充的是，这里的 \(|j\rangle\) 必须是可以由二进制数储存的态，或者说是 \(n\) 量子比特计算基的其中一个态；即 \(|j_1 j_2 \cdots j_n\rangle\)，其中 \(j_1, j_2, \cdots, j_n \in \{0, 1\}\)。同时，我们不考察图 5.2 中的 Hadamard 门：

首先，由于 \(|j\rangle\) 是计算基的态，因此经过控制节点后，仍然保持其结果而不更改相位。

对于 \(|u\rangle\) 线路上的作用，以 \(|j_1\rangle\) 为例，若 \(|j_1\rangle = |1\rangle\)，则作用 \(U^{2^n} = U^{j_1 2^n}\)；若 \(|j_1\rangle = |0\rangle\)，则作用 \(I = U^{j_1 2^n}\)。因此，无论如何都可以表示为 \(U^{j_1 2^n}\) 的作用。其它控制门路同理，因此我们得到

\[\begin{split} \begin{align*} |u\rangle &\rightarrow U^{j_1 2^n} U^{j_2 2^{n-1}} \cdots U^{j_{n-1} 2^1} U^{j_n 2^0} |u\rangle \\ &= U^{j_1 2^n + j_2 2^{n-1} + j_{n-1} 2^1 + j_n 2^0} |u\rangle = U^j |u\rangle \end{align*} \end{split}\]

练习 5.8

练习 5.8

设相位估计算法把状态 \(|0\rangle |u\rangle\) 变为状态 \(|\tilde \varphi_u\rangle |u\rangle\)，那么若给定输入 \(|0\rangle \left( \sum_u c_u |u\rangle \right)\) 时，算法的输出为 \(\sum_u c_u |\tilde \varphi_u\rangle |u\rangle\)。证明如果 \(t\) 按照式 (5.35) 选择，则在相位估计算法后精确到 \(n\) 比特测量 \(\varphi_u\) 的概率，至少是 \(|c_u|^2 (1-\varepsilon)\)。

这个问题看上去很显然；由于测得 \(\varphi_u\) 意味着对应到本征态 \(|u\rangle\)，而这个本征态的出现概率就是 \(|c_u|^2\)；因此与测量概率准度 \((1-\varepsilon)\) 相乘，立即得到了 \(|c_u|^2 (1-\varepsilon)\)。当然，这个概率显然还是得要比 \(|c_u|^2\) 要小的。

---

书上说要有“严格化”(rigorous) 的论证；但我确实觉得，有这样一个直觉已经很充分了。

只是题目假定了相位估计过程，包括第一阶段的本征相位寄存、第二阶段的逆向 Fourier 过程，都是是线性的；但这个结论不一定很显然。我们在此作简要的证明。

补充约定

题目中的 \(|0\rangle |u\rangle\) 记号是容易产生误导的。由于我们关心的是算符 \(U\) 的本征态，因此这里的 \(|u\rangle\) 需要在维度上与 \(U\) 所作用的空间相同。\(|0\rangle\) 其实是 \(t\) 个第一寄存器的控制比特态 \(|00\cdots0\rangle\)，只是用以表征二进制数值 \(0\times 2^0 + 0 \times 2^1 + \cdots + 0 \times 2^t = 0\) 而已。

我们同时约定，以后记号中出现的 \(|u\rangle\) 是任意的 \(U\) 本征态，\(|\mathscr{u}\rangle\) 是其中我们关心的本征态。

线性叠加态的相位估计第一阶段

首先我们考察相位估计第一阶段。回顾到对于单一的本征态 \(|u\rangle\) 而言，其本征值是 \(e^{2 \pi i \varphi_u}\)，那么该过程下，第一寄存器的 \(t\) 个量子比特状态为

\[ |00\cdots0\rangle |u\rangle \rightarrow \frac{1}{2^{t/2}} \bigotimes_{j=1}^t \big( |0\rangle + e^{2 \pi i 2^{t-j} \varphi_u} |1\rangle \big) |u\rangle = \frac{1}{2^{t/2}} \sum_{k=0}^{2^t-1} e^{2 \pi i \varphi_u k} |k\rangle |u\rangle \tag{5.20} \]

现在我们考察第二寄存器代入的是线性组合态 \(\sum_{u} c_u |u\rangle\)。首先引入一个引理。这里需要假设 \(U\) 是线性算符 (量子门路一般都有该要求)；并且利用到本征态 \(|u\rangle\) 和本征值 \(e^{2 \pi i \varphi_u}\) 因此，

\[\begin{split} \begin{align*} U^{m} \sum_u c_u |u\rangle &= U^{m-1} \sum_u c_u U |u\rangle = U^{m-1} \sum_u c_u e^{2 \pi i \varphi_u} |u\rangle \\ &= U^{m-2} \sum_u c_u e^{2 \pi i \varphi_u} U |u\rangle = U^{m-1} \sum_u c_u e^{2 \pi i \varphi_u \times 2} |u\rangle \\ &= \cdots = \sum_u c_u e^{2 \pi i \varphi_u m} |u\rangle \end{align*} \end{split}\]

现在我们考虑第一次控制过程，即在第 \(t\) 个量子比特 \(|0\rangle\) 上引入 Hadamard 门后施加 \(\text{ctrl-}U\) 门：

\[\begin{split} \begin{alignat*}{10} \underbrace{|00\cdots0\rangle}_{t-1} |0\rangle \sum_u c_u |u\rangle \; && \xrightarrow{H \text{ Gate at Qubit } t} \; & \frac{1}{\sqrt{2}} \underbrace{|00\cdots0\rangle}_{t-1} \left( |0\rangle \sum_u c_u |u\rangle + |1\rangle \sum_u c_u |u\rangle \right) \\ && \xrightarrow{\text{Qubit } t \text{ ctrl-}U} \; & \frac{1}{\sqrt{2}} \underbrace{|00\cdots0\rangle}_{t-1} \left( |0\rangle \sum_u c_u |u\rangle + |1\rangle U \sum_u c_u |u\rangle \right) \\ && =\; & \frac{1}{\sqrt{2}} \underbrace{|00\cdots0\rangle}_{t-1} \left( |0\rangle \sum_u c_u |u\rangle + |1\rangle \sum_u c_u e^{2 \pi i \varphi_u 2^0} |u\rangle \right) \\ && =\; & \frac{1}{\sqrt{2}} \underbrace{|00\cdots0\rangle}_{t-1} \sum_u c_u \left( |0\rangle + e^{2 \pi i \varphi_u 2^0} |1\rangle \right) |u\rangle \end{alignat*} \end{split}\]

沿用上面的结果，再考虑第二次控制过程，即在第 \(t-1\) 个量子比特 \(|0\rangle\) 上引入 Hadamard 门后施加 \(\text{ctrl-}U^2\) 门：

\[\begin{split} \begin{alignat*}{10} && \xrightarrow{H \text{ Gate at Qubit } t-1} \; & \frac{1}{\left(\sqrt{2}\right)^2} \underbrace{|00\cdots0\rangle}_{t-2} \big( |0\rangle + |1\rangle \big) \sum_u c_u \left( |0\rangle + e^{2 \pi i \varphi_u 2^0} |1\rangle \right) |u\rangle \\ && \xrightarrow{\text{Qubit } t \text{ ctrl-}U^2} \; & \frac{1}{\left(\sqrt{2}\right)^2} \underbrace{|00\cdots0\rangle}_{t-2} \left( |0\rangle \sum_u c_u \left( |0\rangle + e^{2 \pi i \varphi_u 2^0} |1\rangle \right) |u\rangle + |1\rangle \sum_u c_u \left( |0\rangle + e^{2 \pi i \varphi_u 2^0} |1\rangle \right) U^2 |u\rangle \right) \\ && =\; & \frac{1}{\left(\sqrt{2}\right)^2} \underbrace{|00\cdots0\rangle}_{t-2} \sum_u c_u \left( |0\rangle + e^{2 \pi i \varphi_u 2^1} |1\rangle \right) \left( |0\rangle + e^{2 \pi i \varphi_u 2^0} |1\rangle \right) |u\rangle \end{alignat*} \end{split}\]

如此往复，可以得到第一阶段后，状态会成为

\[ \underbrace{|00\cdots0\rangle}_{t} \sum_u c_u |u\rangle \xrightarrow{\text{First Stage}} \frac{1}{2^{t/2}} \sum_u c_u \bigotimes_{j=1}^t \left( |0\rangle + e^{2 \pi i 2^{t-j} \varphi_u} |1\rangle \right) |u\rangle \]

因此，可以表明相位估计的第一阶段操作是线性的。

线性叠加态的相位估计第二阶段

第二阶段是逆 Fourier 变换；它与 Fourier 变换相似，都是线性操作。这里不再证明了。

关于测量

我认为，对于混合态的测量，不应该会发生“跨态”测量。这是能保证测量 \(t\) 量子比特态 \(\sum_u c_u |\tilde \varphi_u \rangle |u\rangle\) 的全部第一寄存器比特时，它必然坍缩到其中一个 \(|\tilde \varphi_\mathscr{u} \rangle\) 上；而非可能测得一部分在 \(|\tilde \varphi_\mathscr{u} \rangle\)，另一部分在 \(|\tilde \varphi_u \rangle \neq |\tilde \varphi_\mathscr{u} \rangle\) 上。因此，测量得到态 \(|\tilde \varphi_\mathscr{u} \rangle\) 所给出的概率确实就会是其线性组合系数的模 \(|c_\mathscr{u}|^2\)。当然这要基于 \(U\) 的本征态非简并的前提。

举例而言，在测量 Bell 态 \(\frac{1}{\sqrt{2}} (|00\rangle + |11\rangle)\) 的两个量子比特时，不可能测得第一个比特为 \(|0\rangle\)，而第二个比特为 \(|1\rangle\)。

练习 5.9

练习 5.9

令 \(U\) 是一个特征值为 \(\pm 1\) 的酉变换，作用在一个状态 \(|\psi\rangle\) 上。利用相位估计过程，构造一个量子线路，使得 \(|\psi\rangle\) 坍缩到 \(U\) 的两个本征态之一，并给出最终状态在哪个空间的一个经典指示器。与练习 4.34 的结果进行比较。

实际上练习 4.34 的线路就是我们所需要的线路。

相位估计过程等价于练习 4.34 的结果：

• 第一阶段使用 Hadamard 门与受控 \(U\) 门，这与练习 4.34 完全一致；

• 第二阶段是逆向 Fourier 变换；对于单比特的 Fourier 变换，其需要的门路是 \(H\)，那么逆向 Fourier 的门路是 \(H^\dagger = H\)，恰好与练习 4.34 一致。

上一页

5.1 量子 Fourier 变换

下一页

5.3 应用：求阶和因子问题