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\) 的样子了。