《量子计算与量子计算》习题 (待完成)¶
这是【非官方】的 M. A. Nielsen 与 I. L. Chuang 所著《量子计算和量子信息》(Quantum Computation and Quantum Information) 的习题。我同时也在参考清华大学出版社的赵千川的翻译本。
由于不是非常满意现在能搜寻到的资料，因此想尝试一下自己动手丰衣足食。但请不要指望这份习题答案的正确性和专业性；作者身处四大天坑，并没有 EE/CS/Phys/Math 背景。
作者对于量子计算是否有可能在量子力学或仿真问题上，会取代经典计算这样的情况感到略微的危机感。一旦确实地可以取代，而且有着数量级的效率提升，那么作者近七年的专业知识和学习，甚至 1960 年代发展起来的计算化学方法，就有可能要被颠覆。当然这或许这是杞人忧天，如同被害或加害妄想症那样。大家真的别笑话哈，我对量子计算确实就有着这种迷思。我也了解到分子动力学领域的一位数理化计通才，似乎曾试想了解量子计算，并确实地对一本专著作深入了解和翻译；但也因为对量子计算硬件前景有一些悲观的预期，就在更有希望的机器学习的土壤耕作了。我确实很敬仰，但各种意义上深感力不从心；更不用说心中的志向也不能算很高远，深刻地感受到某位哲人说的三十而立竟是如此遥不可及。因此，我只想找一个经典的教材，浅尝即止，稍作了解；不保证这种奇怪的热情或动力还能撑过哪怕半个个学期。如果量子计算确实有可能取代经典计算，我希望不至于落伍；但若它真的是 21 世纪惊天计算机科学天坑或骗局，那我也要被坑地清清楚楚。
目前只是开了个坑。如大家所见，现在只有一章的习题。关于其它习题相关的资料，我认为值得参考的有
陈汉武《量子计算和量子信息（一）——量子计算部分 阅读辅导及习题解析》，东南大学出版社。该书有第一与第二章的习题。第一章的导读材料很有价值，第二章的习题很详尽；但目前没有后续章节的习题。我认为后续章节才是这本书最重要的部分。
https://serab.net/docs/qcqi 我认为质量还是比较高的一份；我的答案也有不少参考并对照这份解答。它有部分第 2 到 6 章的习题。
其它很有意义的资料会有
https://enakai00.hatenablog.com/search?q=QCQI+exercise+solutions
https://quantumcomputing.stackexchange.com/questions/tagged/nielsen-and-chuang
https://github.com/rehaanahmad2013/NielsenChuang-QuantumComputingSolutions
如果题目有错误、或有更合理的解答，可以在 Github 提 Issue 哈。
但我假设现在应该没有多少人会想 pull request 吧，这本书的热度显然没有 CLRS 高。因此目前暂时是独裁地维护状态，以后再看是否需要变化。同时，目前暂时没有翻译为英文的打算。
第四章 量子线路¶
4.2 单量子比特运算¶
未完成的证明：练习 4.11
import numpy as np
import scipy
from qiskit import QuantumCircuit, Aer, assemble
from qiskit.visualization import plot_bloch_multivector
练习 4.1¶
练习 4.1
练习 2.11 计算了 Pauli 矩阵的特征向量 (如果还没有做这个练习，请现在就做)，在 Bloch 球面上求出不同 Pauli 矩阵的归一化特征向量对应的点。
首先，这三个 Pauli 矩阵 \(X, Y, Z\) 的特征值均为 \(\lambda_1 = -1, \lambda_2 = 1\)。它们的特征向量分别是
下面使用程序绘制 Bloch 球面。我们先用 NumPy 给出本征向量，随后代入到 Qiskit 中绘制。可以看到，\(X, Y, Z\) 的本征值分别对应 Bloch 球面上 \(x, y, z\) 三个方向。
X = np.array([[0, 1], [1, 0]])
Y = np.array([[0, -1j], [1j, 0]])
Z = np.array([[1, 0], [0, -1]])
def ex_4_1(matrix, title=None):
""" Input Pauli matrix X or Y or Z; Draw eigenvectors of matrix on Bloch sphere. """
eig = np.linalg.eigh(matrix)[1].T
circ = QuantumCircuit(2)
for n, e in enumerate(eig):
circ.initialize(e, n)
return plot_bloch_multivector(circ, title)
ex_4_1(X, "Eigenvectors of Pauli X")
ex_4_1(Y, "Eigenvectors of Pauli Y")
ex_4_1(Z, "Eigenvectors of Pauli Z")
练习 4.2¶
练习 4.2
令 \(x \in \mathbb{R}\) 即为实数，\(A\) 为一矩阵且满足 \(A^2 = I\)。证明：
利用这一结果验证式 (4.4) 到式 (4.6) 即关于 \(\hat x, \hat y, \hat z\) 轴向的旋转算符定义：
首先，我们回顾一下 \(z \in C\) 下的 Taylor 展开：
对于矩阵而言，其 Taylor 展开是类似的。我们将 \(z = i A x\) 代入，并以尽可能消除虚数符号为目的，得到
如果不用级数展开，而使用 Euler 公式 \(e^{i x} = \cos(x) + i \sin (x)\)，也可以得到相同的结论。
随后，我们注意到另一个条件 \(A^2 = I\)，那么上式可以进一步化简。我们先讨论 \(\cos\) 的情况：
这里利用到求和角标 \(k\) 必须是偶数的条件，因此可以将 \(A^k\) 的偶数幂次化为单位阵的幂次 \(I^{k/2}\)，进而所有被求和项只包含矩阵 \(I\)，可以提到求和之外。最终，将矩阵的函数化为数值函数与矩阵的乘积。
对于 \(\sin\) 而言，情况是类似的：
将 \(\cos(Ax) = \cos(x) I\) 与 \(\sin(Ax) = \sin(x) A\) 代入 \(\exp(i A x)\) 的展开式，得证。
我们不再验证式 (4.4-6)，只是使用程序简单验证一下当 \(\theta = 0.3\) 时式 4.4 的正确性。下面的第一个代码块是计算 \(\theta = 0.3\) 时 \(e^{i \theta X / 2}\) 的结果；第二个代码块则是式 (4.4) 最右边的矩阵数值结果。
θ = 0.3
scipy.linalg.expm(1j * θ * X / 2)
array([[0.98877108+0.j , 0. +0.14943813j],
[0. +0.14943813j, 0.98877108+0.j ]])
np.array([
[np.cos(θ/2), - 1j * np.sin(θ/2)],
[- 1j * np.sin(θ/2), np.cos(θ/2)]
])
array([[0.98877108+0.j , 0. -0.14943813j],
[0. -0.14943813j, 0.98877108+0.j ]])
练习 4.3¶
练习 4.3
证明除了一个全局相位，\(\pi/8\) 门满足 \(T = R_z (\pi/4)\)。
这直接可以参考书中式 (4.3)：
练习 4.4¶
练习 4.4
对某个 \(\varphi\)，将 Hadamard 门表示为旋转算符 \(R_x, R_z\) 以及 \(e^{i \varphi}\) 的乘积。
这个结果需要稍微凑一下。答案应该是
上式的 \(\varphi\) 不是任意的，而是 \(\varphi = \pi / 2\)。
这个等式意味着，态向量在 Hadamard 门作用下，相当于其在 Bloch 球面的表示先依 \(z\) 轴旋转 90°，再依 \(x\) 轴旋转 90°、最后依 \(z\) 轴旋转 90°。\(z\) 轴的方向是 \(|1\rangle\) 到 \(|0\rangle\)；所有旋转都是逆时针旋转。下面的第一块代码是定义 \(\varphi = \pi/2\) 以及旋转算符的矩阵表示；第二个代码块是分别给出在 \(|\psi\rangle = 0.8 |0\rangle + 0.6i |1\rangle\) 时，\(|\psi\rangle\)、\(R_z (\varphi) |\psi\rangle\)、\(R_x (\varphi) R_z (\varphi) |\psi\rangle\)、\(R_z (\varphi) R_x (\varphi) R_z (\varphi) |\psi\rangle\) 的 Bloch 球面表示。籍此可以了解向量是如何沿轴旋转的。
φ = np.pi / 2
Rx_varphi = scipy.linalg.expm(1j * φ * X / 2)
Rz_varphi = scipy.linalg.expm(1j * φ * Z / 2)
circ = QuantumCircuit(4)
vec = np.array([0.8, 0.6j])
circ.initialize(vec, 0)
circ.initialize(Rz_varphi @ vec, 1)
circ.initialize(Rx_varphi @ Rz_varphi @ vec, 2)
circ.initialize(Rz_varphi @ Rx_varphi @ Rz_varphi @ vec, 3)
plot_bloch_multivector(circ)
练习 4.5¶
练习 4.5
证明 \((\hat n \cdot \vec\sigma)^2 = I\)，并以此验证式 (4.8)：
其中，\(\hat n = (n_x, n_y, n_z)\) 为三维空间的实单位向量，\(\vec \sigma = (X, Y, Z)\) 是 Pauli 矩阵的三元向量。
若 \((\hat n \cdot \vec\sigma)^2 = I\) 成立，那么式 (4.8) 的验证实际上和练习 4.2 对式 (4.4-6) 的验证过程实际上是相同的。那么证明的难点还是在 \((\hat n \cdot \vec\sigma)^2 = I\) 的证明上。
实际上证明很简单。首先，容易给出
随后是要作上式的平方。矩阵的平方与数乘不太相同，特别是在对交叉项的处理上。例如 \((A + B)^2 = A^2 + B^2 + AB + BA\)。因此，上式平方是
容易验证 \(XY+YX = YZ+ZY = ZX+XZ = 0\)，因此上式后三项为零矩阵。同时由于 \(X^2 = Y^2 = Z^2 = I\)，因此前三项恰为
注意最后我们利用了 \(\hat n\) 是单位向量的条件。
练习 4.6 (旋转 Bloch 球面的解释)¶
练习 4.6
\(R_{\hat n} (\theta)\) 算符称为旋转算符的一个原因是如下要证明的事实。假设一个单量子比特的状态由 Bloch 向量 \(\vec \lambda\) 表示，则旋转算符 \(R_{\hat n} (\theta)\) 在该态向量上的作用，是绕 Bloch 球面的向量 \(\hat n\) 轴旋转 \(\theta\) 角度。这个事实解释了旋转矩阵中出现的看起来特别神秘的因子 2。
这里需要先引入一个结论；该结论似乎并未在书中出现。这里请参考下述文档的第 20 页。
http://www.vcpc.univie.ac.at/~ian/hotlist/qc/talks/bloch-sphere-rotations.pdf
若 \(\hat n\) 在 Bloch 球面上的坐标可以用 \((\theta_{\hat n}, \varphi_{\hat n})\) 表示，那么绕 \(\hat n\) (逆时针) 旋转 \(\theta\) 角度的算符可以表示为
其大致思路是将绕 \(\hat n\) 轴旋转的问题化为绕 \(\hat z\) 轴旋转。具体来说，
执行 \(R_z (- \varphi_{\hat n})\)，它可以将 \(\hat n\) 轴转到 \(\varphi = 0\) 处，即转到 \(xOz\) 平面上；\(\vec \lambda\) 也作了响应的转动；
执行 \(R_y (- \theta_{\hat n})\)，它可以将方才转到 \(xOz\) 平面上的 \(\hat n\) 轴再转到 \(\theta = 0\) 处，即转到 \(z\) 轴上；\(\vec \lambda\) 也作了响应的转动；
执行 \(R_z (\theta)\)，它执行的是经过上述两个步骤转动后，\(\vec \lambda\) 相对于处在 \(\hat z\) 轴的 \(\hat n\) 的旋转 \(\theta\) 角度操作；
执行 \(R_z (\varphi_{\hat n}) R_y (- \theta_{\hat n})\)，复原 \(\hat n\) 的位置；\(\vec \lambda\) 也作了响应的转动。
从物理的直觉上，如果我们接受 \(R_y(\theta), R_z(\theta)\) 算符的物理意义，那么这五步操作确实可以表示绕 Bloch 球面的向量 \(\hat n\) 轴旋转 \(\theta\) 角度。
但我们并未证明数学上等式左右是成立的。证明的过程会是非常繁琐的；我们用 Mathematica 对计算过程简化，可以验证
就此完成对 \(R_{\hat n} (\theta)\) 表达式正确性与物理图景的说明了。
练习 4.7¶
练习 4.7
证明 \(X Y X = -Y\)，并以此证明 \(X R_y (\theta) X = R_y (-\theta)\)。
\(XYX = -Y\) 的证明只需要验证矩阵乘法即可。\(X R_y (\theta) X = R_y (-\theta)\) 的证明可以利用式 (4.5) 的结论以及 \(X^2 = I\) 的性质：
练习 4.8¶
练习 4.8
任意一个单量子比特酉算符可以以下述形式表示：
其中 \(\alpha, \theta \in \mathbb{R}\)、\(\hat n\) 为三维实向量。
证明这个事实；
求 \(\alpha, \theta, \hat n\) 以得到 Hadamard 门 \(H\)；
求 \(\alpha, \theta, \hat n\) 以得到相位门 \(S\)。
\[\begin{split} H = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}, \quad S = \begin{bmatrix} 1 & 0 \\ 0 & i \end{bmatrix} \end{split}\]
第一问
首先我们需要表明 \(R_{\hat n} (\theta)\) 确实是酉的。实际上之前的练习或书中的文本都没有对这个事实作说明 (练习 4.6 或许需要)。我们首先回顾式 (4.8)：
这里我们用了练习 4.5 的记号。对 \(R_{\hat n} (\theta)\) 取共轭转置，可知
这里利用了 Pauli 矩阵的共轭转置仍然是自身的性质；因此，只有一个虚数单位的 \(i\) 的正负号被颠倒了而已。两者相乘，可以得到
既然 \(R_{\hat n} (\theta)\) 是酉的，那么构成该矩阵表示的两个列向量必然是相互正交且归一的。我们假设一个酉矩阵可以写为
若 \(a, b, c\) 的值是确定的，那么 \(d\) 的值也必然是确定的，因为 \(U U^\dagger = I\) 可以推演出 \(a c^* + b d^* = 0\)。
分别依据 \(U U^\dagger = I\) 与 \(U^\dagger U = I\)，我们可以知道 \(|a|^2 + |b|^2 = 1\) 与 \(|a|^2 + |c|^2 = 1\)。这也同时意味着 \(|b| = |c|\)。因此 \(b, c\) 的值不是任意的。
以上述两个结论出发，可以知道若要使一个 \(\mathbb{C}^2\) 的酉矩阵可以表示为任意酉矩阵，
\(a\) 可以是任意 \(0 \leqslant |a| \leqslant 1\) 的复数；
\(b, c\) 在给定 \(a\) 的值时，尽管模长是固定的，但分别可以取任意相位。
现在回到 \(R_{\hat n} (\theta)\) 的讨论上。我们将其矩阵形式写出：
首先，我们考察 \(b = e^{i \alpha} (- i n_x - n_y) \sin (\theta/2)\) 与 \(c = e^{i \alpha} (- i n_x + n_y) \sin (\theta/2)\) 的相位可以是任意的。我们可以计算得到 (下式利用到 \(\theta \in [0, 2 \pi)\) 下，\(\sin (\theta/2) \geqslant 0\)，因此 \(n_y \sin (\theta/2) < 0\) 在 \(\sin(\theta/2) \neq 0\) 时等价于 \(n_y < 0\))
由于上式中有两个自由度 (\(\alpha, n_x/n_y\))，因此可以保证 \(b, c\) 分别都可以取到任意的相位。
随后，我们再考虑 \(a = \cos \frac{\theta}{2} - i n_z \sin \frac{\theta}{2}\) 的取值。我们在讨论 \(b, c\) 时，已经使用了 \(\alpha\) 的自由度，因此这里 \(\alpha\) 应当视作定值。而 \(n_x, n_y, n_z\) 三个变量受到归一化条件 \(|n_x|^2 + |n_y|^2 + |n_z|^2 = 1\) 限制，因此总自由度为 2；由于 \(n_x/n_y\) 的自由度被使用，因此还剩下的自由度可以归到 \(n_z\) 的取值上。因此，上面 \(a\) 的取值总共受到两个自由度制约，分别是 \(\theta\) 的取值与 \(n_z\) 的取值。这两个自由度分别对应到 \(a\) 的实部与虚部，因此 \(a\) 也是可以任意取到的。
但稍微严格一些的分析方法是考察 \(a = \cos \frac{\theta}{2} - i n_z \sin \frac{\theta}{2}\) 的幅角与模长，因为实部与虚部并不是任意的 \([0, 1]\) 实数，而必须要满足模长不大于 1 的条件。若模长能取任意的 \(|a| \in [0, 1]\) 且幅角能取任意的 \(\arg (a) \in [0, 2\pi)\)，那么 \(a\) 便可以取任意 \(0 \leqslant |a| \leqslant 1\) 复数；但这种分析稍微有些复杂 (我们仍然用到 \(\theta \in [0, 2 \pi)\) 下，\(\sin (\theta/2) \geqslant 0\))：
现在的自由变量仍然是 \(n_z\) 与 \(\theta\)。但由于幅角需要取模 \(2 \pi\) 取余数，还要判断 \(\cos (\theta / 2)\) 的正负号，但这不太利于分析。实际上，在确定 \(b, c\) 相位时，\(\alpha\) 已经被指定了数值了；\(\cos (\theta / 2)\) 的正负号可以依靠 \(\theta\) 的取值解决。因此，我们会希望下述的 \(\gamma_\mathrm{norm}, \gamma_\mathrm{arg}\) 可以取到任意定义域内的值：
我们暂且不对 \(\gamma_\mathrm{arg} = \pm \infty\) 或 \(\gamma_\mathrm{norm} = 0 \text{ or } 1\) 的特殊情况作细致的讨论，只要基本正确就行了。依据上两式，可以推知：
这两式在 \(\gamma_\mathrm{arg} \in (-\infty, +\infty), \gamma_\mathrm{norm} \in (0, 1)\) 的取值域内都是合理的，即一定满足 \(\theta \in (0, 2\pi)\) 且 \(n_z \in (0, 1)\)。上面的整个过程表明了，\(R_{\hat n} (\theta)\) 的第一个元素 \(a = \cos \frac{\theta}{2} - i n_z \sin \frac{\theta}{2}\) 可以取到任意模不大于 1 的复数。边界情况没有作证明，但大体证明完毕。
在这些分析下，我们应当知道，一般来说参数 \(\alpha, \theta, \hat n\) 总共对应四个自由度，恰好与矩阵元素数量一致。因此，大多数情况下，对于给定的酉矩阵 \(U\)，其表示 \(U = \exp(i \alpha) R_{\hat n} (\theta)\) 中的参数 \(\alpha, \theta, \hat n\) 是唯一确定的。
第二问
求解这类问题时，一般来说先通过 \(b, c\) 的幅角确定 \(n_x / n_y\) 和 \(\alpha\) 的值，并尝试给出看起来比较合理的 \(\theta\) 值。最后通过 \(a\) 的值确定 \(n_z\)。
对于 Hadamard 门，我们首先可以依 \(b = c = 1/\sqrt{2}\)，可知 \(b, c\) 相位相同，确定 \(n_y = 0, \alpha = \pi/2\)。随后依 \(a = 1/\sqrt{2}\) 且没有虚部，确定 \(\theta = \pi\)。最后，依据 \(a, b, c\) 的数值，可以确定 \(n_x = n_z = 1/\sqrt{2}\)。因此，\(n = (0, 1/\sqrt{2}, 1/\sqrt{2})\)，
第三问
依 \(b = c = 0\)，我们确定 \(\theta = 0\) 或 \(n_x = n_y = 0\)。但当我们代入 \(\theta = 0\) 时，会发现 \(a, d\) 的相位一致；这与 \(1, i\) 之间相位相差 \(\pi/2\) 矛盾。因此只可能是 \(n_x = n_y = 0\) 且 \(n_z = 1\)，即 \(\hat n = (0, 0, 1)\)。随后再对 \(a, d\) 的值进行讨论，容易知道
练习 4.9¶
练习 4.9
解释为什么任意单量子比特上的酉算符可以写成式 (4.12) 的形式。
这里的证明过程应当与练习 4.8 类似，但会相对容易一些。证明的思路是：
表明 \(UU^\dagger = U^\dagger U = I\)；
表明使用其中的两个自由度 (譬如说 \(\alpha, \beta\))，可以使得非对角元 \(- e^{i (\alpha - \beta/2 + \delta/2)} \sin (\gamma/2)\) 与 \(e^{i (\alpha + \beta/2 - \delta/2)} \sin (\gamma/2)\) 分别可以取到任意相位；
表明在剩余的两个自由度 (譬如说 \(\delta, \gamma\)) 下，可以使得 \(e^{i (\alpha - \beta/2 - \delta/2)} \cos (\gamma/2)\) 取到任意的模长在 1 以内的复数。
这道题还有另一种思路。这里请参考下述文档 (但该文档的证明其实错了，因此不能照搬那边的答案)：
https://serab.net/docs/qcqi/chapter4/#49
我们假设已经完成练习 4.8 的证明，那么
练习 4.9 与练习 4.8 的 \(\alpha\) 恰好是一致的。对于练习 4.9 中的 \(\beta, \delta\) 值，他们应当会满足下述关系 (依据 \(R_{\hat n} (\theta)\) 的非对角元的幅角关系)
那么
这两个关系式可以唯一地确定 \(\beta / 2 - \delta / 2\) 的数值。
同时还要满足 (依据 \(R_{\hat n} (\theta)\) 的对角元的幅角关系)
那么
这两个关系式可以唯一地确定 \(\beta/2 + \delta/2\) 的数值。我们已经知道了 \(\beta/2 - \delta/2\) 的数值了，因此 \(\beta, \delta\) 可以被唯一地确定。
最后，可以通过 \(R_{\hat n} (\theta)\) 的对角元 (也可以是非对角元) 的模长，唯一地确定 \(\gamma\) 的数值。因此，酉矩阵总是可以写为式 (4.12) 的形式，并且参数是唯一确定的。
练习 4.10 (旋转的 \(x\)-\(y\) 分解)¶
练习 4.10
用 \(R_x\) 代替 \(R_z\)，给出相应于定理 4.1 的分解。
分解是很容易给出的：
但类似于定理 4.1 的简单证明，但过程非常复杂，在这个练习中恐怕就很难给出了。
但本题的证明也可以投机取巧地给出。我们只要说，我们将 \(x\) 与 \(z\) 轴转换一下，换个坐标系，那么式 (4.11) 自然就转化为了上述表达式 (可能因为左右手坐标系互换会导致 \(\gamma\) 应该要变为 \(\pi - \gamma\)，但这不重要)。
练习 4.11¶
练习 4.11
设 \(\hat m\) 和 \(\hat n\) 是三维空间中不平行的实单位向量，证明任意单量子比特上的酉算符对适当的 \(\alpha, \beta_k, \gamma_k\)，可以写成
危险
未完成的证明！
我想这道题应该会与练习 4.6 的思路比较像，但我不是很能把握题意。
练习 4.12¶
练习 4.12
给出 Hadamard 门的 \(A, B, C\) 和 \(\alpha\)。其中，\(A, B, C\) 为酉算符，\(A B C = I\) 且 \(H = e^{i \alpha} A X B X C\)。
首先根据式 (4.12)，我们可以比较容易地凑出 \(\alpha = \pi/2\)、\(\beta = 0\)、\(\gamma = \pi/2\)、\(\delta = \pi\)。随后我们回顾推论 4.2 的过程，就知道
练习 4.13 (线路恒等式)¶
练习 4.13
能以熟知的恒等式来简化线路非常有用，证明如下三个恒等式：
证明略。直接套算符的矩阵表示定义很容易可以给出证明。
练习 4.14¶
练习 4.14
利用前面的练习，证明除了一个全局相位，\(HTH=R_x(\pi/4)\)。
直接套定义的话，应该能容易地给出
验证上述等式很容易，代入矩阵定义就行了。
当然，题目既然要求说用上面的练习，那就用吧。我们回顾到
我们再考虑到式 (4.6)：
因此，
练习 4.15 (单量子比特运算的组合)¶
练习 4.15
Bloch 球面为显示两个旋转组合的效果提供了一条很好的途径。
证明如果绕轴 \(\hat n_1\) 旋转一个角度 \(\beta_1\)，接着绕轴 \(\hat n_2\) 旋转一个角度 \(\beta_2\)，则总的旋转为如下给出的绕轴 \(\hat n_{12}\) 转角为 \(\beta_{12}\) 的旋转：
\[\begin{split} \begin{align*} c_{12} &= c_1 c_2 - s_1 s_2 \hat n_1 \cdot \hat n_2 \tag{4.19} \\ s_{12} \hat n_{12} &= s_1 c_2 \hat n_1 + c_1 s_2 \hat n_2 - s_1 s_2 \hat n_2 \times \hat n_1 \tag{4.20} \end{align*} \end{split}\]其中，在角标 \(i = 1, 2, 12\) 下
\[ c_i = \cos \frac{\beta_i}{2}, \quad s_i = \sin \frac{\beta_i}{2} \]证明 \(\beta_1 = \beta_2\) 且 \(\hat n_1 = \hat z\)，这些等式可以简化为
\[\begin{split} \begin{align*} c_{12} &= c^2 - s^2 \hat z \cdot \hat n_2 \tag{4.21} \\ s_{12} \hat n_{12} &= s c (\hat z + \hat n_2) - s^2 \hat n_2 \times \hat z \tag{4.22} \end{align*} \end{split}\]
本题的第二小题在第一小题基础上非常容易导出。我们只考虑第一小题。
需要先说明，待求的未知量除了 \(\beta_{12}\)，还有 \(\hat n_{12}\)。第一小题的证明其实只是套用式 4.8 的证明即可给出，只是过程会比较繁琐。依照题目对 \(c_i, s_i\) 的定义 (\(i = 1, 2, 12\))，
需要注意算符乘积顺序，旋转算符一般不对易。同时，我们需要知道，先作用的算符在右边，后作用的算符在左边。因此，总的作用算符是
这里处理起来比较麻烦的项是 \((\hat n_1 \cdot \vec \sigma) (\hat n_2 \cdot \vec \sigma)\)。若利用下述关系：
可以知道
代入 \(R_{\hat n_{12}} (\beta_{12})\) 的表达式，可以得到
又联系到 \(R_{\hat n_{12}} (\beta_{12})\) 的另一种表示：
因此联立上两式，就能得到待证等式 (4.19-20)。
4.3 受控运算¶
本节的习题也可以参考 Qiskit 网站：
https://qiskit.org/textbook/ch-gates/more-circuit-identities.html
import numpy as np
from opt_einsum import contract as einsum
from qiskit import QuantumCircuit
from qiskit.quantum_info import Operator
import warnings
np.set_printoptions(4, suppress=True)
warnings.filterwarnings("ignore")
# Vector in computational basis
vec0 = np.array([1, 0])
vec1 = np.array([0, 1])
# Matrices in computational basis
I = np.eye(2)
X = np.array([[0, 1], [1, 0]])
Y = np.array([[0, -1j], [1j, 0]])
Z = np.array([[1, 0], [0, -1]])
H = 1/np.sqrt(2) * np.array([[1, 1], [1, -1]])
T = np.array([[1, 0], [0, np.exp(1j*np.pi/4)]])
S = T @ T
P0 = np.outer(vec0, vec0)
P1 = np.outer(vec1, vec1)
预练习：受控门的张量积表示¶
预练习
请表明可以作用于 \(|x_1x_2\rangle\) 的、以 \(x_1\) 为控制量子比特、以 \(x_2\) 为目标量子比特的受控非门 \(\mathrm{CNOT}_{x_1, x_2}\) 可以表示为
其中，\(P_0, P_1\) 是计算基下的投影算符：
我们以后经常会使用这类受控门的张量积表示，来进行证明或计算。该控制门的图示是 (\(x_1, x_2\) 对应到下图的 \(q_0, q_1\))
circ = QuantumCircuit(2)
circ.cx(0, 1)
circ.draw()
证明 1
我们令待证等式右边为算符 \(A = P_0 \otimes I + P_1 \otimes X\) 。将 \(A\) 作用于两个量子比特 \(x_1, x_2\) 所构成的态 \(|x_1 x_2\rangle\) 上：
我们只需要考虑 \(|x_1 x_2\rangle\) 为计算基 \(\{ |00\rangle, |01\rangle, |10\rangle, |11\rangle \}\) 的情况。
若 \(|x_1\rangle = |0\rangle\)，那么 \(P_0 |0\rangle = |0\rangle\) 且 \(P_0 |0\rangle = 0\)。因此，
\[ A |0 x_2\rangle = |0\rangle \otimes I |x_2\rangle = |0x_2\rangle \]这意味着如果 \(|x_1\rangle = |0\rangle\)，那么经过算符 \(A\) 的作用后，\(|x_2\rangle\) 仍然保持不变。
若 \(|x_1\rangle = |1\rangle\)，那么 \(P_0 |1\rangle = 0\) 且 \(P_1 |1\rangle = |1\rangle\)。因此，
\[ A |1 x_2\rangle = |1\rangle \otimes X |x_2\rangle \]这意味着如果 \(|x_1\rangle = |1\rangle\)，那么经过算符 \(A\) 的作用后，\(|x_2\rangle\) 会变成 \(X |x_2\rangle\)，即将非门作用于 \(|x_2\rangle\)。
因此，算符 \(A\) 完全符合受控非门的定义。
对于上述的计算过程，请不要搞混 \(x_1, x_2\) 的下标与 \(|0\rangle, |1\rangle\)。
证明 2
直接计算等式右的 \(P_0 \otimes I + P_1 \otimes Z\)，并验证它是否是书中式 (4.23) 所表示的矩阵：
求取张量积 (Kronecker tensor product) 的过程实际上也可以通过 np.kron 函数实现。
np.kron(P0, I) + np.kron(P1, X)
array([[1., 0., 0., 0.],
[0., 1., 0., 0.],
[0., 0., 0., 1.],
[0., 0., 1., 0.]])
补充
我们有时还需要用以 \(x_2\) 为控制量子比特、以 \(x_1\) 为目标量子比特的受控非门 \(\mathrm{CNOT}_{x_1, x_2}\)。其表示是
请注意相对于 \(\mathrm{CNOT}_{x_1, x_2}\)，上式的变化不是 \(P_0\) 与 \(P_1\) 交换，而是张量积的顺序发生了变化。其图示是 (\(x_1, x_2\) 对应到下图的 \(q_0, q_1\))
circ = QuantumCircuit(2)
circ.cx(1, 0)
circ.draw()
练习 4.16 (多量子比特门的矩阵表示)¶
练习 4.16
在计算基下，如下线路的 \(4 \times 4\) 酉矩阵是什么？
如下线路在计算基下的酉矩阵是什么？
这里有意将原书中的 \(x_1, x_2\) 颠倒过来。一般来说，不管是程序还是书中，排在上面的线路的量子比特序号都比较小。
在这一小节中，我们会尽量同时使用 qiskit 来绘制线路图，以熟悉程序的编写。
第一个线路的酉矩阵是
np.kron(H, I)
array([[ 0.7071, 0. , 0.7071, 0. ],
[ 0. , 0.7071, 0. , 0.7071],
[ 0.7071, 0. , -0.7071, -0. ],
[ 0. , 0.7071, -0. , -0.7071]])
该线路的绘制可以通过下述代码实现：
circ = QuantumCircuit(2)
circ.h(0)
circ.draw()
第二个线路的酉矩阵是
np.kron(I, H)
array([[ 0.7071, 0.7071, 0. , 0. ],
[ 0.7071, -0.7071, 0. , -0. ],
[ 0. , 0. , 0.7071, 0.7071],
[ 0. , -0. , 0.7071, -0.7071]])
该线路的绘制可以通过下述代码实现：
circ = QuantumCircuit(2)
circ.h(1)
circ.draw()
练习 4.17 (由受控 \(Z\) 门建造受控非门)¶
练习 4.17
从一个受控 \(Z\) 门 (即一个在计算基下的作用由如下酉矩阵表示)
和两个 Hadamard 门构造一个受控非门，并指定控制量子比特和目标量子比特。
该练习是多解题。我们将在练习 4.18 中证明到
因此，对于受控 \(Z\) 门而言，控制量子比特和目标量子比特是完全等价的。我们将受控 \(Z\) 门的矩阵表示用程序变量 ctrl_Z 写出。
ctrl_Z = np.kron(P0, I) + np.kron(P1, Z)
ctrl_Z
array([[ 1., 0., 0., 0.],
[ 0., 1., 0., 0.],
[ 0., 0., 1., 0.],
[ 0., 0., 0., -1.]])
受控非门 CNOT 是受控 \(X\) 门，依据控制量子比特是 \(x_1\) 或 \(x_2\)、目标量子比特是 \(x_2\) 或 \(x_1\)，我们可能写出两种 CNOT 的矩阵表示，分别用变量 \(\mathrm{CNOT}_{x_1, x_2}\) ctrl_1_X 与 \(\mathrm{CNOT}_{x_2, x_1}\) ctrl_2_X 写出。
ctrl_1_X = np.kron(P0, I) + np.kron(P1, X)
ctrl_2_X = np.kron(I, P0) + np.kron(X, P1)
ctrl_1_X, ctrl_2_X
(array([[1., 0., 0., 0.],
[0., 1., 0., 0.],
[0., 0., 0., 1.],
[0., 0., 1., 0.]]),
array([[1., 0., 0., 0.],
[0., 0., 0., 1.],
[0., 0., 1., 0.],
[0., 1., 0., 0.]]))
我们很容易地可以凑出下述结果：
用数学的方式来表达上述过程，则是
有两种证明方法。第一种是给出所有矩阵表示并作验证：
np.allclose(np.kron(I, H) @ ctrl_Z @ np.kron(I, H), ctrl_1_X)
True
第二种方法是作代数证明。回顾到 \(HZH = X, H^2 = I\)，因此
证明完毕。
其中一个门路的图像可以绘制如下 (\(x_1, x_2\) 对应到下图的 \(q_0, q_1\))：
circ = QuantumCircuit(2)
circ.h(1); circ.cz(0, 1); circ.h(1)
circ.draw()
由于受控 \(Z\) 门实际上是关于控制与目标量子比特 \(x_1, x_2\) 对称的，因此也很容易地给出另一种情况：
练习 4.18¶
练习 4.18
证明下图：
回顾到预练习，用数学的语言表述，该题希望证明
这个证明恐怕还是需要用矩阵表示做比较方便：
np.allclose(
np.kron(P0, I) + np.kron(P1, Z),
np.kron(I, P0) + np.kron(Z, P1))
True
但也可以使用代数做法。我们可以利用下述结论：
因此，
因此，受控 \(Z\) 门是关于两个量子比特对称的。一般来说，它的图像不使用方块圈起来的 \(Z\) 给出，而是像下图一样 (也可以回顾练习 4.17 的解答)：
circ = QuantumCircuit(2)
circ.cz(0, 1)
circ.draw()
练习 4.19 (受控非门在密度矩阵上的作用)¶
练习 4.19
受控非门在密度矩阵 \(\rho\) 上的作用是重排矩阵元素的位置，故仅为一置换。在计算基下清晰地写出它的作用。
实际上，不仅对于密度矩阵，对于任意的 \(4 \times 4\) 矩阵 \(A\) 都是置换作用。我们令计算基下的 \(A\) 矩阵：
A = np.array(np.zeros((4, 4)) + np.array([1, 2, 3, 4]) + np.array([10, 20, 30, 40])[:, None], dtype=int)
A
array([[11, 12, 13, 14],
[21, 22, 23, 24],
[31, 32, 33, 34],
[41, 42, 43, 44]])
可以知道，\(\mathrm{CNOT}_{x_1, x_2} A\) 的效应是将矩阵的第 3、4 行进行对调：
np.array(ctrl_1_X @ A, dtype=int)
array([[11, 12, 13, 14],
[21, 22, 23, 24],
[41, 42, 43, 44],
[31, 32, 33, 34]])
可能更有意义的作用是 \(\mathrm{CNOT}_{x_1, x_2} \, A \, \mathrm{CNOT}_{x_1, x_2}^\dagger\) 的效应是将第 3、4 行与第 3、4 列同时对调。我们同时注意到 \(\mathrm{CNOT}_{x_1, x_2}\) 是 Hermitian 矩阵，即 \(\mathrm{CNOT}_{x_1, x_2} = \mathrm{CNOT}_{x_1, x_2}^\dagger\)。
np.array(ctrl_1_X @ A @ ctrl_1_X, dtype=int)
array([[11, 12, 14, 13],
[21, 22, 24, 23],
[41, 42, 44, 43],
[31, 32, 34, 33]])
因此，操作 \(\mathrm{CNOT}_{x_1, x_2} \, A \, \mathrm{CNOT}_{x_1, x_2}^\dagger\) 实际上相当于将计算基 \(\{ |00\rangle, |01\rangle, |10\rangle, |11\rangle \}\) 转换到 \(\{ |00\rangle, |01\rangle, |11\rangle, |10\rangle \}\)。
练习 4.20 (受控非门的基变换)¶
练习 4.20
不像理想的经典门，理想的量子门没有 (如电子工程师说的) 高阻抗输入。实际上，“控制”和“目标”的角色是随意的——它们的区分依赖于你认为该设备在哪组基下计算。我们已经描述了受控非门相对计算基的行为，并且在这个描述中控制量子比特是不变的。然而，如果考虑一组不同的基，则控制量子比特的确要变：我们将看到依赖于“目标”量子比特的状态，它的相位要翻转。证明下图：
引入基状态组 \(|\pm\rangle \equiv (|0\rangle \pm |1\rangle) / \sqrt{2}\)，利用这个线路恒等式关系证明一个第一个量子比特作为控制、第二个量子比特作为目标的受控非门的作用为
因此，相对这组新基，目标的量子比特的状态不变，而控制量子比特的状态在目标是 \(|-\rangle\) 的时候翻转，否则保持不变；即在这组基下，目标和控制的角色实际上互换了。
首先证明线路图等式。该线路图等式用数学语言表述，是
证明如下。我们需要利用到的结论有
我们当然也可以利用矩阵乘法直接证明等式：
np.allclose(
np.kron(H, H) @ ctrl_1_X @ np.kron(H, H),
ctrl_2_X)
True
第二个论断的另一种叙述方式是，若计算基下的态 \(|x_1 x_2\rangle\) 等价于 \(\{ |+\rangle, |-\rangle \}\) 基下的态 \(|y_1 y_2\rangle\)，那么 \(\mathrm{CNOT}_{x_1, x_2}\) 作为 \(x_1\) 控制、\(x_2\) 目标的受控非门，在基 \(\{ |+\rangle, |-\rangle \}\) 下恰好等价于 \(\mathrm{CNOT}_{y_2, y_1}\) 即 \(|y_2\rangle\) 控制、\(|y_1\rangle\) 目标的受控非门。
实际上左乘 \(H\)，右乘 \(H^\dagger = H\) 就相当于将算符的表示矩阵从计算基 \(\{ |0\rangle, |1\rangle \}\) 转换到基 \(\{ |+\rangle, |-\rangle \}\)。依照这个思路，我们作如下简单的说明。我们首先要回顾到
以及
因此，
上式中用到的技巧是 \((H \otimes H)^2 = I\)。
类似地，
对于 \(|-\rangle |+\rangle, |-\rangle |-\rangle\) 来说，证明过程是类似的。
练习 4.21¶
练习 4.21
验证下图的 \(C^2 (U)\) 的运算。
其中，\(V^2 = U\)，且 \(U, V\) 均为酉算符。
该练习尽管可以使用数学方法作证明，但过程非常繁琐。分类讨论是最快的处理方法。我们考察下图：
上图的过程是指，对于初始三粒子态 \(|\psi_0\rangle = |x_1 x_2\rangle \otimes |x_3\rangle\)，经过该门路后得到 \(|\psi_5\rangle\)。我们对 \(|x_1 x_2\rangle = |00\rangle, |01\rangle, |10\rangle, |11\rangle\) 分别进行讨论。下面需要利用到酉矩阵的性质 \(V V^\dagger = V^\dagger V = I\)。
这其中，只有 \(|11\rangle \otimes |x_3\rangle\) 给出了 \(|11\rangle \otimes U |x_3\rangle\)，其它情况都保持初态不变。因此，该门路从定义上确实符合 \(x_1, x_2\) 为控制量子比特、\(x_3\) 为目标量子比特的受控 \(U\) 门路。
练习 4.22¶
练习 4.22
证明一个 \(C^2 (U)\) 门 (对任意单量子比特酉算符 \(U\)) 可至多用 8 个单量子比特门和 6 个受控非门构造出来。
该证明实际上还是比较精妙的。这里先给出大体的证明过程；但对于其中一部分细节，我们在后续的引理证明部分给出。
该题的参考资料是
https://quantumcomputing.stackexchange.com/a/6951/14843
第一步：用 CNOT 与单量子比特酉算符表示 \(C^2(U)\) 门¶
证明的第一步很容易。我们回顾到图 4.6，任意的酉矩阵 \(V\) 总可以写为酉矩阵 \(A, B, C\) 与实数相位参数 \(\alpha\) 的表达式：
为了方便，我们定义下述相位算符：
因此，书中的图 4.6 可以表示如下 (注意为了这道例题的记号方便，我们有意用 \(V\) 替代 \(U\) 表示任意酉矩阵)：
其转置 \(V = C^\dagger X B^\dagger X (e^{-i \alpha} A^\dagger)\) 也是容易给出的。我们只要将转换为自伴算符，并对调线路顺序即可：
我们将这两个线路代入图 4.8 即可 (红色线条隔开受控 \(V\) 或 \(V^\dagger\) 算符的代入区域)：
我们发现，上述的图像中，有两个可以简化的线路。所有蓝色虚线框中标出的部分实际上是恒等作用 \(A A^\dagger = C^\dagger C = I\) (回顾到 \(A, B, C\) 都是酉矩阵)，因此进一步简化为
到现在为止，我们简化到 8 个单量子比特门路、与 8 个 CNOT 门路。我们还需要减掉两个 CNOT 门路。下一步中，我们会先对上图中的蓝色区域所包含的 CNOT 作简化。
第二步：简化 CNOT 门路¶
这一步需要用到下述引理一：
我们可以立即简化得到 (这里仍然有 7 个 CNOT 门路，还没有达到要求)
注意到第三行的 \(B^\dagger\) 门路与第一、二行的 CNOT 门路相互不受影响，因此我们交换一下这两个门路：
对上述蓝色区域使用引理一推论：
可以得到
第三步：相位转移¶
看起来问题又复杂化了，重新回到了 8 个 CNOT 门路。但实际上，依据引理二与引理三，上述蓝色虚线框中的部分可以比较随意地移动。迁移之后，得到
橙色的区域是两个相同的 CNOT 算符。由于 CNOT 算符在双量子比特空间下是实对称酉算符，因此可以相互抵消。最终，我们得到
引理一：CNOT 门路简化¶
我们需要证明下述路线图：
证明方法与练习 4.21 相同。我们对等式左作考察：
再对等式右作考察：
我们就发现 \(|\psi_3\rangle = |\psi_5\rangle\)，即等式两边相等。
引理一推论¶
我们给出下述等式关系：
我们对引理一的等式左右取自伴算符，随后对调等式左右，就得到上式的第一个等号。
第二个等号相当于一种对易关系：
对于这个对易，它是比较容易看出来的，我们不作仔细证明。
我们说，\(\mathrm{CNOT}_{x_1, x_3}\) 对于对目标量子比特 \(|x_3\rangle\) 的作用是 \(X\) 或 \(I\)。而其它可能对 \(|x_3\rangle\) 产生作用的算符是 \(\mathrm{CNOT}_{x_2, x_3}\)，它也是 \(X\) 或 \(I\)。因此，可能作用于 \(|x_3\rangle\) 上的所有算符都相互对易。
同时，\(|x_1\rangle\) 的作用仅仅是控制，因此 \(|x_1\rangle\) 的值始终不变。
综合上面的两点考虑，\(\mathrm{CNOT}_{x_1, x_3}\) 的位置在这个门路中是可以任意交换。
但我们也必须要说明，\(\mathrm{CNOT}_{x_1, x_2}\) 与 \(\mathrm{CNOT}_{x_2, x_3}\) 在门路中不可以交换。这个由读者自行验证吧。一般来说，如果一个量子比特同时可能作为控制比特出现，也被单量子比特算符作用或作为目标比特作用，那么这些算符之间不可交换。
引理二：对角算符在受控门路下的平移¶
我们之前说到，一般来说，不是所有算符都可以与 CNOT 的控制部分作对换。一个简单的例子会是
但我们马上会证明下述结论。对于任意的对角矩阵 \(\Lambda\) 与受控 \(A\) 门路 (未必要求是酉矩阵)，其门路满足下式
既然 \(\Lambda\) 是对角矩阵，那么它一定能通过参数 \(\lambda_0, \lambda_1 \in \mathbb{C}^2\) 表示：
那么
练习 4.23¶
练习 4.23
仅用受控非门和单量子比特门构造一个 \(U = R_x(\theta)\) 和 \(U = R_y(\theta)\) 的 \(C^1(U)\) 门。你能够把所需的单量子比特门的数量减到三个或两个吗？
我们先构造较为简单的受控 \(R_y(\theta)\)。回顾练习 4.7，我们有
因此，我们构造下述矩阵拆分：
其中，\(\alpha = 0\)、\(A = I\)、\(B = R_y(-\theta/2)\)、\(C = R_y(\theta/2)\)。容易证明 \(ABC = I\)。因此，
类似地，我们也能得到 \(R_z (\theta) = X R_z (-\theta) X\)。但我们还能同时得到另一个结论：
证明过程很简单。套用式 (4.4, 4.6, 4.18)，可以得到
基于上述结论，以及仿照 \(R_y\) 的矩阵拆解
我们立即可以得到
其中，\(\alpha = 0\)、\(A = H\)、\(B = R_z(-\theta/2)\)、\(C = R_z(\theta/2) H\)。同样容易证明 \(ABC = I\)。因此，
练习 4.24¶
练习 4.24
验证图 4.9 所实现的 Toffoli 门。
我们这里采用与原来书中稍有不同的记号。我们令
它具有性质 \(V^2 = X\)。
V = 0.5 * (1 + 1j) * (I - 1j * X)
V
array([[0.5+0.5j, 0.5-0.5j],
[0.5-0.5j, 0.5+0.5j]])
np.allclose(V.conj() @ V.conj(), X)
True
可以验证 \(V\) 具有如下分解：
A = H @ T
B = T.conj().T
C = H
α = np.pi / 4
np.allclose(np.exp(1j * α) * A @ X @ B @ X @ C, V)
True
那么依据练习 4.22 的结论，我们立即能得到
上图与待证的图 4.9 在线路图的第一、二行上稍有差别。第一行依据练习 4.22 的引理二，容易知道其实是等价的，即第一行的 \(T\) 门位置并不重要。对于第二行，我们需要表明 (下图中的 \(S = T^2\))
第一个量子比特是控制比特，等式左右当然是相等的。我们要分别考察第二个目标量子比特在第一个比特为 \(|0\rangle, |1\rangle\) 时的行为。对于控制量子比特为 \(|0\rangle\) 时，上图的等式证明问题就化为
这个结论是比较显然的，等式左右为恒等算符。
np.allclose(
T.conj().T @ T,
S @ T.conj().T @ T.conj().T)
True
控制量子比特为 \(|1\rangle\) 时，上图的等式证明就化为
np.allclose(
X @ T.conj().T @ X @ T,
S @ X @ T.conj().T @ X @ T.conj().T)
True
因此，上图的等式成立。到这里，我们就借着练习 4.22 的结论，完成了 Toffoli 门的证明。
练习 4.25 (Fredkin 门的构造)¶
练习 4.25
回忆 Fredkin (受控交换，controlled-swap) 门进行的运算：
给出使用三个 Toffoli 门构造的 Fredkin 门 (提示：想想这个交换门的结构——可以每次控制一个门)。
证明第一个和最后一个 Toffoli 门可以用受控非门代替。
用图 4.8 所示线路代替中间的 Toffoli 门，来得到仅用 6 个双量子比特门所构造的 Fredkin 门。
有更简单的仅用 5 个双量子比特门的结构吗？
第一问
首先我们要验证交换门路：
我们假设态处于 \(|x_1\rangle |x_2\rangle\)，其中 \(x_1, x_2 \in \{0, 1\}\)。那么
经过第一个 CNOT，得到 \(|x_1\rangle |x_2 \oplus x_1\rangle\)；
经过第二个 CNOT，得到 \(|x_1 \oplus (x_2 \oplus x_1)\rangle |x_2 \oplus x_1\rangle = |x_2\rangle |x_2 \oplus x_1\rangle\)；
经过第三个 CNOT，得到 \(|x_2\rangle |(x_2 \oplus x_1) \oplus x_2\rangle = |x_2\rangle |x_1\rangle\)；
这就将 \(|x_1\rangle |x_2\rangle\) 转换到了 \(|x_2\rangle |x_1\rangle\)。
因此，受控交换门只是再加上了一个控制节点而已：
第二问
这一问答案是
比较正常的解法会是对该算符考察其真值表 (原书中图 3.15)。当然，我们也可以用数学的语言来证明。上图的三量子比特下的 CNOT 门 (等式右的左右两个门路) 可以写为 \(I \otimes \mathrm{CNOT}\)，而等式右的中间 Toffoli 门表示为 \(I^{\otimes 3} + P_1 \otimes (X-I) \otimes P_1\)。我们需要证明的是
ctrl_12_X = np.kron(I, ctrl_1_X)
ctrl_13_toff = np.eye(8) + np.kron(np.kron(P1, X-I), P1)
ctrl_12_X @ ctrl_13_toff @ ctrl_12_X
array([[1., 0., 0., 0., 0., 0., 0., 0.],
[0., 1., 0., 0., 0., 0., 0., 0.],
[0., 0., 1., 0., 0., 0., 0., 0.],
[0., 0., 0., 1., 0., 0., 0., 0.],
[0., 0., 0., 0., 1., 0., 0., 0.],
[0., 0., 0., 0., 0., 0., 1., 0.],
[0., 0., 0., 0., 0., 1., 0., 0.],
[0., 0., 0., 0., 0., 0., 0., 1.]])
上述的计算结果与题目所给出的 Fredkin 门矩阵表示完全一致。
第三问
由于交换算符的对称性，门路的第二、三行可以互相交换。为了方便起见，我们交换这两行，并代入图 4.8：
第四问
这里需要利用到一些对易关系。首先，利用到 \(V V^\dagger = V^\dagger V = I\) 的对易关系，可以表明左数第 6 个门路与左数 3, 4, 5 门路可以交换。因此，
随后利用到 \([X, X] = 0\) 的关系，右数第 1, 2 个门路可以对易。因此，
上图中的五个蓝色虚线框，就是题目所要求的 5 个双量子比特门路。
本题的参考资料是
https://journals.aps.org/pra/abstract/10.1103/PhysRevA.53.2855
练习 4.26¶
练习 4.26
证明如下线路
与 Toffoli 门的差别仅是相对相位。即该线路把 \(|c_1, c_2, t\rangle\) 变为 \(e^{i \theta(c_1, c_2, t)} |c_1, c_2, t \oplus c_1 c_2\rangle\)，其中 \(e^{i \theta(c_1, c_2, t)}\) 是某个相对相位因子。这类门在实验实现中有时有用，它可以实现除了一个相对相位外与 Toffoli 门相同的门，但比直接实现 Toffoli 门容易得多。
本题使用练习 4.21 的解法会比较方便。我们同时回顾到练习 4.7 的结论 \(X R_y(\theta) X = R_y(-\theta)\) 以及 \(X^2 = 1\)。那么，我们考察不同的 \(c_1, c_2\) 下，第三行算符的实际作用 (注意算符图上线路的顺序与矩阵乘法顺序是反过来的)：
这里比较特殊的是 \((c_0, c_1) = (1, 0)\) 的情况。该控制门路的作用是将 \(|t\rangle\) 变为 \(Z |t\rangle\)，而不是恒等变换。但我们也注意到，\(Z\) 的作用等同于相位门 \(P_\pi = S^2 = T^4\)。因此，对于这种特殊情况，确实可以认为是相差一个相位；但这个相位是 \(|t\rangle\) 中 \(|0\rangle\) 与 \(|1\rangle\) 的贡献分量相位之区别，而不是全局相位 \(e^{i \theta(c_1, c_2, t)}\)。因此我倾向于认为，题目的问法是错的。
练习 4.27¶
练习 4.27
仅用受控非门和 Toffoli 门，来构造一个执行如下变换的量子线路。
这类部分循环置换 (cyclic permutation) 运算将在后面第 7 章用到。
很遗憾的是，这道题的答案目前还是凑出来的。但是我们至少可以验证下述结果。
仍然按照练习 4.21 的做法，对每个可能的波函数进行讨论：
上表满足题目所要求的循环置换的矩阵表示结果。
我们也可以利用 Python 代码结合 Qiskit 实现。但需要注意，由于原书中的量子比特记号约定是 \(|x_1 x_2 x_3\rangle\)，但在 Qiskit 中则是 \(|x_3 x_2 x_1\rangle\)，因此为了得到与书中相同的矩阵表示，我们需要额外增加两个 SWAP 门路。作为答案的线路，在下图中是被灰色虚线所围起来的线路。
circ = QuantumCircuit(3)
circ.swap(0, 2)
circ.barrier()
circ.toffoli(1, 2, 0)
circ.cnot(2, 1)
circ.cnot(1, 2)
circ.cnot(0, 1)
circ.toffoli(0, 1, 2)
circ.cnot(0, 1)
circ.barrier()
circ.swap(0, 2)
circ.draw()
我们可以用下述代码，打出其矩阵表示。可以发现，该矩阵表示结果与题目要求完全相同。
np.asarray(Operator(circ).data, dtype=int)
array([[1, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 1],
[0, 1, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 1, 0]])
但本题最为直观的构造方式是，先对量子比特作加法，随后若 \(|x_1 x_2, x_3\rangle = |00, x_3\rangle\)，那么将其变换为 \(|00, x_3\oplus1\rangle\)。其实际操作过程非常直观：
加法的线路构造思路是，需要在 \(|x_3\rangle\) 引入 \(X\) 算符以实现 \(|x_3 \oplus 1\rangle\)，随后小心地通过引入控制门路以作合适的进位。
控制部分 \(|x_1 x_2, x_3\rangle = |00, x_3\rangle\) 线路，实际上就是以 \(|x_1 x_2\rangle = |00\rangle\) 来控制的 Toffoli 线路；我们回顾到先前定义的所有 Toffoli 线路都是以 \(|x_1 x_2\rangle = |11\rangle\) 控制的；因此，依照书中的图 4.11 或图 4.12，可以给出该控制线路。
下图的蓝色区域即是加法线路，橙色区域即是控制线路。该线路也是本题的一个解，且构造思路清晰；但由于包含了单量子比特 \(X\) 门路，因此并不满足题目的要求。
练习 4.28¶
练习 4.28
对于 \(U = V^2\)，其中 \(V\) 是酉的，使用类似于图 4.10 的方式构造 \(C^5 (U)\) 门，但不用工作量子比特，可以使用受控 \(V\) 门与受控 \(V^\dagger\) 门。
危险
本题无解。无解性的证明思路是作行列式值分析。详细的理由请参考
https://cs.stackexchange.com/a/138853/141343
如果我们允许多控制节点的非门或 \(V\) 门，那么 \(C^5 (U)\) 门是可以构造出来的：
同时，若定义 \(U = V^{16}\)，那么该练习也是可以完成的，但线路恐怕会非常复杂。
练习 4.29, 4.30¶
练习 4.29
不使用工作量子比特，求出一个包含 \(O(n^2)\) Toffoli 门、受控非门和单量子比特门的可实现 \(C^n(X)\) 门 (\(n > 3\)) 的线路。
练习 4.30
设 \(U\) 是一个单量子比特酉运算，不使用工作量子比特，求一个包含 \(O(n^2)\) Toffoli 门、受控非门和单量子比特门，实现 \(C^n (U)\) 门 (\(n>3\)) 的线路。
警告
这两个问题不在此作证明。
可以参考下述文献的 Corollary 7.6。尽管证明过程还算比较直观，但需要引入许多符号，证明过程也比较长。
https://arxiv.org/abs/quant-ph/9503016
同时需要指出，对于任意 \(n > 5\)，如果允许一个工作量子比特，那么依据 Corollary 7.4，多受控非门的门路复杂度可以从 \(O(n^2)\) 降为 \(O(n)\)。从这个角度来说，工作量子比特其实还是非常重要的。工作量子比特在这个问题中，或可能在其它问题中，可以对线路大大作简化。
练习 4.31 (更多的线路恒等式)¶
练习 4.31
令下标表示算符作用的量子比特、并令 \(C\) 是量子比特 1 为控制、量子比特 2 为目标的受控非门。证明如下恒等式：
记号的细化定义¶
我们回顾到 \(C\) 即 CNOT 门，因此
\(X_1\) 是只作用于第一个量子比特的门路，因此
仿上，其它的符号也可以相应地给予定义。
式 (4.32)¶
上式中，我们利用了 \(P_0 X P_1 + P_1 X P_0 = I\) 以及 \(P_0 X P_0 = P_1 X P_1 = 0\)。这些可以通过矩阵乘法简单地验证，当然也可以用 \(Z, I\) 的表达式展开 \(P_0, P_1\) 来求解。
式 (4.33)¶
上式中，我们利用了 \(P_0 Y P_1 + P_1 Y P_0 = Y\) 以及 \(P_0 Y P_0 = P_1 Y P_1 = 0\)。
式 (4.34)¶
上式中，我们利用了 \(P_0 Z P_0 + P_1 Z P_1 = Z\) 以及 \(P_0 Z P_1 = P_1 Z P_0 = 0\)。
式 (4.35)¶
上式中，我们利用了 Pauli 矩阵所具有的性质 \(X^2 = Y^2 = Z^2 = I\)、投影算符的幂等性 \(P_0^2 = P_0\) 及 \(P_1^2 = P_1\)，和投影算符性质 \(P_0 + P_1 = I\)。
式 (4.36)¶
上式中，我们利用了 \(Z\) 在投影算符下的展开 \(Z = P_0 - P_1\)，以及一个恒等式 \(X Y X = iZX = i^2 Y = -Y\)。
式 (4.37)¶
上式中，我们利用了一个恒等式 \(X Z X = iXY = i^2 Z = -Z\)。
4.4 测量¶
import numpy as np
np.set_printoptions(4, suppress=True)
vec0 = np.array([1, 0])
vec1 = np.array([0, 1])
I = np.eye(2)
X = np.array([[0, 1], [1, 0]])
H = 1/np.sqrt(2) * np.array([[1, 1], [1, -1]])
P0 = np.outer(vec0, vec0)
P1 = np.outer(vec1, vec1)
练习 4.32¶
练习 4.32
设 \(\rho\) 是描述双量子系统的密度矩阵。假设在计算基中执行对第二个量子比特的测量，令 \(P_0 = |0\rangle\langle0|\) 和 \(P_1 = |1\rangle\langle1|\) 分别是第二个量子比特上到状态 \(|0\rangle\) 和 \(|1\rangle\) 的投影。令 \(\rho'\) 是测量后，由一个不了解测量结果的观测者分配给系统的密度矩阵。证明
再证明第一量子比特的约化密度矩阵不受测量的影响，即 \(\mathrm{tr}_2 (\rho) = \mathrm{tr}_2 (\rho')\)。
警告
记号重新定义
首先我们沿用题目所给的记号 \(\rho, \rho' \in \mathbb{C}^4\)。我们认为 \(P_0, P_1 \in \mathbb{C}^2\) 是单量子比特算符。因此，实际的算符作用是在 \(\mathbb{C}^4\) 的双量子比特空间下完成。因此，待证等式应当是
这个等式看起来比较丑陋，但我想应该更合适一些。
测量定义回顾
我们需要先对基于投影算符的测量作回顾 (这本书也会提到基于 POVM 的测量，但我们希望把问题弄得简单一些)。对于 \(\mathbb{C}^2\) 下的量子比特 \(|\psi\rangle\)，测量得到态 \(|m\rangle\) 态的过程，使用算符作用的方式可以写为式 (2.104) 形式
其中，\(P_m = |m\rangle\langle m|\) 是投影算符，\(p_m = \langle \psi | P_m | \psi \rangle\) 是测量得到态 \(|m\rangle\) 的概率。
作为测量的结果的态的密度算符为
单量子比特测量后的密度矩阵
但是现在假使我们不知道测量的结果 (即不清楚到底投影到了 \(|0\rangle\) 还是 \(|1\rangle\))。但我们从 \(|\psi\rangle\) 的结构，应当能了解投影到 \(|0\rangle\) 和 \(|1\rangle\) 的概率分别为 \(p_0\) 和 \(p_1\)。那么此时，我们就依概率将两个密度算符加起来：
这就是单个粒子下，在我们不知道测量结果时，测量后体系的密度矩阵了。
我们考察一个实际的例子。若 \(|\psi\rangle\) 在计算基下的向量用下述程序表示为变量 v (通过随机数生成)，那么其密度矩阵 \(|\psi\rangle \langle\psi|\) 则可以用 rho_v：
v = np.random.randn(2) + np.random.randn(2) * 1j
v /= np.linalg.norm(v)
v
rho_v = np.outer(v.conj(), v)
rho_v
array([[0.8616+0.j , 0.2185-0.2675j],
[0.2185+0.2675j, 0.1384+0.j ]])
在 \(P_0 |\psi\rangle \langle\psi| P_0 + P_1 |\psi\rangle \langle\psi| P_1\) 作用下，只有对角元留了下来：
P0 @ rho_v @ P0 + P1 @ rho_v @ P1
array([[0.8616+0.j, 0. +0.j],
[0. +0.j, 0.1384+0.j]])
双量子比特测量后的密度矩阵
双量子比特的情形是类似的。既然我们的测量对第一个量子比特没有作修改，那么对于比特 \(|\phi\psi\rangle = |\phi\rangle \otimes |\psi\rangle\) 测量得到态 \(|\phi m\rangle\) 可以用算符表示为
若我们不知道到底测量后得到了什么态，则这个状态的密度矩阵表示为
又，依据题目的记号，测量前的态 \(|\phi\psi\rangle\) 对应的密度矩阵是 \(\rho\)，那么就意味着 \(\rho = |\phi\psi\rangle \langle\phi\psi|\)；而上面的表达式是测量后的密度矩阵 \(\rho'\)，那么
偏迹求取
随后，我们要求取 \(\rho'\) 与 \(\rho\) 的偏迹。\(\rho\) 不能写为简单的两个 \(\mathbb{C}^2\) 算符的直积；但它总可以表示为这种直积的线性组合。即，必然存在一系列 \(\mathbb{C}^2\) 空间下的算符 \(\{ \sigma_k, \varsigma_k \}\)，使得 \(\rho\) 可以写为下述形式：
那么，
我们对上式的其中一部分求迹：
上式成立的原因可以看讨论单量子比特测量后密度矩阵的时候，我们说 \(P_0 \varsigma_k P_0 + P_1 \varsigma_k P_1\) 的作用是保留 \(\varsigma_k\) 的对角元，而将所有非对角元剔除。在这个操作下，迹没有发生变化。
因此，\(\rho'\) 的偏迹可以写为
例子：Bell 态
对于其中一个 Bell 态，在计算基下的向量和其对应的密度矩阵是
vec_bell = np.array([1, 0, 0, 1]) / np.sqrt(2)
rho_bell = np.outer(vec_bell.conj(), vec_bell)
rho_bell
array([[0.5, 0. , 0. , 0.5],
[0. , 0. , 0. , 0. ],
[0. , 0. , 0. , 0. ],
[0.5, 0. , 0. , 0.5]])
对第二个粒子测量后，若不知道测量结果，则该态的密度矩阵是
rho_measured = np.kron(I, P0) @ rho_bell @ np.kron(I, P0) + np.kron(I, P1) @ rho_bell @ np.kron(I, P1)
rho_measured
array([[0.5, 0. , 0. , 0. ],
[0. , 0. , 0. , 0. ],
[0. , 0. , 0. , 0. ],
[0. , 0. , 0. , 0.5]])
偏迹的计算说明如下。实际上，双量子比特下的算符 \(A\) 应当是 \(\mathbb{C}^{2 \times 2 \times 2 \times 2}\) 空间下的张量；但为了书写与程序编写的方便，通常我们将其表示为 \(\mathbb{C}^{4 \times 4}\) 矩阵。实际上，它应当表述为
总地来说，张量 \(A\) 的元素可以用 \(A_{\alpha_1 \beta_1 \alpha_2 \beta_2}\) 表示；\(\alpha\) 和 \(\beta\) 分别与第一个和第二个量子比特有关，而写为矩阵时则合并角标 \(\alpha_1 \beta_1\) 与 \(\alpha_2 \beta_2\) 得到 \(A_{(\alpha_1 \beta_1), (\alpha_2 \beta_2)}\)。
现在我们的目标是求第二个量子比特的偏迹，那么做法是把与第二个量子比特有关的角标 \(\beta_1, \beta_2\) 作求和 (\(\delta_{\beta_1 \beta_2}\) 是 Kronecker Delta 函数)：
偏迹的求取在 Python 下不是难事；先将 \(4 \times 4\) 矩阵转换为 \(2 \times 2 \times 2 \times 2\) 张量，随后对 \(\beta_1, \beta_2\) 角标求迹即可。我们可以得到
rho_bell.reshape(2, 2, 2, 2).trace(axis1=1, axis2=3)
array([[0.5, 0. ],
[0. , 0.5]])
rho_measured.reshape(2, 2, 2, 2).trace(axis1=1, axis2=3)
array([[0.5, 0. ],
[0. , 0.5]])
练习 4.33 (在 Bell 基中的测量)¶
练习 4.33
我们对量子线路规定的测量模型限于计算基。然而，我们常在其它标准正交状态定义的基中执行测量。为执行这样的测量，只需要从我们希望在其中进行测量的基，酉变换到计算基，再进行测量。例如，证明图
执行了在 Bell 态下的测量。更精确地，证明这个线路导致相应的 POVM 元是到四个 Bell 态的投影的测量，并求出相应的测量算符是什么。
直观的分类讨论
我们让初态是 Bell 态，代入上述线路图的测量部分前，可以知道该线路的作用是
譬如我们测量得到了 \(|10\rangle\)，那么我们就知道，代入 CNOT 与 H 门之前，两个量子比特的状态是 Bell 态 \((|00\rangle - |11\rangle) / \sqrt{2}\)。这就对原来的题目作了证明。
POVM 元的讨论
上述的讨论其实是很严格的。但题目可能认为，使用算符的语言也可以作证明，并且更为精确，因此要求对 POVM 作讨论。
为了讨论方便，我们定义 \(\mathrm{CNOT}, H_1, P_{mn} \in \mathbb{C}^{4 \times 4}\) 是双量子比特算符，其中 \(m, n \in \{0, 1\}\) 表示计算基角标，
那么该线路所代表的测量算符相当于 \(M_{mn} = P_{mn} H_1 \mathrm{CNOT}\)。需要注意，既然它是测量算符，那么其作用于双量子比特态 \(|\Phi\rangle \in \mathbb{C}^2\) 后，得到的态应该要归一化：
注意上述测量算符 \(M_{mn}\) 与投影算符 \(P_{mn}\) 都作用于 \(|\Phi\rangle\) 得到了 \(|mn\rangle\)，但由于测量得到的概率不同即 \(\langle \Phi | M_{mn}^\dagger M_{mn} | \Phi \rangle \neq \langle \Phi | P_{mn}^\dagger P_{mn} | \Phi \rangle\)，因此还是有区别的。该算符的 POVM 是
上式我们用到了 \(\mathrm{CNOT}, \mathrm{H}_1, P_{mn}\) 的自伴算符与其自身相同的性质、以及 \(P_{mn}\) 作为投影算符的幂等性。
我们具体分析 \((m, n) = (1, 0)\) 的情况。在计算基下，POVM 算符 \(E_{10}\) 的矩阵表示可以计算得
CNOT = np.kron(P0, I) + np.kron(P1, X)
H1 = np.kron(H, I)
P10 = np.kron(P1, P0)
E10 = CNOT @ H1 @ P10 @ H1 @ CNOT
E10
array([[ 0.5, 0. , 0. , -0.5],
[ 0. , 0. , 0. , 0. ],
[ 0. , 0. , 0. , 0. ],
[-0.5, 0. , 0. , 0.5]])
我们再考察对于 Bell 基的其中一个态以及其在计算基下的向量表示：
其密度矩阵，即其测量算符 (定义)，即其 POVM (幂等性)，事实上等价于 POVM 算符 \(E_{10}\)：
vec = np.array([1, 0, 0, -1]) / np.sqrt(2)
np.outer(vec.conj(), vec)
array([[ 0.5, 0. , 0. , -0.5],
[ 0. , 0. , 0. , -0. ],
[ 0. , 0. , 0. , -0. ],
[-0.5, -0. , -0. , 0.5]])
np.linalg.det(CNOT @ H1 @ P10 @ H1 @ CNOT)
0.0
对于其它的情况，我们也一样能证明，该线路下的任何测量的 POVM 算符，总能对应到其中一个 Bell 态测量算符的 POVM。结论得证。
练习 4.34 (测量一个算符)¶
练习 4.34
设我们有一个具有特征值 \(\pm 1\) 的单量子比特上的算符 \(U\)，于是 \(U\) 既是 Hermite 的又是酉的，故可以看作既是一个可观测量又是一个量子门。假设我们希望测量可观测量 \(U\)，即我们希望获得指示两个特征值之一的测量结果，并将测量后的状态带到相应的特征向量。用一个量子线路如何实现？证明下面的线路实现了一个测量。
我们分析双量子比特 \(|0\rangle \otimes |\psi_\mathrm{in}\rangle\) 进入线路到测量之前的变化过程：
那么若测量第一个量子比特
得到 \(|0\rangle\)，那么 \(|\psi_\mathrm{out}\rangle\) 在不考虑归一化时，等于 \((I + U) |\psi_\mathrm{in}\rangle\)；
得到 \(|1\rangle\)，那么 \(|\psi_\mathrm{out}\rangle\) 在不考虑归一化时，等于 \((I - U) |\psi_\mathrm{in}\rangle\)。
下面考察一个有意思的现象。我们令算符 \(U\) 的两个本征态是 \(|a\rangle\) 与 \(|b\rangle\)，根据题意，令它们分别对应的本征值为 \(\lambda_a = 1, \lambda_b = -1\)；那么对于任意 \(|\psi_\mathrm{in}\rangle\)，总可以写为这两个线性无关本征态的线性叠加 (为了讨论方便，我们额外对 \(|\psi_\mathrm{in}\rangle\) 作要求 \(\alpha, \beta \neq 0\) 以避免零波函数输出)：
因此，
这意味着，若测量第一个量子比特
得到 \(|0\rangle\)，那么 \(|\psi_\mathrm{out}\rangle = |a\rangle\)；
得到 \(|1\rangle\)，那么 \(|\psi_\mathrm{out}\rangle = |b\rangle\)。
这相当于对第二个线路的算符进行了“测量”。
练习 4.35 (与控制可交换的测量)¶
练习 4.35
推迟测量原理的一个结论是，当被测量量子比特是一个量子门的控制量子比特时，测量量子比特和量子门可以交换，即
(在图中双线代表经典比特) 证明第一个等式。右边的等式只是为了方便，测量结果以经典方式控制量子门的符号来表示。
我们令输入到线路的双量子比特态为
其中，\(k, l \in \{0, 1\}\)。我们暂且不对测量过程之后的态进行归一化 (归一化前后的态代表相同的物理实在)。那么对于第一个线路，若对第一个量子比特测量得到态 \(|a\rangle \in \{|0\rangle, |1\rangle\}\)，
对于第二个线路，则是
注意到 \(P_a\) 是计算基下的投影算符，即 \(P_a \in \{ P_0, P_1 \}\)。由于 \(P_0, P_1\) 之间可对易即 \(P_0 P_1 = P_1 P_0\)，因此上两式中的 \(P_a\) 与 \(P_0, P_1\) 可对易，上述两个线路的结果其实是等价的。
4.5 通用量子门¶
import numpy as np
from functools import reduce
np.set_printoptions(4, suppress=True, linewidth=150)
# Vector in computational basis
vec0 = np.array([1, 0])
vec1 = np.array([0, 1])
# Matrices in computational basis
I = np.eye(2)
X = np.array([[0, 1], [1, 0]])
Z = np.array([[1, 0], [0, -1]])
H = 1/np.sqrt(2) * np.array([[1, 1], [1, -1]])
T = np.array([[1, 0], [0, np.exp(1j*np.pi/4)]])
S = T @ T
P0 = np.outer(vec0, vec0)
P1 = np.outer(vec1, vec1)
练习 4.36¶
练习 4.36
构造一个把双比特数 \(x\) 和 \(y\) 进行模 4 加的量子线路，即线路可以完成 \(|x, y\rangle \rightarrow |x, (x+y) \text{ mod } 4\rangle\) 的变换。
我们定义下述四个单量子比特数 \(a, b, c, d, e, f \in \{0, 1\}\)，并定义 \(|x\rangle = |ab\rangle, |y\rangle = |cd\rangle\)。题目所要求的线路是从 \(|abcd\rangle \rightarrow |abef\rangle\) 的变换。
题目要求的 \(ef\) 是二进制下的 \((ab+cd) \text{ mod } 4\) (这里 \(ab\) 表示的不是乘法，而是二进制数 \(a \times 2 + b\))。根据进位原则，
这两步操作分别在下述线路图中用蓝色与橙色框表示。
练习 4.37¶
练习 4.37
求变换
的一个两级酉矩阵分解。这是量子 Fourier 变换的一个特例，下一章将作仔细研究。
作为量子 Fourier 变换的分解
我们采用图 5.1 的结论，可以立即得到待求的 \(U\) 就是下述线路：
用数学的语言表述的话，是
U = 0.5 * np.array([
[1, 1, 1, 1],
[1, 1j, -1, -1j],
[1, -1, 1, -1],
[1, -1j, -1, 1j]
])
swap = np.array([[1, 0, 0, 0], [0, 0, 1, 0], [0, 1, 0, 0], [0, 0, 0, 1]])
np.allclose(swap @ np.kron(I, H) @ (np.kron(I, P0) + np.kron(S, P1)) @ np.kron(H, I), U)
True
上式中，受控 \(S\) 算符和 SWAP 算符都是二级酉矩阵，但作用于单量子比特的 \(H\) 算符则还需要进一步展开。因此，我们写出下述线路：
\(U = U_1^\dagger U_2^\dagger U_3^\dagger U_4^\dagger U_5^\dagger U_6^\dagger\) 的每个矩阵可以写为
验证上述计算过程的代码如下：
U_list_fourier = [
swap,
np.kron(P1, I) + np.kron(P0, H),
np.kron(P0, I) + np.kron(P1, H),
np.kron(I, P0) + np.kron(S, P1),
np.kron(I, P1) + np.kron(H, P0),
np.kron(I, P0) + np.kron(H, P1),
]
np.allclose(reduce(np.dot, U_list_fourier), U)
True
标准做法
上面是从第 5 章已经知道答案的情况下，对答案进行验证的过程。但这一节所给的标准做法是不断地消去非对角元。这个过程是非常清晰的，可以通过简单的程序直接给出。需要指出，最后一个矩阵的处理方式会稍微有些特别。
def generate_two_level_unitary(M, axis1, axis2):
"""
Input unitary matrix M, and give the matrix element position
you want to set U.dot(M)[axis1, axis2] == 0,
Output the desired two-level unitary matrix U.
"""
U = np.eye(M.shape[0], dtype=M.dtype)
a = M[axis2, axis2]
b = M[axis1, axis2]
r = np.linalg.norm([a, b])
U[axis1, axis1] = - a / r
U[axis1, axis2] = b / r
U[axis2, axis1] = np.conj(b) / r
U[axis2, axis2] = np.conj(a) / r
return U
def generate_two_level_decompose(M):
"""
Input unitary matrix M
Output two-level unitary matrix decomposition list U_list
"""
dim = M.shape[0]
M_proc = M
U_list = []
# first (d-2) columns: regular process
for j in range(dim-2):
for i in range(j+1, dim):
U = generate_two_level_unitary(M_proc, i, j)
U_list.append(U.conj().T)
M_proc = U @ M_proc
# last transformation: special treatment
U_last = np.eye(dim, dtype=M_proc.dtype)
U_last[-2:, -2:] = M_proc[-2:, -2:]
U_list.append(U_last)
return U_list
下面的程序可以给出题目所要求的二级酉矩阵。该结果比较复杂，但也是正确的。
U_list = generate_two_level_decompose(U)
np.allclose(reduce(np.dot, U_list), U)
True
\(U = U_1^\dagger U_2^\dagger U_3^\dagger U_4^\dagger U_5^\dagger U_6^\dagger\) 的每个矩阵可以写为
练习 4.38¶
练习 4.38
证明存在 \(d \times d\) 酉矩阵 \(U\)，它不能分解为少于 \(d-1\) 个两级酉矩阵的乘积。
简单的 \(d=3\) 的情况
首先我们考察容易分析的情况。对于 \(d = 3\)，如果一个矩阵可以由 2 个两级矩阵所表示，那么不妨令
那么
我们能发现，其中一个元素的值为零。事实上，不论两级矩阵的“两级”在 \(3 \times 3\) 的哪一个子矩阵中，2 个这种两级矩阵相乘总会有一个元素是零。这与矩阵是否是酉的其实没有关系。
依据这个认识，我们对任何的 \(d \geqslant 3\) 作证明。
待证问题
对于 \(d \times d\) 的矩阵 \(U\)，不存在分解 \(U = M^1 M^2 \cdots M^{d-1}\)，使得 \(U\) 的每个元素非零。其中，\(M^1, M^2, \cdots, M^{d-1}\) 是两级矩阵。
定义补充
我们作一些符号的定义。这段证明全部采用 1-索引，即起始角标为 1。我们不考虑矩阵是否是酉的。
对于 \(\mathbb{C}^{d \times d}\) 空间，我们定义一系列两级矩阵 \(M^1, M^2, \cdots, M^n\)。需要注意，这里的上标并非是幂次，而是标识矩阵的上角标；这是由于我们需要使用到下角标标识矩阵的具体元素。这个证明不需要使用矩阵幂次。
我们同时定义，各两级矩阵的子矩阵角标集合是 \(\sigma_1, \sigma_2, \cdots, \sigma_n\)。。举例而言，若 \(\sigma_1 = \{1, 3\}\)，那么两级矩阵 \(M^1\) 必然可以写为下述形式：
即元素 \(M^1_{11}, M^1_{13}, M^1_{31}, M^1_{33}\) 可以是任意值；而其它情况下，只有对角线元素为 1，否则为零。
证明过程
反证法。现在我们假设存在 \(M^1, M^2, \cdots, M^{d-1}\)，使得 \(U = M^1 M^2 \cdots M^{d-1}\)，且 \(U\) 的每一个元素非零。因此，指标集合 \(\sigma_1, \sigma_2, \cdots, \sigma_{d-1}\) 也是确定的。那么对于任意角标 \(k, l \in \{1, 2, \cdots, d\}\)，依据矩阵乘法定义，有
为了让 \(U_{kl}\) 不为零，我们要保证至少存在一组 \(\{i_1, i_2, \cdots, i_{d-2}\}\)，使得
我们令 \(S_n\) 是满足上式的 \(i_n\) 可能取值的集合。令记号 \(\mathscr{S}_l\) 是 \(l\) 可能取值的集合。
我们要稍微分析一下这个作用。先考虑 \(M^1_{k i_1} M^2_{i_1 i_2}\) 如何才能是非零的。由于 \(\sigma_1, \sigma_2, \cdots, \sigma_{d-1}\) 是给定的，因此我们总可以找到一个 \(k\)，它满足 \(k \not \in \sigma_1\)。那么 \(i_1\) 必须为 \(k\) 即 \(M^1_{k i_1}\) 必须是 \(M^1_{kk} = 1\)，否则 \(M^1_{k i_1} = 0\)。我们之后一直需要使用这种 \(k\)。
若 \(i_1 \not \in \sigma_2\)，那么 \(i_2\) 必须为 \(i_1\)，理由同上，即否则 \(M_{i_1 i_2} = 0\)；但恰好，\(i_1 = k\)，因此要求了 \(i_2 = k\)；在这种情况下，\(S_2 = \{k\}\)；
若 \(i_1 \in \sigma_2\)，那么 \(i_2\) 可以取 \(i_1\)，也可以取 \(\sigma_2\) 中的另一个元素；在这种情况下，\(S_2 = \{k, i_1, i_2\} = \{k\} \cup \sigma_2\)。但我们指出，\(|S_2| = 2\)，因为 \(k = i_1 \in \sigma_2\)，因此 \(S_2 = \sigma_2\)。
这两种情况都是 \(|S_2| \leqslant 2\)。
随后，我们考察 \(M^1_{k i_1} M^2_{i_1 i_2} M^3_{i_2 i_3}\)。
若 \(i_2 \not \in \sigma_3\)，那么 \(i_3\) 必须取为 \(i_2\)；在这种情况下，\(S_3 = S_2\)；元素数 \(|S_3| = |S_2|\)；
若 \(i_2 \in \sigma_3\)，那么 \(i_3\) 可以取为 \(i_2\)，也可以取为 \(\sigma_3\) 的任何元素。因此 \(S_3 = S_2 \cup \sigma_3\)；但由于 \(\{i_2\} \subseteq \sigma_3 \cap S_2\)，因此
\[ |S_3| = |S_2| + |\sigma_3| - |S_2 \cap \sigma_3| \leqslant |S_2| + 2 - 1 = |S_2| + 1 \]
这两种情况都是 \(|S_3| \leqslant |S_2| + 1 \leqslant 3\)。
以此类推，可知
到 \(M^1_{k i_1} M^2_{i_1 i_2} M^3_{i_2 i_3} \cdots M^{d-1}_{i_{d-2} l}\) 时，我们知道
这就意味着 \(l\) 只可能取 \(d - 1\) 个值；当取到 \(\{1, 2, \cdots, d\} \setminus \mathscr{S}_l \neq \emptyset\) 中的元素时，\(U_{kl}\) 必然为零。因此，对于任意的 \(k \not \in \sigma_1\)，总存在 \(l\)，使得 \(U_{kl} = 0\)。证毕。
练习 4.39¶
练习 4.39
求一个用单量子比特运算和受控非门的量子线路，实现变换
其中 \(\tilde U = \begin{bmatrix} a & c \\ b & d \end{bmatrix}\) 是任意的 \(2 \times 2\) 酉矩阵。
上述变换是从 \(|010\rangle\) 到 \(|111\rangle\) 的非平凡变换。仿照式 (4.59) 与图 4.16，我们写出连接 \(|010\rangle\) 与 \(|111\rangle\) 的 Gray 码：
那么所构成的线路是
练习 4.40¶
练习 4.40
对任意的 \(\alpha\) 和 \(\beta\)，证明
依式 (4.8)，对等式左边的算符部分作如下展开：
使用和差化积，可以得到
因此，
随后我们考察到，将三角函数转换为指数后，
因此，
题目还要求证明式 (4.76)。我们不在这里回顾上下文，只给出证明了。首先，上文曾经表明过，对于很小的 \(\forall \delta > 0\)，
这里与原书稍有不同。我们这里不妨令 \(\theta_{k-j} > 0\)。那么
我们令 \(n = l (k - j)\)。那么，\(R_{\hat n} (\theta)^n = R_{\hat n} (n \theta) = R_{\hat n} \big( l (k-j) \theta \; \mathrm{mod} \; 2 \pi \big) = R_{\hat n} \big( l \theta_{k-j} \; \mathrm{mod} \; 2 \pi \big)\) 与 \(R_{\hat n} (\alpha)\) 中，旋转角度的差具有关系 (注意 \(\hat n\) 作为旋转轴与 \(n\) 作为幂次是两个完全无关的记号)
因此，(注意到 \(\sin x < x\) 在 \(x > 0\) 时恒成立)
题目要求对 \(\forall \varepsilon > 0\) 成立 \(E \big( R_{\hat n} (\alpha) - R_{\hat n} (\theta)^n \big) < \varepsilon / 3\)，那么我们令 \(\delta = \varepsilon / 2\)。依据上面和原文的推导，
证毕。
练习 4.41¶
练习 4.41
本练习和下两个练习通过构造证明 Hadamard 门、相位门、受控非门和 Toffoli 门是通用的。证明下图所示的线路在两个测量输出都是 \(|0\rangle\) 时，把 \(R_z (\theta)\) 运算应用到第三 (目标) 量子比特，其中 \(\cos \theta = 3/5\)；否则把 \(Z\) 应用到目标量子比特。证明两个测量结果都是 \(|0\rangle\) 的概率是 5/8，并说明如何反复使用该线路和 \(Z = S^2\) 门，来让应用 \(R_z (\theta)\) 门的概率接近 1。
我们不妨将测量之前的线路情况描绘一下：
我们可以通过矩阵计算，给出 \(3S + XSX\) 与 \(S - XSX\) 的表达式：
上式的 \(\alpha, \beta\) 是可以求出的。其中，\(\alpha = \pi / 4\)，\(\cos(\beta/2) = 2/\sqrt{5}\) 即 \(\beta = 2 \arccos(2/\sqrt{5})\)。但实际上，我们利用倍角公式，容易知道
意味着 \(\cos \beta = 3/5\)，即 \(\beta = \arccos (3/5)\)。
我们回到线路图上。在测量前，线路给出的三粒子态是
这可以表明，在对前两个量子比特测量后，若忽略全局相位的话，
若测量结果是 \(|00\rangle\)，则第三个量子比特相当于 \(|\psi\rangle \rightarrow R_z(\beta) |\psi\rangle\)；
若测量结果是其它情况，则第三个量子比特相当于 \(|\psi\rangle \rightarrow Z |\psi\rangle\)。
测得 \(|00\rangle\) 的概率是 \((\sqrt{10} / 4)^2 = 5/8\)。这就对原题的第一部分做了证明。
原题的第二部分是利用既定的事实 \(\beta = \arccos(3/5)\) 是 \(2 \pi\) 的无理倍数，表明 Hadamard 门 \(H\)、相位门 \(S\) 和 Toffoli 门可以构造任意旋转角度 \(\theta\) 的 \(R_z (\theta)\)。
我们回顾到教材的正文，事实上，如果对于 \(\beta = \arccos(3/5)\) 下的 \(R_z (\beta)\) 可以稳定地构造出来，那么任意旋转角度的 \(R_z (\theta)\) 就可以通过累次操作 \(R_z (\beta)\) 以任意精度进行逼近。
那么问题化为 \(R_z (\beta)\) 要如何稳定地生成。尽管很低效，但若不考虑全局相位，它可以在上述量子线路实现后测量前两个量子比特，
若前两个量子比特是 \(|00\rangle\)，那么我们就导出第三个量子比特为 \(R_z (\beta) |\psi\rangle\)；
若两个量子比特是其它情况，那么我们对第三个量子比特 \(Z |\psi\rangle\) 再作用一次 \(Z\) 门，使得其回到 \(|\psi\rangle\)；随后重置前两个量子比特为 \(|00\rangle\)，重新代入线路。
它不能保证一次性地将第三个量子比特变成 \(R_z (\beta) |\psi\rangle\)，但多次迭代后，这是可以做到的。
这个过程原则上没有精度损失，但对线路复杂度的讨论会稍有影响。我们说，由于前两个量子比特不为 \(|00\rangle\) 的概率是 \(3/8\)，因此若要通过迭代使得第三个量子比特达到 \(R_z (\beta) |\psi\rangle\)，平均的迭代次数会是
因此，它对线路复杂度的影响其实只是多乘了 2.56 的系数，并不对大 \(O\) 渐进性造成影响。
练习 4.42 (\(\theta\) 的无理性)¶
练习 4.42
设 \(\cos \theta = 3/5\)，我们用反证法证明 \(\theta\) 是 \(2 \pi\) 的无理倍数。
利用 \(e^{i \theta} = (3+4i)/5\) 的事实，证明若 \(\theta\) 是 \(2 \pi\) 的有理倍数，则必存在一个正整数 \(m\)，使得 \((3 + 4i)^m = 5^m\)。
证明对所有 \(m > 0\)，\((3 + 4i)^m = 3 + 4i \; (\text{mod } 5)\) (等号在模 5 余数下成立)，并得出不存在 \(m\)，使得 \((3 + 4i)^m = 5^m\) 的结论。
依据题目假设，若 \(\theta\) 是 \(2 \pi\) 的有理倍数，那么我们可以令倍数为 \(t/m\)，其中 \(m\) 是正整数，\(t\) 是整数。因此，
整理上式立即得到 \((3 + 4i)^m = 5^m\)。
证明后一个结论是简单的数归。这里的模 5 余数是分别针对实部与虚部而言的。首先 \(m = 1\) 时显然成立。那么若对于 \(m=k\) 的情形成立，那么当 \(m = k+1\) 时，就有下述模 5 余数的等式：
因此，对于任意的 \(m > 0\)，\((3 + 4i)^m = 3 + 4i \; (\text{mod } 5)\)；但又由于我们刚才得到 \((3 + 4i)^m = 5^m = 0 \; (\text{mod } 5)\)，因此有理数的假设不成立。得证。
练习 4.43¶
练习 4.43
利用上两个练习的结果证明，Hadamard 门、相位门、受控非门和 Toffoli 门对量子计算是通用的。
我们回顾到教材的正文中，对 Hadamard 门、受控非门和 \(\pi/8\) 门的通用性证明过程大致分为下述步骤 (书中定义的“相位门”其实是 \(S = T^2\)，因此有 \(\pi/8\) 门 \(T\) 就够了)：
对于单量子比特算符，存在一根轴 \(\hat n = (\cos \pi/8, \sin \pi/8, \cos)\) 和一个角度 \(\theta\)，使得仅通过 Hadamard 门、\(\pi/8\) 门就可以表示其旋转 \(R_{\hat n} (\theta)\)；
表明 \(\theta\) 是 \(2 \pi\) 的无理倍数，因此总有办法以任意精度近似任意旋转角度 \(R_{\hat n} (\alpha)\)；
存在第二根与 \(\hat n\) 不平行的轴 \(\hat m\)，使得 \(R_{\hat m} (\theta)\) 也可以仅通过 Hadamard 门、\(\pi/8\) 门就可以表示；因此，任意单量子比特的酉矩阵可以表示；
对于多量子比特，通过 4.5.2 节的说明，任意的二级酉矩阵可以通过受控非门 CNOT 与上面的任意单量子比特结合表示；
进而，通过 4.5.1 节的说明，任意多量子比特的酉矩阵可以通过二级酉矩阵表示。
换到我们当前的问题。我们还没有证明这道题的线路图可以用于表示任意单量子比特；但对于多量子比特，现成的结论都已经有了。因此，我们需要对上面步骤中的第 1、2、3 点作说明。
对于第 1 点，我们在练习 4.41 已经有所证明，只是 \(\hat n\) 与 \(\theta\) 在当前的问题下变为了 \(z\) 轴与 \(\beta = \arccos (3/5)\)。尽管该练习的量子线路不一定一次性地给出 \(R_z (\beta)\)，但通过多次迭代该线路，总是可以生成这个算符的。
对于第 2 点，已经在练习 4.42 证明。
对于第 3 点，我们回顾到书中的式 (4.4), (4.6), (4.18)，我们有
因此，通过 Hadamard 门与题目所给出的线路图，我们不仅可以实现 \(z\) 轴的任意旋转，也可以实现 \(x\) 轴的任意旋转。结合起来，就可以实现任意的 Bloch 球面旋转了，即给出任意的单量子比特酉矩阵。
第 4、5 点都是书中已有的结论了。因此，Hadamard 门、相位门、受控非门和 Toffoli 门对多量子比特门的通用性证明完毕。
练习 4.44¶
练习 4.44
证明只要 \(\alpha\) 是无理的，如下定义的三量子比特门对量子计算就是通用的。
危险
本题我尚不打算进行完整证明。
它实际上表现的是 Deutsch 门的通用性。一些重要的参考资料可以是
http://theory.caltech.edu/~preskill/ph229/notes/chap6.pdf
https://quantumcomputing.stackexchange.com/a/10221/14843
练习 4.45¶
练习 4.45
设 \(U\) 是用 \(H\)、\(S\)、受控非门和 Toffoli 门构造的一个 \(n\) 量子比特线路。证明 \(U\) 具有形式 \(2^{-k/2} M\)，其中 \(k\) 是某个整数，\(M\) 是只有复整数元的 \(2^n \times 2^n\) 矩阵。对以 \(\pi/8\) 门代替 Toffoli 门的情形，重复本练习。
本体不作详细说明。我们只说，\(H\) 可以写为 \(2^{-1/2}\) 与复整数元的矩阵乘积；\(T\) 尽管也可以这么做，但需要额外乘以全局相位；这个全局相位并不重要。剩下的 \(S\)、CNOT 与 Toffoli 门都完全是整数矩阵。因此，它们组合起来的形式自然就是 \(2^{-k/2} M\) 的样子了。
4.7 量子系统的仿真¶
练习 4.46 (量子系统复杂性的指数增长)¶
练习 4.46
令 \(\rho\) 是描述 \(n\) 量子比特状态的一个密度矩阵，证明对 \(\rho\) 的描述需要 \(4^n - 1\) 个独立实数。
警告
我其实不清楚，为何一定要是实数。下面是混合复数与实数的说明。
一种说明方式是，对于 \(n\) 量子比特，其态向量是 \(2^n\) 维度的；那么其构成的矩阵也便是 \(4^n\) 大小的。但由于迹 \(\mathrm{tr} (\rho) = 1\)，因此独立数为 \(4^n - 1\)。
另一种说明方式是，态向量维度是 \(2^n\)；但由于归一化条件受限，因此不考虑全局相位的话，描述一个态的实际变量数是 \(2^n - 1\)。在 \(2^n\) 维空间下，相互正交的态也必然存在 \(2^n\) 个。对于一个系综，这 \(2^n\) 个态各自对应其出现概率，但由于概率之和是 1，因此概率变量数总共是 \(2^n - 1\)。因此，将态变量数与态存在数相乘，再加上概率变量数，得到
练习 4.47¶
练习 4.47
对 \(H = \sum_k^L H_k\)，证明若对所有的 \(j, k\) 都有 \([H_j, H_k] = 0\)，则对所有的 \(t\)，
该练习的证明思路很简单。我们考虑这样的问题：若 \([A, B] = 0\) 即 \(A, B\) 可对易，那么 \(e^{A+B} = e^A e^B\) 是否成立？
显然是成立的。我们将其作 Taylor 展开到两阶，并利用 \(AB = BA\)，有：
我们发现若只展开到二次幂，它们都具有 \(1/2 (A^2 + 2AB + B^2)\) 的形式。注意到这利用了 \(A, B\) 的可对易性质。这对于更高次幂其实都成立。严格的证明尽管与二项式定理基本一致，但过程稍微需要一些功夫。
首先我们化简问题。我们令 \(M_k = -i H_k t\) 是关于 \(t\) 的矩阵；但我们会发现时间 \(t\) 和负系数 \(i\) 在这道题证明中没有什么意义。因此，若 \(M = \sum_k^L M_k\)，那么原先问题化为
同时，另一个题目条件化为了 \([M_j, M_k] = - i t [H_j, H_k] = 0\)。
使用数学归纳法。若 \(A = \sum_k^{L-1} M_k\) 时，等式 \(e^A = \prod_k^{L-1} e^{M_k}\) 成立；那么对于 \(L\) 的情况，我们假设 \(B = M_L\)，那么 \(A = M - M_L\)。若 \(e^M = e^{A+B} = e^A e^B\) 成立，那么一方面，该等式很容易地推广到 \(L=2\) 的情形，归纳法所需要的初始情况得到满足；另一方面，这也符合归纳法对于递增的 \(L\) 的要求。
我们同时考察 \([A, B]\)：
因此，原题化为了下述问题：若 \([A, B] = 0\) 即 \(A, B\) 可对易，那么证明 \(e^{A+B} = e^A e^B\)。这就完成了问题的化简。
我们知道，
那么若下述等式对任意自然数 \(\gamma\) 成立，那么 \(e^{A+B} = e^A e^B\)：
下面我们证明上述等式。实际上这与二项式定理的证明几乎一致。使用数学归纳法。显然 \(\gamma = 0\) 时成立；那么对于 \(\gamma + 1\) 的情况，
利用可对易性，易知
因此，
我们将等是右边的第一个求和角标的 \(\lambda + 1\) 替换为 \(\lambda\)，重新组织求和过程：
对于 \(\lambda = 1, 2, \cdots, \gamma\) 时，
因此，
依据数学归纳法，证明完毕。
练习 4.48¶
练习 4.48
若对于 \(n\) 粒子体系，每个算符 \(H_k\) 最多影响 \(c\) 个粒子，那么这意味着式 (4.97) 中求和上限 \(L\) 至多是关于 \(n\) 的多项式。
题目暗含的意思是在这种情况下，\(L\) 并不随着 \(n\) 呈指数级变化。
这类算符实际上也称为 \(c\) 体算符 (\(c\)-Body Operator)，即作用于 \(c\) 个粒子的算符。在化学中，若体系在 Bohn-Oppenheimer 近似下不受特殊外场扰动，那么只会包含一体算符 (动能、外势能算符) 或二体算符 (电子互斥算符)。
若我们用 \(C_n^c\) 表示组合数，那么对于 \(n\) 粒子体系，\(k\) 体算符至多有 \(C_n^k = n (n-1) \cdots (n-k) < n^k\) 个。因此，
即 \(L\) 是 \(n\) 的多项式。
练习 4.49 (Baker-Campbell-Hausdorf 公式)¶
练习 4.49
证明
并且再证明
需要注意这里不一定有 \([A, B] = 0\) 的条件了。我们首先展开式 (4.105) 的左侧：
再考察式 (4.105) 的右侧并回顾到 \([A, B] = AB - BA\)：
因此，式 (4.105) 在忽略 \(O(\Delta t^3)\) 小量下是等价的。
式 (4.103) 的证明过程仿上，很容易给出。
式 (4.104) 的证明固然也可以仿照 (4.105) 对指数作 Taylor 展开。但我们也可以利用 (4.105) 的结论。我们指出，Baker-Campbell-Hausdorf 公式还可以写成下述形式：
证明过程仿上。我们同时注意到 \([A, B] = - [B, A]\)，因此 (系数 \(i\) 不影响证明)，
上式三次利用了练习 4.47 的推演结论，即若 \([A, B] = 0\) 则 \(e^{A+B} = e^A e^B\)。
练习 4.50¶
练习 4.50
令 \(H = \sum_k^L H_k\)，且定义
证明 \(U_{\Delta t} = e^{- 2 i H \Delta t} + O(\Delta t^3)\)；
利用盒子 4.1 的结果，证明对某个常数 \(\alpha\) 与任意正整数 \(m\)，有
\[ E(U_{\Delta t}^m, e^{-2mi H \Delta t}) \leqslant m \alpha \Delta t^3 \]
第一问
反复套用式 (4.104) 就很容易给出结论：
第二问
简单回顾盒子 4.1 的结论 (4.69)。若序列 \(V_1, V_2, \cdots, V_m\) 用来近似某个门的另一个序列 \(U_1, U_2, \cdots, U_m\)，那么
误差记号 \(E(\cdot, \cdot)\) 中两个参量的顺序是可以交换的。对于这道题，\(V_j\) 全部是 \(U_{\Delta t}\)，\(U_j\) 全部是 \(e^{-2iH \Delta t}\)。因此，
依据误差的定义，
我们可以定义对于任意小的 \(\Delta t > 0\) 都有界，但并不一定是小量的算符 \(D\)，使得 \(U_{\Delta t} - e^{-2i H \Delta t} = D \Delta t^3 + O(\Delta t)^4\)，那么
我们可以定义
因此，在这种定义下，
补充说明
事实上，依据线性代数的结论，\(\alpha\) 取到 \(D\) 的最大本征值的绝对值。但这个 \(D\) 算符与 \(\Delta t\) 无关，且 \(\alpha\) 尽管有界但不是变量，更不是可以取到任意小的误差量。
因此，这个结论其实是表明，若 \(\Delta t\) 足够小，那么采用 \(U_{\Delta t}\) 来近似 \(e^{- 2 i H \Delta t}\) 确实地可以实现任意精度的量子计算仿真。我们令预期的仿真精度是 \(\delta\)，那么在仿真时间长度 \(t\)、单个仿真时间差 \(\Delta t\) 下，我们需要 \(m = t / \Delta t\) 个仿真算符连乘。若我们取仿真时间差是
那么整个过程的仿真总误差是
练习 4.51¶
练习 4.51
构造一个 Hamilton 量
的量子线路，模拟对任意的 \(\Delta t\) 执行酉变换 \(e^{- i \Delta t H}\)。
由于
因此我们将这些分解放入线路图中，可以得到
第五章 量子 Fourier 变换及其应用¶
5.1 量子 Fourier 变换¶
练习 5.1¶
练习 5.1
给出式 (5.2) 定义的线性变换是酉变换的直接证明。
首先，依据该式，可以给出 Fourier 变换的矩阵元 \(F_{jk}\) 可以写为
为了证明该变换是酉变换，我们尝试求取其自伴矩阵 \(F^\dagger\) 与 \(F\) 之间的乘积，以验证是否 \(F^\dagger F = I\)。回顾到自伴矩阵 \(F^\dagger\) 是 \(F\) 的共轭转置。我们对矩阵元 \(jk\) 作考察：
下面要分两种情况考虑。若 \(k = j\)，则上式化为
若 \(k \neq j\)，那么若将 \(e^{2 i \pi (k-j) l / N}\) 看作关于自然数 \(l\) 的数列，那么它是等比数列，且比例 \(\omega\) 是 \(\omega = e^{2 i \pi (k-j) / N}\)。又由于 \(0 \leqslant j, k \leqslant N-1\)，因此易推知 \(0 < |k-j| < N\)，即 \(\omega = e^{2 i \pi (k-j) / N} \neq e^{2 \pi i} = 1\)。因此，该等比数列的求和可以套用公式
但由于 \(k-j\) 是整数，因此 \(\omega^N = e^{2 i \pi (k-j)} = 1\)。因此，当 \(j \neq k\) 时，\((F^\dagger F)_{jk} = 0\)。综上，
练习 5.2¶
练习 5.2
具体计算 \(n\) 量子比特状态 \(|00\cdots0\rangle\) 的 Fourier 变换。
直接套用式 (5.2)，代入 \(j = 0\)，得到
但这里需要说明，首先作为 \(n\) 量子比特状态，因此 \(|k\rangle\) 有 \(2^n\) 种可能构造，因此 \(N = 2^n\)。其次，在原先的式 (5.2) 中，\(|k\rangle\) 代表的是态，而 \(e^{2 i \pi jk / N}\) 中的 \(k\) 是该态对应的、可以用于运算的二进制数。
但这里需要说明，首先作为 \(n\) 量子比特状态，因此 \(|k\rangle\) 有 \(2^n\) 种可能构造，因此 \(N = 2^n\)。其次，在原先的式 (5.2) 中，\(|k\rangle\) 代表的是态，而 \(e^{2 i \pi jk / N}\) 中的 \(k\) 是该态对应的、可以用于运算的二进制数。
我们换一个更具体、且与原题不同的例子。对于 \(|j\rangle = |01\rangle\) 时，其量子比特数 \(n = 2\)，其态对应的数值是 \(j = 1\)，其 Fourier 变换则会是
有时为了方便和简洁起见，会用 \(\omega = e^{\frac{1}{4} 2 i \pi}\) 对上式作记号简化，即 Fourier 变换是
练习 5.3 (经典快速 Fourier 变换)¶
练习 5.3
在一个经典计算机上进行一个包含 \(2^n\) 个复数向量的 Fourier 变换，验证基于式 (5.1) 的直接方法进行 Fourier 变换，需要 \(\Theta (2^{2n})\) 个基本算术运算。验证基于式 (5.4) 的运算方法，算术运算数量降低到 \(\Theta (n 2^n)\) 个。
我们不严格分析 \(\Theta\) 与 \(\text{big-}O\) 的区别，只是大致作讨论。
对于 \(n\) 比特的运算 (即 \(N = 2^n\) 的离散向量 Fourier 变换)
我们若认为 \(j \times k\) 的乘法运算是 \(O(1)\) 的，那么
\(e^{2 i \pi j k / N}\) 的运算是 \(O(1)\) 的；
求和操作 \(\sum_{j=0}^{N-1}\) 需要 \(N=2^n\) 次运算；
我们需要求得 \(y_1, y_2, \cdots, y_N\)，因此一共要求取 \(N=2^n\) 个值。
综上，运算数是 \(2^n \times 2^n \times O(1) = O(2^{2n})\)。但需要指出，若 \(n\) 比特乘法 \(j \times k\) 的运算被认为是 \(O(n)\) 的 (因为我们需要处理类似于 \(j \times k, j \times (k+1)\) 等连续乘法，因此乘法完全可以当作加法来处理；否则不使用加法的话，应该至少是 \(O(n \log n \log \log n)\))，那么运算数应该是 \(O(n 2^{2n})\)。
若使用下式，
构造 \(|0\rangle + e^{2 i \pi \times 0.j_lj_{l+1}\cdots j_n} |1\rangle\) 的时间至多是 \(O(n)\)，且相比后续计算，可以忽略；
乘法表达式还不是 \(N = 2^n\) 个向量分量的线性组合，我们最后还要求线性组合的系数 (相当于式 (5.1) 中的 \(y_k\))；
对于线性组合系数，我们需要进行至多 \(n\) 次或平均 \(n/2\) 次乘法求出，即 \(\Theta (n)\) 次乘法。
因此，运算数是 \(O(n) + 2^n \Theta (n) = \Theta (n 2^n)\)。
练习 5.4¶
练习 5.4
给出受控 \(R_k\) 门到单量子比特门和受控非门的一个分解。
为了解该题，我们要回顾图 4.6。我们需要找到三个算符 \(A, B, C\) 与相位因子 \(\alpha\)，使得 \(R_k = e^{- i \alpha} AXBXC\)，且 \(ABC = I\)。
我们回顾到 \(R_k\) 的表达式
我们回顾到 \(X R_z(\theta) X = R_z (- \theta)\) (可以参考练习 4.7 的证明)，那么
因此，我们可以令
我们若令 \(P_{\alpha}\) 是下述门路：
那么其对应的线路图，依据书中的图 4.6，可以绘制为
练习 5.5¶
练习 5.5
给出进行逆量子 Fourier 变换的一个量子线路。
对比式 (5.1)，逆 Fourier 变换可以如下定义：
这实际上就是与 Fourier 变换的所有相位取负而已。因此，将图 5.1 Fourier 变换的量子线路的所有 \(R_k\) 替换为 \(R_k^\dagger\) 即得到逆 Fourier 变换的线路了。
另一种做法如书中后文所述，将线路对调也可以实现。
练习 5.6 (量子 Fourier 变换的近似)¶
练习 5.6
量子 Fourier 变换的量子线路结构，表面上需要用到的门路个数为量子比特数目的指数量级；然而，多项式规模的量子线路永远不需要这样的精度。例如，令 \(U\) 是 \(n\) 量子比特上的理想 Fourier 变换，而 \(V\) 是以精度 \(\Delta = 1 / p(n)\) 完成受控 \(R_k\) 门得到的结果，其中 \(p(n)\) 是某个多项式。证明误差
因此每个门的多项式精度对保证输出状态的多项式精度就够了。
首先，回顾盒子 4.1 的式 (4.69) 结论，若量子 Fourier 变换使用图 5.1 实现，且我们假设 Hadamard 门与 swap 门可以精确实现，那么 \(E(U, V)\) 的误差可以拆分为各 \(R_k\) 门路误差的和。由于对于 \(n\) 量子比特，Fourier 变换线路需要 \(n(n-1)/2\) 个 \(R_k\) 门 (书中所说的 \(n(n+1)/2\) 个门路包含了 \(n\) 个 Hadamard 门，在误差分析中要剔除这些门路的误差贡献)，因此
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}\) 的作用。其它控制门路同理，因此我们得到
练习 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\) 个量子比特状态为
现在我们考察第二寄存器代入的是线性组合态 \(\sum_{u} c_u |u\rangle\)。首先引入一个引理。这里需要假设 \(U\) 是线性算符 (量子门路一般都有该要求)；并且利用到本征态 \(|u\rangle\) 和本征值 \(e^{2 \pi i \varphi_u}\) 因此，
现在我们考虑第一次控制过程，即在第 \(t\) 个量子比特 \(|0\rangle\) 上引入 Hadamard 门后施加 \(\text{ctrl-}U\) 门：
沿用上面的结果，再考虑第二次控制过程，即在第 \(t-1\) 个量子比特 \(|0\rangle\) 上引入 Hadamard 门后施加 \(\text{ctrl-}U^2\) 门：
如此往复，可以得到第一阶段后，状态会成为
因此，可以表明相位估计的第一阶段操作是线性的。
线性叠加态的相位估计第二阶段
第二阶段是逆 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.3 应用：求阶和因子问题¶
练习 5.10¶
练习 5.10
证明 \(x=5\) 模 \(N=21\) 的阶是 6。
练习 5.11¶
练习 5.11
证明 \(x\) 的阶满足 \(r \leqslant N\)。
依据阶的定义，\(x\) 与 \(N\) 无公因子，即互质。由定理 D.9 (Euler)，\(x^{\varphi(N)} = 1 \; (\text{mod } N)\)，其中 \(\varphi(N)\) 是 Euler \(\varphi\) 函数，即小于 \(N\) 且与 \(N\) 互质的正整数。因此，阶一定不大于 \(\varphi(N) < N\)。
但需要注意，阶未必需要是 \(\varphi(N)\)。譬如，对于练习 5.10 的例子而言，\(\varphi(21) = 18\) (20 个整数去除 \(3, 7\)；注意 \(1\) 与任何数互质)；但阶是 6。
练习 5.12¶
练习 5.12
证明式 (5.36) 所给出的 \(U\) 是酉的：
其中，\(x\) 与 \(N\) 互质，且只有 \(0 \leqslant y \leqslant N-1\) 时的 \(U\) 操作是不平凡的。
我们的目标是证明 \(U^\dagger U = I\)，即考察矩阵元 \((U^\dagger U)_{y' y}\) 是否是 \(\delta_{y' y}\)。
若 \(y = y'\)，显然 \((U^\dagger U)_{y y} = 1\)。
若 \(y \neq y'\)，那么
这是因为 \(x\) 与 \(N\) 互质，因此不存在非零正整数 \(y-y'\)，使得 \(x (y-y')\) 是 \(N\) 的倍数。整理上式易知
因此，若 \(y \neq y'\)，则 \((U^\dagger U)_{y' y} = 0\)。证明完毕。
最后，我们指出，\(U^\dagger = U^{-1}\) 操作相当于
其中，\(r\) 是 \(x\) 模 \(N\) 的阶。
练习 5.13¶
练习 5.13
证明下式：
进而证明
提示：本题证明过程需要利用到下述结论 (也可以参考练习 5.1 的证明过程)：
回顾式 (5.37)，并将 (5.37) 中的角标 \(k\) 换成 \(k'\)：
代入式 (5.45)，则待证等式左为
利用题目的提示，上式对 \(s\) 的求和可以化为
因此，式 (5.45) 证明完毕。
对于式 (5.44) 的证明，我们需要利用到练习 5.8 的其中一个证明步骤：对于态 \(\sum_s c_s |u_s\rangle\)，其中 \(|u_s\rangle\) 必须是 \(U\) 的本征态且对应本征值 \(\lambda_s\)，那么 \(U^m\) 作用于该混合态的结果是
因此，我们对式 (5.45) 等式两边作用 \(U^{-k}\) (这里的 \(-k\) 尽管是负整数，但由于 \(U^r = I\)，因此其实也可以用 \(U^{r-k}\) 替代作证明)。等式右边为
我们回顾到式 (5.39)，\(|u_s\rangle\) 的本征值是 \(\lambda_s = e^{2 \pi i s / r}\)。因此，
因此，式 (5.44) 证明完毕。
练习 5.14¶
练习 5.14
若我们将第二寄存器初始化为 \(|1\rangle\)，在逆 Fourier 变换之前，求阶算法产生的量子状态是
证明如果我们把 \(U^j\) 替换为酉变换 \(V\)，它计算的是
且让第二寄存器从 \(|0\rangle\) 开始，那么将得到同样的状态。同时说明如何仍然用 \(O(L^3)\) 个门构造 \(V\)。
\(V\) 与 \(U^j\) 的等价性是显然的；只要将 \(k = 0\) 代入即可。由于加法运算的门路估计是 \(O(L)\)，而 \(x^j\) 门路估计是 \(O(L^3)\)，因此总地来说仍然是 \(O(L^3)\) 门路复杂度。
练习 5.15¶
练习 5.15
证明正整数 \(x\) 和 \(y\) 的最小公倍数是 \(xy / \gcd(x, y)\)，其中 \(\gcd (x, y)\) 表示 \(x, y\) 的最大公因子。因此若 \(x\) 和 \(y\) 是 \(L\) 比特数，那么最小公倍数可以在 \(O(L^2)\) 步运算内算出。
这应该是初中竞赛题里不需要额外说明，就可以使用的定理吧。这里只是简单的说明而已。
令 \(g = \gcd(x, y)\)，那么可以定义整数 \(a, b\) 使得 \(x = ag, y = bg\)。显然 \(\gcd(a, b) = 1\)，否则 \(\gcd(x, y)\) 就可以写成 \(\gcd(a, b) g\) 了。
现在令最小公倍数 \(t\)，即 \(x | t\) 且 \(y | t\)。那么可以设正整数 \(\alpha, \beta\) 使得 \(t = \alpha x = \alpha a g\)；同时 \(t = \beta y = \beta b g\)。联立两式，得到
我们希望 \(\alpha, \beta\) 要尽可能小；但由于 \(a, b\) 互质，因此 \(\alpha, \beta\) 最小分别是 \(b, a\)。因此，
但至于求最小公倍数的消耗，在附录 D.2 节的 Euclid 辗转相除法叙述中，我们知道 \(\gcd\) 消耗是 \(O(L^3)\) 的；因此总的耗时应该是 \(O(L^3)\)，或许题目给错了。
但不论怎么说，求 \(\gcd\) 是多项式时间可完成的；而且完全可以交给经典计算机完成。
练习 5.16¶
练习 5.16
对所有的 \(x \geqslant 2\)，证明
进而证明下式
由上式，可知式 (5.58) 成立：
这里关于 \(q\) 的求和是对素数的求和。
首先我们验证定积分
之所以不等式成立，是因为我们利用了 \(x \geqslant 2\) 的条件：
随后证明 \(\sum_q q^{-2}\) 的不等式 (注意关于素数 \(q\) 的求和范围比对 \(x\geqslant 2\) 的范围要小一些)：
因此，式 (5.58) 成立。事实上，即使是使用上述粗糙的证明过程，式 (5.58) 的后一个不等号 \(\geqslant\) 也完全可以写为 \(>\)。
作为简单的补充，实际上下述过程成立：
因此，
即作两次相位估计给出 \(r_1', r_2'\)；而后通过求取最大公倍数的方法得到阶的做法，正确率不止书上提到的 1/4 即 25%；它至少可以达到 35.5% 甚至更高。
练习 5.17¶
练习 5.17
设 \(N\) 为 \(L\) 比特长。本练习的目的是找出一个有效的经典算法，判定 \(N = a^b\) 是否对某些整数 \(a > 1\) 和 \(b \geqslant 2\) 成立。这可以按如下步骤达到。
证明若这样的 \(b\) 存在，则必满足 \(b \leqslant L\)；
证明为计算 \(y = \log_2 N\)，对 \(b \leqslant L\) 计算 \(x = y / b\)，以及计算两个最接近 \(2^x\) 的整数 \(u_1, u_2\)，至多需要 \(O(L^2)\) 个运算；
证明为计算 \(u_1^b\) 和 \(u_2^b\) (反复使用平方) 和检查它们是否等于 \(N\)，至多需要 \(O(L^2)\) 个运算；
将前面的结果结合起来，给出一个 \(O(L^3)\) 的算法，以判定 \(N=a^b\) 是否对整数 \(a\) 和 \(b\) 成立。
警告
本题可能存在诸多问题。
整数 \(N\) 应当要是 \(L \geqslant 2\) 比特的，否则会出现 \(a = 1\) 的情况；这个情况不值得讨论；见下述网站论述：
https://serab.net/docs/qcqi/chapter5/#517
第 2 小题已经作更正，即令 \(y = \log_2 N\)；见下述网站论述：
https://quantumcomputing.stackexchange.com/questions/11394/not-sure-what-do-nielsen-and-chuang-mean-by-number-of-operations
https://math.stackexchange.com/questions/1362724/algorithm-for-determining-whether-n-ab
一些基本数学运算的复杂度可以参考：
https://quantumcomputing.stackexchange.com/questions/11394/not-sure-what-do-nielsen-and-chuang-mean-by-number-of-operations
https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations
首先，\(y = \log_2 N\) 的操作，目前最优秀的算法应当是 \(O(L^2 \log L)\)；但它只需要计算一次。
若存在，则 \(b = \log_a N \leqslant \log_2 N \leqslant L\)；这意味着整个算法可以以 \(b = 2, 3, \cdots, L\) 来循环，循环带来的复杂度是 \(O(L)\)。
若我们认为乘除法的复杂度是 \(O(L^2)\)，\(2^x\) 运算也是 \(O(L^2)\)，那么这里总复杂度是 \(O(L^2)\)。但我不太确定 \(2^x\) 作为幂次算法是否确实是 \(O(L^2)\) 的，特别是这里的 \(x\) 不是整数，因此 \(2^x\) 不能简单地通过位移实现。
这里我们不需要直接计算幂次；因为我们对 \(b\) 进行迭代，因此这里实际需要的计算是 \(u_1^{b-1} \times u_1\)，其中 \(u_1^{b-1}\) 是被储存的数值；当然这里以额外内存空间作为代价。因此，计算复杂度与乘法相同，是 \(O(L^2)\)。
第 2、3 步的总复杂度是 \(O(L^2)\)，而它们包含在 \(O(L)\) 次的循环中，因此总复杂度是 \(O(L^3)\)。
练习 5.18 (因式分解 91)¶
练习 5.18
假设我们希望因式分解 \(N=91\)。验证第 1 步和第 2 步会通过。对第 3 步，设我们选择 \(x=4\)，它与 \(91\) 互质。计算 \(x\) 相对 \(N\) 的阶，并证明 \(x^{r/2} = 64 \neq -1 \; (\text{mod } 91)\)，因此算法会成功，并给出 \(\gcd(64-1, 91) = 7\)。这不是读者所见到过的分解 \(91\) 的最有效方法。的确，如果所有的计算都在经典计算机上进行，这个规约不会导致一个有效的因式分解算法；因为上不知道在经典计算机上解决求阶问题的有效算法。
我们回顾到算法因式分解到求阶的归约。第 1 步，若 \(N\) 是偶数，返回因子 2；但 91 不是偶数。第 2 步，是否有 \(N = 91 = a^b\) 的表达式，但显然不是。第 3 步，\(\gcd(4, 91) = 1\)，因此将继续进行到第 4 步求 \(x\) 模 \(N\) 的阶。
因此，阶 \(r = 6\)；恰巧 \(r\) 为偶数且 \(4^{r/2} = 64 \neq -1 \; (\text{mod } 91)\)。因此，算法成立。
第 5 步，我们发现 \(\gcd(4^3-1, 91) = 7 \; (\text{mod } 91)\) 且 \(\gcd(4^3+1, 91) = 13 \; (\text{mod } 91)\)。因此，我们发现 \(7, 13\) 都是 91 的因数。
事实上，求阶的过程在经典计算机上，需要通过枚举给出；这对于非常大的数而言是非常低效的。在量子计算机上，则可能在一定概率下给出。
练习 5.19¶
练习 5.19
证明 \(N=15\) 是需要用到求阶子程序的最小数，即它是即非偶数又非更小正整数幂的最小合数。
若依据书中的算法因式分解到求阶的归约，那么第 1 条排除所有偶数；第 2 条排除正整数幂 \(3^2=9\)。因此，满足条件的最小的合数确实就是 \(3 \times 5 = 15\)。在盒子 5.4 中，书中也表明 15 确实可以被量子算法有效地因式分解。
当然，我自己其实比较怀疑，这是否是个偶然。按理来说，如果不考虑第二条性质，那么最小的合数会是 \(9\)。但在这种情况下，\(1\) 是平凡的、\(3, 6\) 是有公因子的；
\(2\) 的阶是 \(6\)，但 \(2^3=8 \; (\text{mod } 9) = -1\)；
\(4\) 的阶是 \(3\)，阶恰好不是偶数；
\(5\) 的阶是 \(6\)，但 \(5^3=8 \; (\text{mod } 9) = -1\)；
\(7\) 的阶是 \(3\)，阶恰好不是偶数；
\(8\) 的阶是 \(2\)，但 \(8^1=8 \; (\text{mod } 9) = -1\)；
因此，在当前的算法下，我们确实无法分解 \(9\)。我也不清楚是否与偶数和幂次数有关；但这可能确实地表明，基于书中所提到的相位估计的 Shor 算法，不一定完美地分解所有合数。这会是源于阶不是奇数的性质、以及阶除以 2 后幂次恰为 -1 的性质。但可能对于足够大的数而言，这种情况发生的概率非常小，如书中式 (5.60) 所言。
5.4 量子 Fourier 变换的一般应用¶
练习 5.20¶
练习 5.20
设 \(f(x+r) = f(x)\)，且 \(0 \leqslant x < N\)，\(N\) 是 \(r\) 的一个整倍数；计算
并将此结果与式 (5.63) 联系起来。其中用到的事实是
上式编号为式 (5.69)。
警告
英文原版中，式 (5.69) 是错误的。中文版是正确的。
书中提到，之所以算法求周期的第 (3) 步是近似的，是因为 \(N = 2^t\) 不一定是 \(r\) 的整数倍数；但若确实是整数倍数，那么这个近似其实就是等价了。我们在这里证明的是 \(N\) 是 \(r\) 倍数时的等价情况。
什么情况下，算法的第 (3) 步的近似是有效的呢？若 \(\lfloor N/r \rfloor \times r\) 到 \(N - 1\) 之间的求和在总求和区间即 \(0\) 到 \(N-1\) 内占比很小时，那么近似是有效的。为了达到一个较好的近似，\(N\) 应当要取得足够大。
式 (5.69) 验证
为了之后证明的方便，我们也要试一下将 (5.69) 的记号进行简化，并对其进行验证。首先，依题目的假设，我们可以定义整数 \(j = \frac{k}{r}\)，并定义整数 \(\lambda, c\) 为 \(l = \lambda N/r + c\)，其中 \(c\) 是小于 \(N/r\) 的自然数。那么，待证式 (5.69) 可以写为
若 \(c = 0\)，即 \(l = \lambda N / r\) 即 \(l\) 是 \(N/r\) 的整倍数，那么被求和项是 \(e^{2 \pi i j \lambda} = 1\)。由于总共有 \(N/r\) 个求和项，因此总和就是 \(N/r\)。
若 \(c \neq 0\)，那么被求和项是 \(e^{2 \pi i j \lambda} e^{2 \pi i j r c / N} = e^{2 \pi i j r c / N}\)；因此依据以比例为 \(\omega = e^{2 \pi i r c / N}\) 等比数列的求和方法，
\[ \sum_{j=0}^{N/r-1} e^{2 \pi i jrc / N} = \frac{1 - \omega^{N/r}}{1 - \omega} = \frac{1 - e^{2 \pi i c}}{1 - \omega} = \frac{0}{1 - \omega} = 0 \]
式 (5.68) 验证
首先，我们可以用 \(x = j r + d\) 的形式表示指标；那么在当前的问题下，恰好 \(j\) 可以取遍 \(0, 1, \cdots, N/r-1\)，而 \(d\) 恰好可以取遍 \(0, 1, \cdots, r-1\)。那么，我们将 (5.68) 对 \(x\) 的求和化为对 \(j\) 与 \(d\) 的求和了。同时注意到 \(f(x+r) = f(x)\) 的周期性条件，因此 \(f(x) = f(jr+d) = f(d)\)：
我们现在回顾到 \(\sum_{j=0}^{N/r-1} e^{2 \pi i j r l / N}\) 只有在 \(l\) 是 \(N/r\) 整倍数时非零且为 \(N/r\) 的结论，那么将上式整理可得
与式 (5.63) 的联系
该式与 (5.63) 看起来相差了归一化因子。我们作如下说明。
将上面答案中的被求和角标 \(d\) 替换为 \(x\)；并且将 \(f(x)\) 表示为右矢空间的态 \(|f(x)\rangle\)。
由于不是所有 \(l\) 都需要考虑，因为只有 \(l\) 是 \(N/r\) 的情况下结果是非平凡的。那么我们就只考虑这些非平凡的 \(l\)。我们使用 \(r\) 维度的向量空间 \(|\hat g(\lambda)\rangle\) 来储存这些 \(|\hat f (l) \rangle = |\hat g (\lambda N/r) \rangle\)：
\[ |\hat g (\lambda)\rangle = \frac{\sqrt{N}}{r} \sum_{x=0}^{r-1} e^{-2 \pi i (\lambda N / r) x / N} |f(x)\rangle \left/ \sqrt{\frac{r}{N}} \right. = \frac{1}{\sqrt{r}} \sum_{x=0}^{r-1} e^{-2 \pi i \lambda x / r} |f(x)\rangle \]
之所以要除以 \(\sqrt{r/N}\)，是因为我们之前的 \(|\hat f (l)\rangle\) 的空间是 \(l = 0, 1, \cdots, N-1\) 的 \(N\) 维空间；而 \(|\hat g(\lambda)\rangle\) 则是 \(\lambda = 1, 2, \cdots, r\) 的 \(r\) 维空间。因此，并非把 \(|\hat f (l)\rangle\) 的所有非零元素放到 \(|\hat g(\lambda)\rangle\) 就好了，还需要作合适的归一化。
上式其实就是式 (5.63) 了。需要注意，本题的 \(l\) 是可以取 \(l = 0, 1, \cdots, N-1\) 的；但式 (5.63) 的 \(l\) 其实只能取 \(l = 0, 1, \cdots, r-1\)，这也能从式 (5.64) 的求和角标取值范围看出。式 (5.63) 的 \(l\) 其实是这道题的 \(\lambda = l / (N / r)\)。
练习 5.21 (求周期与相位估计)¶
练习 5.21
设为上述周期函数，给定一个执行变换 \(U_y |f(x)\rangle = |f(x+y)\rangle\) 的酉算符 \(U_y\)。
证明 \(U_y\) 的特征向量是 \(|\hat f(l)\rangle\)，并计算其特征值；
证明对某个 \(x_0\) 所给定的 \(|f(x_0)\rangle\)，\(U_y\) 可被用来实现和求周期问题中的 \(U\) 一样有用的黑箱。
第一问
我们使用式 (5.63) 所定义的 \(|\hat f(l)\rangle\)。同时，令变量 \(u = x + y\)，\(u' = u - r\)。因此，
第四个等号利用的是 \(|f(x)\rangle\) 以 \(r\) 为周期的性质；第六个等号则利用了 \(e^{- 2 \pi i l} = 1\)，且回顾 \(|\hat f(l)\rangle\) 的定义就可以推导出来。因此我们验证了 \(|\hat f(l)\rangle\) 是 \(U_y\) 的本征态，且本征值是 \(e^{2 \pi i l y / r}\)。
第二问
对于特定的 \(x_0\)，我们先要对其依据式 (5.64)，将其拆解为 \(U_y\) 本征态的线性组合 (注意对于第一寄存器比特数 \(t\)，若 \(r \nmid 2^t\)，那么下式在实际实现过程中会成为近似)：
那么就可以利用算符的线性性质，将 \(U_y\) 作用在 \(|f(x_0)\rangle\) 上得到
对于实际线路中，\(x\) 是要被求和的，即两个寄存器实际状态是
需要注意，由于逆向 Fourier 变换只在第一寄存器上计算，该过程可以写为
因此，在逆向 Fourier 变换后，所有寄存器上的状态表示为
随后对第一寄存器测得分数 \(\widetilde{l/r}\)。因此，我们注意到尽管使用 \(U_y: |f(x)\rangle \mapsto |f(x+y)\rangle\) 相比于 \(U: |f(x)\rangle \mapsto |y \oplus f(x)\rangle\) 在最终的寄存器表达式中多了 \(e^{-2 \pi i l y / r}\) 一项，但它只是个相位。测得的 \(\widetilde{l/r}\) 是相同的，而且对于每个 \(l = 0, 1, \cdots, r-1\)，其出现的概率也相同。
练习 5.22¶
练习 5.22
证明
且这个表达式不为零的限制条件是，\((l_1/s)-l_2\) 是 \(r\) 的整倍数。
警告
原书中的公式表述有些错误。式 (5.70) 其实不包含 \(1/\sqrt{r}\) 的系数。对 \(|f(x_1, x_2)\rangle\) 的 Fourier \(|\hat f(l_1, l_2)\rangle\) 的变换空间其实是 \((l_1, l_2)\) 构成的 \(\mathbb{Z}_r \times \mathbb{Z}_r\) 空间，因此归一化系数应该取为 \((1/\sqrt{r})^2 = 1/r\)。
首先我们回顾到，我们现在的函数是 \(f(x_1, x_2) = a^{s x_1 + x_2} \; (\text{mod } N)\)，因此，该函数也可以写为 \(f(0, sx_1 + x_2)\)。因此代入待证等式，得到
随后将 \(x_2\) 用 \(j = s x_1 + x_2\) 替换，那么
利用 \(f(0, j) = f(0, j+r)\) 的周期性，上式化为
我们以前已经多次证明到，
因此，
练习 5.23¶
练习 5.23
用式 (5.70) 证明，
警告
原来题目里 \(e\) 幂指数上是有负号的。但作为 Fourier 变换，其符号应该是正的才对。参考式 (5.64)，我决定将题目中的幂指数上的负号去掉。
首先，我们知道 \(l_1 = s l_2 (\text{mod } r)\) 的 \(|\hat f(l_1, l_2)\rangle\) 的值可能非零。同时，由于 \(l_1\) 的可取值范围是 \(0, 1, \cdots, r-1\)，因此 \(\sum_{l_1=0}^{r-1}\) 与其说是求和，不如说只能取 \(s l_2 (\text{mod } r)\)。但出于周期性，因此我们代入 \(l_1 = s l_2\) 也无妨。那么得到待证等式左为
随后我们代入练习 5.22 的结论：
我们首先对 \(l_2\) 求和。利用我们以前一直证明过的结论，知道
因此，对待证等式左有实质贡献的项必然满足 \(j = s x_1 + x_2 \; (\text{mod } r)\)。在这种情况下，\(f(0, j) = f(0, s x_1 + x_2) = f(x_1, x_2)\)。考虑到这些后，待证等式就证明完毕了。
练习 5.24¶
练习 5.24
建立离散对数算法第 6 步所需要的，从 \(s l_2/r\) 和 \(l_2 / r\) 的估计确定 \(s\) 的推广的连分式算法。
警告
下述做法其实是很直白的，没有使用推广连分式。但需要一次量子算法，因此实现稍困难一些。
首先，这个算法是合理的。我们至少有 \(1/4\) 概率通过对 \(\widetilde{l_2/r}\) 作连分式，得到正确的 \(r\)；因此不必担心因为 \(s\) 是 \(r\) 的因子，而无法从 \(\widetilde{s l_2 / r}\) 获得正确分母的情况。因此，\(\widetilde{s l_2 / r}\) 的分子、分母都可以正常地估计，即使它们并不互质。
算法困难之处在于 \(s l_2\) 可能因为大于 \(r\)，因此我们实际估计到的分子不是 \(s l_2\)，而是 \(s l_2 \; (\text{mod } r)\)。不能将 \(\widetilde{s l_2 / r}\) 的分子与 \(\widetilde{l_2/r}\) 的分子直接相除。当然，如果 \(s l_2 \; (\text{mod } r)\) 恰好是 \(l_2\) 的倍数，那么我们可以直接输出两者的比例作为 \(s\) 的值。
如果 \(s l_2 \; (\text{mod } r)\) 不是是 \(l_2\) 的倍数，那么解决方案是，既然我们通过 \(\widetilde{l_2/r}\) 可以获得正确的 \(l_2\) (回顾到它与 \(r\) 需要是互质的，才能给出正确的 \(r\))，并且假设 \(r\) 是 \(L\) 比特数，那么
通过 \(O(L^3)\) 量子算法和连分式算法，获得 \(l_2\) 模 \(r\) 的阶 \(k\)，即 \(l_2^k = 1 (\text{mod } r)\)；我们注意到因为上面的过程要求 \(l_2\) 与 \(r\) 互质，因此这里的阶的存在性是能保证的。
通过 \(O(L^3)\) 的幂运算，获得 \(l_2^{k-1} \; (\text{mod } r)\)。
从而可以计算 \(s l_2 \times l_2^{k-1} = s \; (\text{mod } r)\)。
整个过程仍然是 \(O(L^3)\) 的，但需要一次额外的量子算法。
练习 5.25¶
练习 5.25
为用于两子离散对数算法的黑箱 \(U\) 构造一个量子线路；该黑箱以 \(a, b\) 为参数，执行酉变换 \(|x_1\rangle |x_2\rangle |y\rangle \rightarrow |x_1\rangle |x_2\rangle |y \oplus b^{x_1} a^{x_2} \rangle\)，需要多少基本运算？
假定 \(x_1, x_2, y, a, b\) 均是不大于 \(L\) 的比特数。
幂次运算 \(b^{x_1}\)、\(a^{x_2}\) 是 \(O(L^3)\) 计算复杂度，它们可能需要用到额外 \(L\) 个寄存器用于储存临时变量；
乘法 \(b^{x_1} a^{x_2}\) 是 \(O(L^2)\) 计算复杂度；
加法 \(y \oplus b^{x_1} a^{x_2}\) 是 \(O(L)\) 计算复杂度。
总得来说是 \(O(L^3)\) 复杂度。
练习 5.26¶
练习 5.26
因为 \(K\) 是 \(G\) 的一个子群，当我们把 \(G\) 分解为素幂阶循环群的乘积时，也分解了 \(K\)。重新表达式 (5.77)，证明为确定 \(l_i'\)，可以在对应于 \(K\) 的循环子群 \(K_{p_i}\) 中采样。
设 \(K\) 的分解是 \(K = Z_{p_1} \times Z_{p_2} \times \cdots \times Z_{p_N} \subseteq Z\)，那么式 (5.77) 可以写为
那么对于上式的任何一个 \(j\)，目标是要寻找能使下式非零的 \(l_j'\)：
一般来说，这会要求 \(l_j' = 0\)；否则依等比数列求和公式，若 \(l_j' / p_j\) 不是整数，那么上式必然为零。
我对抽象的群论只有一些了解，但没有把握掌握这些。下面是我对这道题的理解。
我想这道题是说，如果 Abel 群 \(G\) 是可以拆分为有限素幂阶循环群，那么对于 Fourier 变换后的变量 \(l\) 并非可以是任意的，而必须要满足一定形式，才会使 \(|\hat f(l)\rangle\) 的贡献非零。
假设说，\(G = G_1 \times G_2 \times K_1 \times K_2\)，其中 \(K = K_1 \times K_2\) 是 \(G\) 的隐含子群，那么对应地，\(l = (l_{G_1}, l_{G_2}, l_{K_1}, l_{K_2})\)。只有 \(l_{K_1}, l_{K_2} = 0\) 时 (或类似地，\(l_{K_1}\) 是 \(|K_1|\) 的倍数、\(l_{K_2}\) 是 \(|K_2|\) 的倍数)，那么这样的 \(|\hat f(l)\rangle\) 对 \(|f(x)\rangle\) 的贡献才是非零的。
一个例子可以是离散对数问题，即 \(\mathbb{Z}_r \times \mathbb{Z}_r\) 下的循环函数 \(f(x_1, x_2) = f(x_1 + l, x_2 - ls)\)。我们使用数对 \((x_1, x_2)\) 表示函数 \(f(x_1, x_2)\)，由此在求 Fourier 变换时对应地使用 \((l_1, l_2)\) 给出
进而发现，必须要有限制条件 \(l_1 - l_2 s\) 是 \(r\) 的倍数。因此，\(l_1, l_2\) 就缺少了一个自由度。
换个角度来考虑问题。如果我们用数对 \((x_1, x_2)\) 表示 \(f(x_1 + l x_2, x_1 - ls x_2)\) (需要指出，我们一开始并不知道周期常数 \(l, s\)，因此它不能使用在实际的量子算法中，但现在只是写写公式而已)。为了讨论方便 (因此这里的讨论其实相当不严谨，但我想大致思路是对的)，我们假设现在恰巧 \(l, s, r\) 互质，那么 \(x_1, x_2\) 可以取遍所有 \(\mathbb{Z}_r \times \mathbb{Z}_r\) 下的二元数组。令群 \(x_1 \in G_1\)、\(x_2 \in G_2\)，那么 \((x_1, x_2) \in G_1 \times G_2 = G = \mathbb{Z}_r \times \mathbb{Z}_r\)。那么不论 \(x_2\) 的值是多少，函数的值只受 \(x_1\) 的影响而变化。如果我们在求 Fourier 变换时对应地使用 \((l_1, l_2)\)，那么可以给出
我们注意到关于 \(x_2\) 的求和式中，若 \(l_2 / |G_2|\) 不为整数，那么这一项就为零。因此，\(l_2\) 必须要是零，即
或者如果我们剔除 \(l_2\)，则可以少去一个归一化因子：
依据定义，\(x_2\) 的取值空间 \(G_2\) 其实同构于隐含子群 \(K\)，即二元数组 \((l, -ls)\) 依关于 \(r\) 的模生成的群。从这个角度来考察这道练习 5.26，我想应该就会更直观一些。
但现实中，\(l, s, r\) 互质并不一定成立；因此对于 \(\mathbb{Z}_r \times \mathbb{Z}_r\) 问题，可能不能真的依这种方法简化。但若可以拆成多个不同素数的素幂阶循环群，那么可能就有算法提升的空间。
未完成题目¶
危险
练习 5.27-5.29 未完成。
练习 5.27 可以参考下述文献：
https://arxiv.org/abs/cs/0101004
练习 5.28, 5.29 可以参考下述文献：
https://arxiv.org/abs/quant-ph/9903071
第六章 量子搜索算法¶
6.1 量子搜索算法¶
练习 6.1¶
练习 6.1
证明对应于 Grover 迭代中，相移的酉算符是 \(2 |0\rangle \langle0| - I\)。
这是比较显然的。一种理解方式是矩阵表示。另一种则是将该相移算符作用于具体的态 (下式的 \(x > 0\))：
练习 6.2¶
练习 6.2
证明应用运算 \((2 |\psi\rangle\langle\psi| - I)\) 到一般状态 \(\sum_k \alpha_k |k\rangle\) 产生
其中 \(\langle \alpha \rangle = \sum_k \alpha_k / N\) 是 \(\alpha_k\) 的均值，因此，\((2 |\psi\rangle\langle\psi| - I)\) 有时称为关于均值的反演 (inversion about mean) 运算。
首先我们回顾到均衡叠加态的定义
因此，其外积为
随后，我们指出题目中的 \(\sum_k \alpha_k |k\rangle\) 严格来说是 \(\sum_{k=0}^{N-1} \alpha_k |k\rangle\)，即 \(k\) 并非任意角标。因此，
最后一个等号仅仅是角标的替换而已。随即，
练习 6.3¶
练习 6.3
证明 \(|\alpha\rangle, |\beta\rangle\) 基中，可以把 Grover 迭代写成
其中 \(\theta\) 是一个 \(0\) 到 \(2 \pi\) 之间的实数 (为简单起见，假定 \(M \leqslant N/2\)，这个限制很快会取消)，它满足
首先，我们很容易表明题目中所给的 \(\theta\) 与正文的定义相同。我们回顾到正文中定义
因此，
随后我们利用矩阵下的表示来作说明。首先，\(|\psi\rangle\) 在基 \(\{ |\alpha\rangle, |\beta\rangle \}\) 下的表示向量是
那么其外积是
而依据运算 \(O\) 的定义
我们知道其矩阵表示类似于 \(Z\) 算符：
因此，
这道题的直观思路显然是书中的图 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) 中有阐述：
练习 6.5¶
练习 6.5
证明用一次 \(O\) 调用，基本量子门和附加的量子比特 \(|q\rangle\) 可以构造增广的 oracle \(O'\)。
该问题的解答参考下述网页：
https://serab.net/docs/qcqi/chapter6/
构造下述量子线路：
首先，如果 \(|q\rangle\) 是 \(|0\rangle\)，那么总的量子线路的作用相当于
因此，对于 \(|q\rangle\) 为 \(|0\rangle\) 的情况，\(|x\rangle\) 是否是解可以从相位是否翻转看出。
但若 \(|q\rangle\) 是 \(|1\rangle\)，那么在进入未增广的 orcale 门 \(O\) 之前，最后的工作量子比特变成了 \((|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\)。因此，该门路其实是
6.2 作为量子仿真的量子搜索¶
练习 6.7¶
练习 6.7
验证图 6.4 和图 6.5 所示线路分别实现运算 \(e^{- i |x\rangle \langle x| \Delta t}\) 和 \(e^{- i |\psi\rangle \langle\psi| \Delta t}\)，其中 \(|\psi\rangle\) 如式 (6.24) 所示：
图 6.4
图 6.5
警告
这道题可能有一些表述不当或错误。
式 (6.24) 的求和对象是 \(a\) 而非原书中的 \(x\)；因为在上下文中，\(|x\rangle\) 已经用来表示解了，因此用于表示均匀叠加态的求和指标应当用其它记号比较好。
图中的相位门的符号可能是错的，这在很多讨论中已经发现 (serab.net 的解答、Stack Exchange 的讨论 1 与 2)。因此，我们这里也采用经过修正的相位。
我们修改了代入线路的初始状态为 \(|\phi\rangle |0\rangle\)。原来的书中是 \(|y\rangle |0\rangle\)，但我认为不太合适，因为 \(|y\rangle\) 已经用来表示非解了。
图 6.4 证明 (1) 指数算符的简化
以 \(\Delta t\) 作为小量进行 Taylor 展开：
我们回顾到\(|x\rangle \langle x|\)、\(|\psi\rangle \langle\psi|\) 等外积算符是投影算符。因此，它满足幂等性，即 \(( |x\rangle \langle x| )^2 = |x\rangle \langle x|\)。幂等性的推广可以是，若 \(k \geqslant 1\) 且为整数，那么 \((|x\rangle\langle x|)^k = |x\rangle\langle x|\)。因此，上式的求和可以化为
最后，由于 \(|x\rangle\) 与 \(|y\rangle\) 在整个空间互补，因此 \(|x\rangle \langle x| + |y\rangle \langle y| = I\)。进而，
我们最后考察一下 \(e^{- i |x\rangle \langle x| \Delta t}\) 算符作用在 \(|\phi\rangle = \alpha |x\rangle + \beta |y\rangle\) 上的结果 (留意到因为 \(|x\rangle\) 是解态而 \(|y\rangle\) 是非解态，因此两者正交即 \(\langle x|y\rangle = 0\))：
图 6.4 证明 (2) 线路图
我们仍旧与以前一样，通过每个门路之后，考察线路的态的行为。
对于 orcale 过程，若代入的是问题的解 (即 \(|x\rangle\))，则互换 orcale 工作空间比特的 \(|0\rangle\) 与 \(|1\rangle\)；但若不是问题的解 (即 \(|y\rangle\))，那么不作变换。因此，
对于最末的相位过程，若代入的是 \(|0\rangle\) 则不作变换；若代入的是 \(|1\rangle\) 则加以相位 \(e^{i \Delta t}\)。因此，
最后再用一次 orcale 过程：
我们发现这个结果中，除去 orcale 工作量子比特，其余部分与 \(e^{- i |x\rangle \langle x| \Delta t} |\phi\rangle\) 结果一致。
图 6.5 证明 (1) 指数算符的简化
与之前的计算过程非常类似地，我们可以得到图 6.5 待证的算符是
但在图 6.5 的证明中，比较方便的做法是直接使用数学推演，而非使用线路结果。我们提前需要表明，作为均匀叠加态，
图 6.5 证明 (2) 线路图
我们令相位门 \(P_{- i \Delta t} = \begin{bmatrix} 1 & 0 \\ 0 & e^{- i \Delta t} \end{bmatrix}\)，那么图 6.5 的线路中存有三种门路：Hadamard 门 \(H^{\otimes n} \otimes I\)、受控非门 \(I^{\otimes n} \otimes I - |0\rangle\langle0| \otimes (I-X)\)、相位门 \(I^{\otimes n} \otimes P_{-i \Delta t}\)。其中，受控非门的 \(|0\rangle\langle0|\) 表示的是 \(n\) 量子比特态的投影算符，而非单量子比特投影算符。我们依次作计算；首先是第一个 (Hadamard 门)、第二个 (受控非门) 算符作用：
再作用第三个算符 (相位门)：
再作用第四个算符 (受控非门)：
再作用第五个算符 (Hadamard 门) 得到
最后我们注意到，最末的量子比特被规定是 \(|0\rangle\)，因此
因此，该线路作用在 \(|\phi\rangle |0\rangle\) 后会得到
整理上式得到
这就证明完毕了。
练习 6.8¶
练习 6.8
设仿真步的精度可达 \(O(\Delta t^{r})\)，证明以合理的精度模拟 \(H\) 所需要的 oracle 调用次数是 \(O(N^\frac{r}{2 (r-1)})\)。注意当 \(r\) 增大时，\(N\) 的指数接近 \(1/2\)。
首先，总步数始终没有变化，为 \(t / \Delta t = O (\sqrt{N} / \Delta t)\)。累积的误差是 \(O(\Delta t^r \times \sqrt{N} / \Delta t) = O(\Delta t^{r-1} \times \sqrt{N})\)。为了要让这个误差在 \(O(1)\) 级别，因此
算法调用步数则是
容易验证
练习 6.9¶
练习 6.9
验证式 (6.25) (提示：参看练习 4.15)。
此题实在是太直观了，没办法给出过程。
首先，利用练习 4.4 的结论，知道 \(e^{-i |\psi\rangle\langle\psi| \Delta t}\) 与 \(e^{-i |x\rangle\langle x| \Delta t}\) 都是旋转算符；旋转轴分别是该题目在书中上文所定义的 \(\vec \psi = (2 \alpha \beta, 0, \alpha^2 - \beta^2)\) 和 \(\hat z = (0, 0, 1)\)；旋转角都是 \(\Delta t\)。然后直接套用练习 4.15 的结论就行了。
练习 6.10¶
练习 6.10
证明通过适当选取 \(\Delta t\)，可以得到用 \(O(\sqrt{N})\) 次调用的量子搜索算法，并且最终状态恰好是 \(|x\rangle\)。该算法成功概率为 \(1\)，而不是以稍小一些的概率成功。
我们使用倒推法。重新考察式 (6.28)，
因此，
若我们令 \(\theta = 4 / \sqrt{N}\)，则该式符合反三角函数定义域要求，且该值也不需要事先对 \(|x\rangle\) 有所了解。我们不妨绘制一下 \(\Delta t\) 随 \(N\) 的变化情况 (下图的纵坐标是关于 \(\pi\) 的倍数)。
%matplotlib notebook
from matplotlib import pyplot as plt
import numpy as np
N_list = np.arange(1, 10, 0.1)
Dt_list = 2 * np.arcsin(np.sqrt(N_list / 2 * (1 - np.cos(2 / np.sqrt(N_list))))) / np.pi
fig, ax = plt.subplots(figsize=(4, 3))
ax.plot(N_list, Dt_list)
ax.set_xlabel("$N$"); ax.set_ylabel("$\Delta t / \pi$")
ax.set_title(r"When $\theta = 4/\sqrt{N}$")
fig.tight_layout()
练习 6.11 (连续量子搜索的多重解)¶
练习 6.11
猜测一个 Hamiltonian 量，用以求解有 \(M\) 个解的连续时间搜索问题。
我们回顾到之前的 Hamiltonian 量是 \(H = |x\rangle \langle x| + |\psi\rangle \langle\psi|\)。之前讨论的 \(|x\rangle\) 是单解态。但 \(|x\rangle\) 也可以像上一节一样是多解态，即每个解 \(|m\rangle\) 的总和 (不考虑归一化系数) \(|x\rangle = \sum_m |m\rangle\)。在这种情况下，如果量子仿真的每一步精度都足够高，那么 \(O(\sqrt{N/M})\) 步可以完成一次解的搜索，但每次无法确定是其中哪一个解。
练习 6.12 (量子搜索的不同 Hamiltonian 量)¶
练习 6.12
设
给定按 Hamiltonian 量的 \(H\) 演化，证明从状态 \(|\psi\rangle\) 到状态 \(|x\rangle\) 用 \(O(1)\) 次旋转；
说明如何进行 Hamiltonian 量 \(H\) 的量子仿真，并确定以高概率得到该解该仿真技术需要的 orcale 调用次数。
第一问
我们仿照这一节开头的讨论。将 \(|x\rangle\) 与 \(|y\rangle\) 作为基，表示 Hamiltonian 量 \(H\)。我们令 \(|\psi\rangle = \alpha |x\rangle + \beta |y\rangle\)，那么
因此，依据式 (4.8)，
我们已经知道 \((\beta X + \alpha Z) |\psi\rangle = |x\rangle\)，因此
为了让变换 \(e^{-i H t}\) 保证将 \(|\psi\rangle\) 变换到 \(|x\rangle\)，只要让 \(\cos(t) = 0\) 即可。因此可以选用 \(t = \pi/2\)。
第二问
我们发现 \(H = |x\rangle \langle\psi| + |\psi\rangle \langle x|\) 与 \(H = |x\rangle \langle x| + |\psi\rangle \langle\psi|\)，两者在 \(e^{- i H t}\) 算符上唯二的区别在于常数相位与仿真时间间隔。这前者是不关键的；后者是在实际量子门路中可以调整的。因此，这两者在仿真实现上是等价的。
6.3 量子计数¶
练习 6.13, 6.14¶
练习 6.13
考虑计数问题的一个经典算法。该算法在搜索空间中均匀独立地进行 \(k\) 次采样，令 \(X_1, X_2, \cdots, X_k\) 为 orcale 调用的结果，即当第 \(j\) 个调用显示为问题的一个解时，\(X_j = 1\)；而第 \(j\) 个调用没有显示为问题的一个解时，\(X_j = 0\)。这个算法给出搜索问题解的数目的估计 \(S \equiv N \times \sum_j X_j / k\)。证明 \(S\) 的标准差为 \(\Delta S = \sqrt{M (N-M) / k}\)。证明为以至少 3/4 概率，以精度 \(\sqrt{M}\) 对所有 \(M\) 估计 \(M\)，必须有 \(k = \Omega(N)\)。
练习 6.14
证明对任何至少以概率在 \(c \sqrt{M}\) 精度内，对所有的 \(M\) 估计 \(M\)，必须有 \(k = \Omega(N)\)。
我们使用概率的语言来解释标准差 \(\Delta S\) 的求取结果。考虑 \(p(\sum_j X_j = l)\) 或简记为 \(p(l)\) 即调用了 \(k\) 次 orcale，返回了 \(l\) 次结果 1。需要注意，题目中要求是均匀独立地进行 \(k\) 次采样，因此每次采样返回结果 1 的概率总是 \(\frac{M}{N}\)；因此 \(l\) 次采样为 1 的概率就是 \((\frac{M}{N})^l (\frac{N-M}{N})^{k-l}\)；同时，\(k\) 次采样中取出 \(l\) 次采样的数量是 \(C_k^l\)，因此
\(l\) 次采样为 1 的搜索问题解数目估计 \(S(l) = N l / k\)。那么，\(S(l)\) 对于 \(l\) 的平均值是
\(S(l)\) 对于 \(l\) 的平方平均值是
因此，标准差可以计算为
如果我们认为标准差与精度正比挂钩，那么 \(\Delta S < c \sqrt{M}\) 达成的条件是 \(k > (N - M) / c^2\)。尽管说，如果 \(M\) 非常接近于 \(N\)，那么 \(k\) 的次数不需要很多；但题目的要求是对所有的 \(M\) 作估计，因此 \(k\) 的复杂度应当视为与 \(N\) 同等级别，即 \(\Omega(N)\)。
6.6 搜索算法的最优性¶
练习 6.15¶
练习 6.15
利用 Cauchy-Schwarz 不等式，证明对任何归一化状态的向量 \(|\psi\rangle\) 和一组有 \(N\) 个向量的标准正交基向量 \(|x\rangle\)，有
首先我们将求和式的模平方作展开 (其中 \(\mathfrak{R}\) 是取实部的意思)：
因此，注意到 \(x\) 可以是 \(N\) 个正交基向量，因此不等式右的求和总数是 \(N\) 个：
我们定义该正交基的平均加和态为 \(|\chi\rangle = \frac{1}{\sqrt{N}} \sum_x |x\rangle\)，那么
显然对于两个归一的态，\(\mathfrak{R} (\langle \psi | \chi \rangle) \leqslant 1\)；因此
等号只有在 \(\langle \psi | \chi \rangle = 1\) 时取到，即 \(|\psi\rangle = |\chi\rangle = \frac{1}{\sqrt{N}} \sum_x |x\rangle\) 时取到。这个等号取到条件还蛮苛刻的，因为它不仅要求 \(|\psi\rangle\) 在构成上等同于 \(|\chi\rangle\)，而且相位上也要等同。但通过这种方式证明似乎不需要使用到 Cauchy-Schwarz 不等式。
练习 6.16¶
练习 6.16
设对所有可能值 \(x\) 的均匀平均而不是对 \(x\) 的所有值，要求差错的概率小于 \(1/2\)，证明 \(O(\sqrt{N})\) 次 orcale 调用对解搜索问题仍然是必需的。
这个条件意味着原先的对所有 \(x\) 满足 \(|\langle x | \psi_k^x \rangle| \geqslant 1/2\) 变更为了对于 \(x\) 的均匀平均的
回到书中的证明过程，由于 \(F_k\) 不涉及 \(\psi_k^x\)，因此我们只要考察 \(E_k = \sum_x \Vert \psi_k^x - x \Vert^2\) 即可。
这里需要利用模的值不大于 1，因此模本身比模平方要大的性质：
我们可以得到
上述不等号的取得条件极其苛刻，等号成立所有 \(x\) 下是 \(\langle \psi_k^x | x \rangle\) 为 1 或 0。
因此，将上述结果代入书中的式 (6.51)，可得
如果令 \(c\) 是任何小于 \((\sqrt{2} - 1)^2 \simeq 0.17\) 的常数，那么原先的 \(k \geqslant \sqrt{c N / 4}\) 即 \(k = \Omega(\sqrt{N})\) 仍然成立。因此，orcale 调用次数仍然需要 \(O(\sqrt{N})\) 数量级。
练习 6.17 (对多重解的最优性)¶
练习 6.17
假设搜索问题有 \(M\) 个解，证明为找到一个解需要 \(O(\sqrt{N/M})\) 次 orcale 调用。
危险
该练习不打算作证明。详细的证明恐怕需要将整个 6.6 节重新叙述一遍。
我想就如同之前一样，将单个解的 \(|x\rangle\) 的空间转换到多个解的空间就可以了。但为此，许多归一化的过程要引入 \(M\)，这会比较复杂。
第七章 量子计算机：物理实现¶
7.3 谐振子量子计算机¶
该节中的 5 个练习，实际上是让读者在基于位置算符与动量算符的对易关系 \([x, p] = i \hbar\)、以及谐振体系的 Hamiltonian 量 \(H\) (式 (7.4)) 和为了计算方便引入的升降算符 \(a^\dagger, a\) 的定义式 (式 (7.6-7))，完整地推导出谐振体系的各种算符与态关系 (包括式 (7.5, 7.10-12))。
练习 7.1¶
练习 7.1
根据 \(x\) 和 \(p\) 不对易的事实，并且实际上 \([x, p] = i \hbar\)，具体说明 \(a^\dagger a = H / \hbar \omega - 1/2\)。
我们先回顾一下定义式：
那么，
需要记得，算符不一定满足交换律。上述等式右边，\(x, p\) 分别是坐标算符与动量算符，不能像普通变量一样地化简。同时回顾到对易子定义 \([x, p] = xp - px\)，因此，
将 \(H\) 的定义式代入，很容易对原题得到证明。这其实也就对原书中的式 (7.5) 作了证明。
练习 7.2¶
练习 7.2
给定 \([x, p] = i \hbar\)，计算 \([a, a^\dagger]\)。
利用对易子的线性性质 \([A, B + C] = [A, B] + [A, C]\)，有
同一算符间的对易是零即 \([A, A] = 0\)；对易子满足反对易关系即 \([A, B] = - [B, A]\)，因此
练习 7.3¶
练习 7.3
计算 \([H, a]\)，并用这个结果证明，若 \(|\psi\rangle\) 是 \(H\) 的本征态，具有能量 \(E \geqslant n \hbar \omega\)，则 \(a^n |\psi\rangle\) 是具有能量 \(E - n \hbar \omega\) 的一个本征态。
这是对盒子 7.2 关于 \([H, a^\dagger]\) 性质的拓展。
这里我们要利用 \(H\) 的另一个定义：
利用到对易子的乘法分配性质 \([AB, C] = [A, C] B + A [B, C]\)，并利用练习 7.2 的结论，可知，
因此，如果 \(|\psi\rangle\) 为 \(H\) 的本征态且对应能级为 \(E\)，即 \(H |\psi\rangle = E |\psi\rangle\)，则
即 \(a |\psi\rangle\) 此时也会是 \(H\) 的本征态，且对应能级是 \(E - \hbar \omega\)。依此类推，\(a^2 |\psi\rangle\) 的能级比 \(a |\psi\rangle\) 低 \(\hbar \omega\)，即 \(E - 2 \hbar \omega\)，等等。故 \(a^n |\psi\rangle\) 的能级是 \(E - n \hbar \omega\)。
练习 7.4, 7.5¶
这两道体系是对式 (7.10-12) 的补充说明与证明。我们先对练习 7.5 作说明。
练习 7.5
验证式 (7.11) 和式 (7.12) 与式 (7.10) 以及归一化条件 \(\langle n | n \rangle = 1\) 相容。
这里需要作澄清。譬如式 (7.12) 中，等式右边的 \(\sqrt{n} |n-1\rangle\) 的 \(\sqrt{n}\) 表示一个数；而 \(|n-1\rangle\) 表示能级为第 \(n-1\) 波函数，即 \(H |n-1\rangle = (n-1 + 1/2) \hbar \omega |n-1\rangle\)。同理地，式 (7.10) 右边的 \(n |n\rangle\) 中，第一个 \(n\) 是一个数；而第二个 \(|n\rangle\) 是能级为第 \(n\) 的波函数。
事实上，我认为这道题应该要反过来问。有了归一化限制 \(\langle n | n \rangle = 1\) 后，式 (7.10-12) 的推导将会是自然出现的。这些表达式并非人为规定得到的。
我们在练习 7.1 已经对式 (7.5) 作证明：
同时，借用练习 7.3 或盒子 7.2 的结论，我们知道了对于 \(H\) 的本征态 \(|n\rangle\)，其中 \(n = 0, 1, \cdots\)，具有结论
其中，\(E_0 = \hbar \omega / 2\) 是零点能，即 \(|0\rangle\) 的能量。注意这里的 \(|0\rangle\) 不是之前的单量子比特的计算基，而表示的是谐振子的基态。并且，\(|n\rangle\) 可以用产生算符来构造，即 \(|n\rangle \propto (a^\dagger)^n |0\rangle\)。最后的问题其归一化系数应当是多少。
首先是式 (7.10)。该式可以很容易地通过式 (7.5) 给出：
随后是式 (7.12)。我们将上式左乘 \(\langle n|\)，得到
注意到 \(a\) 与 \(a^\dagger\) 在定义上互为自伴算符，因此上式表示的是 \(\big\Vert a|n\rangle \big\Vert^2 = n\)，即该态的归一化常数是 \(\sqrt{n}\)。又依据练习 7.3 的中间推导过程，知道 \(a |n\rangle \propto |n-1\rangle\)，即 \(a\) 作用在 \(|n\rangle\) 之后得到的态是能级比 \(E_n = (n + 1/2) \hbar \omega\) 低 \(\hbar \omega\) 的态 \(|n-1\rangle\)。因此，
最后是式 (7.11)。根据式 (7.12)，我们可以得到推论
我们在盒子 7.2 知道，\(a^\dagger |n-1\rangle \propto |n\rangle\)；依据上式，我们知道归一化系数是 \(\sqrt{n}\)，即
如果我们将 \(n+1\) 替换上式的 \(n\)，那么就立即得到了式 (7.11)。
因此与其说是式 (7.10-12) 与归一化条件相容，不如说是归一化条件导出了式 (7.10-7.12)。
练习 7.4
证明 \(\displaystyle |n\rangle = \frac{(a^\dagger)^n}{\sqrt{n!}} |0\rangle\)。
由式 (7.11)，立即得到
