6.1 量子搜索算法
练习 6.1
练习 6.1
证明对应于 Grover 迭代中，相移的酉算符是 \(2 |0\rangle \langle0| - I\)。
这是比较显然的。一种理解方式是矩阵表示。另一种则是将该相移算符作用于具体的态 (下式的 \(x > 0\))：
\[\begin{split}
\begin{align*}
(2 |0\rangle \langle0| - I) |0\rangle &= 2 |0\rangle \langle0|0\rangle - |0\rangle = |0\rangle \\
(2 |0\rangle \langle0| - I) |x\rangle &= 2 |0\rangle \langle0|x\rangle - |x\rangle = - |x\rangle
\end{align*}
\end{split}\]
练习 6.2
练习 6.2
证明应用运算 \((2 |\psi\rangle\langle\psi| - I)\) 到一般状态 \(\sum_k \alpha_k |k\rangle\) 产生
\[
\sum_k \big( - \alpha_k + 2 \langle \alpha \rangle \big) |k\rangle
\]
其中 \(\langle \alpha \rangle = \sum_k \alpha_k / N\) 是 \(\alpha_k\) 的均值，因此，\((2 |\psi\rangle\langle\psi| - I)\) 有时称为关于均值的反演 (inversion about mean) 运算。
首先我们回顾到均衡叠加态的定义
\[
|\psi\rangle = \frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} |x\rangle
\]
因此，其外积为
\[
|\psi\rangle\langle\psi| = \frac{1}{N} \sum_{x=0}^{N-1} \sum_{y=0}^{N-1} | x \rangle \langle y |
\]
随后，我们指出题目中的 \(\sum_k \alpha_k |k\rangle\) 严格来说是 \(\sum_{k=0}^{N-1} \alpha_k |k\rangle\)，即 \(k\) 并非任意角标。因此，
\[\begin{split}
\begin{align*}
|\psi\rangle\langle\psi| \sum_{k=0}^{N-1} \alpha_k |k\rangle &= \frac{1}{N} \sum_{x=0}^{N-1} \sum_{y=0}^{N-1} \sum_{k=0}^{N-1} \alpha_k | x \rangle \langle y | k\rangle \\
&= \frac{1}{N} \sum_{x=0}^{N-1} \sum_{y=0}^{N-1} \sum_{k=0}^{N-1} \alpha_k | x \rangle \delta_{yk} = \frac{1}{N} \sum_{x=0}^{N-1} \sum_{k=0}^{N-1} \alpha_k | x \rangle \\
&= \frac{\sum_{k=0}^{N-1} \alpha_k}{N} \sum_{x=0}^{N-1} | x \rangle = \langle \alpha \rangle \sum_{x=0}^{N-1} | x \rangle = \langle \alpha \rangle \sum_{k=0}^{N-1} | k \rangle
\end{align*}
\end{split}\]
最后一个等号仅仅是角标的替换而已。随即，
\[
\big( 2 |\psi\rangle\langle\psi| - I \big) = 2 \langle \alpha \rangle \sum_{k=0}^{N-1} | k \rangle - \sum_{k=0}^{N-1} | k \rangle
= \sum_{k=0}^{N-1} \big( - \alpha_k + 2 \langle \alpha \rangle \big) |k\rangle
\]
练习 6.3
练习 6.3
证明 \(|\alpha\rangle, |\beta\rangle\) 基中，可以把 Grover 迭代写成
\[\begin{split}
G = \begin{bmatrix} \cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \end{bmatrix}
\end{split}\]
其中 \(\theta\) 是一个 \(0\) 到 \(2 \pi\) 之间的实数 (为简单起见，假定 \(M \leqslant N/2\)，这个限制很快会取消)，它满足
\[
\sin\theta = \frac{2 \sqrt{M (N-M)}}{N}
\]
首先，我们很容易表明题目中所给的 \(\theta\) 与正文的定义相同。我们回顾到正文中定义
\[
|\psi\rangle = \sqrt{\frac{N-M}{N}} |\alpha\rangle + \sqrt{\frac{M}{N}} |\beta\rangle = \cos \frac{\theta}{2} |\alpha\rangle + \sin \frac{\theta}{2} |\beta\rangle
\]
因此，
\[
\sin \theta = 2 \cos \frac{\theta}{2} \sin \frac{\theta}{2} = 2 \sqrt{\frac{N-M}{N}} \sqrt{\frac{M}{N}} = \frac{2 \sqrt{M (N-M)}}{N}
\]
随后我们利用矩阵下的表示来作说明。首先，\(|\psi\rangle\) 在基 \(\{ |\alpha\rangle, |\beta\rangle \}\) 下的表示向量是
\[\begin{split}
|\psi\rangle = \begin{bmatrix} \cos \frac{\theta}{2} \\ \sin \frac{\theta}{2} \end{bmatrix}
\end{split}\]
那么其外积是
\[\begin{split}
|\psi\rangle \langle\psi|
= \begin{bmatrix} \cos^2 \frac{\theta}{2} & \sin \frac{\theta}{2} \cos \frac{\theta}{2} \\ \sin \frac{\theta}{2} \cos \frac{\theta}{2} & \sin^2 \frac{\theta}{2} \end{bmatrix}
= \frac{1}{2} \begin{bmatrix} \cos \theta + 1 & \sin \theta \\ \sin \theta & 1 - \cos \theta \end{bmatrix}
\end{split}\]
而依据运算 \(O\) 的定义
\[
O(a |\alpha\rangle + b |\beta\rangle) = a |\alpha\rangle - b |\beta\rangle
\]
我们知道其矩阵表示类似于 \(Z\) 算符：
\[\begin{split}
O = \begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix}
\end{split}\]
因此，
\[\begin{split}
G = (2 |\psi\rangle \langle\psi| - I) O = \begin{bmatrix} \cos \theta & \sin \theta \\ \sin \theta & - \cos \theta \end{bmatrix} \begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix} = \begin{bmatrix} \cos \theta & - \sin \theta \\ \sin \theta & \cos \theta \end{bmatrix}
\end{split}\]
这道题的直观思路显然是书中的图 6.3。它将 \(|\psi\rangle\) 逆时针旋转了 \(\theta\) 角度。这种旋转效应确实可以写为待证的 \(\begin{bmatrix} \cos \theta & - \sin \theta \\ \sin \theta & \cos \theta \end{bmatrix}\) 矩阵。但需要指出，这道题的证明应当对任何向量都要有效，而不只是均衡叠加态 \(|\psi\rangle\) 有效。
练习 6.4
练习 6.4
像上面那样，对多解情况 (\(1 < M < N/2\))，给出量子搜索算法的具体步骤。
我认为唯一的区别在于应用 Grover 迭代的次数 \(R\)。这在式 (6.17) 中有阐述：
\[
R \leqslant \left\lceil \frac{\pi}{4} \sqrt{\frac{N}{M}} \right\rceil
\]
练习 6.5
练习 6.5
证明用一次 \(O\) 调用，基本量子门和附加的量子比特 \(|q\rangle\) 可以构造增广的 oracle \(O'\)。
该问题的解答参考下述网页：
https://serab.net/docs/qcqi/chapter6/
构造下述量子线路：
首先，如果 \(|q\rangle\) 是 \(|0\rangle\)，那么总的量子线路的作用相当于
\[
|0\rangle |x\rangle \frac{|0\rangle - |1\rangle}{\sqrt{2}} \xrightarrow{\text{orcale}} |0\rangle (-1)^{f(x)} |x\rangle \frac{|0\rangle - |1\rangle}{\sqrt{2}} = (-1)^{f(x)} |0\rangle |x\rangle \frac{|0\rangle - |1\rangle}{\sqrt{2}}
\]
因此，对于 \(|q\rangle\) 为 \(|0\rangle\) 的情况，\(|x\rangle\) 是否是解可以从相位是否翻转看出。
但若 \(|q\rangle\) 是 \(|1\rangle\)，那么在进入未增广的 orcale 门 \(O\) 之前，最后的工作量子比特变成了 \((|0\rangle + |1\rangle) / \sqrt{2}\)。因此，
\[
|1\rangle |x\rangle \frac{|0\rangle - |1\rangle}{\sqrt{2}} \xrightarrow{Z\text{ gate}} |1\rangle |x\rangle \frac{|0\rangle + |1\rangle}{\sqrt{2}} \xrightarrow{\text{orcale}} 1^{f(x)} |1\rangle |x\rangle \frac{|0\rangle + |1\rangle}{\sqrt{2}} \xrightarrow{Z\text{ gate}} |1\rangle |x\rangle \frac{|0\rangle - |1\rangle}{\sqrt{2}}
\]
这意味着，对于 \(|q\rangle\) 为 \(|1\rangle\) 的情况，经过增广的 orcale \(O'\) 之后，相位并未发生变化，即没有标识为解。
练习 6.6
练习 6.6
验证除了一个无关紧要的全局相位因子 \(\alpha\)，盒子 6.1 第二个图中带点的框中的门完成相移运算 \(2 |00\rangle \langle00| - I\)。
首先，对于第一个量子比特，在控制点两边各有 \(X\) 门相当于以 \(|0\rangle\) 为控制；而对于第二个量子比特，由于 \(XHXHX = XZX = -Z\)、以及 \(XHHX = I\)，因此总地来说该门路等价于以第一个量子比特 \(|0\rangle\) 为控制的受控 \(-Z\) 门：
随后就分别使用 \(|00\rangle, |01\rangle, |10\rangle, |11\rangle\) 代入门路，可以得到输出结果是 \(- |00\rangle, |01\rangle, |10\rangle, |11\rangle\)。因此，该门路其实是
\[
- 2 |00\rangle \langle00| + I = e^{i \pi} (2 |00\rangle \langle00| - I)
\]