5.3 应用：求阶和因子问题¶

练习 5.10¶

练习 5.10

证明 \(x=5\) 模 \(N=21\) 的阶是 6。

\[\begin{split} \begin{alignat*}{10} 5^1 & && &&= 5 &&\; (\text{mod } 21) \\ 5^2 &= 5 \times 5 &&= 25 &&= 4 && \; (\text{mod } 21) \\ 5^3 &= 5 \times 4 && &&= 20 && \; (\text{mod } 21) \\ 5^4 &= 5 \times 20 &&= 100 &&= 16 && \; (\text{mod } 21) \\ 5^5 &= 5 \times 16 &&= 80 &&= 17 && \; (\text{mod } 21) \\ 5^6 &= 5 \times 17 &&= 85 &&= 1 && \; (\text{mod } 21) \end{alignat*} \end{split}\]

练习 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\) 是酉的：

\[ U |y\rangle = |xy \; (\text{mod } N)\rangle \]

其中，\(x\) 与 \(N\) 互质，且只有 \(0 \leqslant y \leqslant N-1\) 时的 \(U\) 操作是不平凡的。

我们的目标是证明 \(U^\dagger U = I\)，即考察矩阵元 \((U^\dagger U)_{y' y}\) 是否是 \(\delta_{y' y}\)。

\[ (U^\dagger U)_{y' y} = \langle y' | U^\dagger U | y\rangle = \langle x y' \; (\text{mod } N) | x y \; (\text{mod } N) \rangle \]

若 \(y = y'\)，显然 \((U^\dagger U)_{y y} = 1\)。

若 \(y \neq y'\)，那么

\[ x(y-y') \neq 0 \; (\text{mod} N) \]

这是因为 \(x\) 与 \(N\) 互质，因此不存在非零正整数 \(y-y'\)，使得 \(x (y-y')\) 是 \(N\) 的倍数。整理上式易知

\[ xy' \neq xy \; (\text{mod} N) \]

因此，若 \(y \neq y'\)，则 \((U^\dagger U)_{y' y} = 0\)。证明完毕。

最后，我们指出，\(U^\dagger = U^{-1}\) 操作相当于

\[ U^{-1} |y\rangle = |x^{r-1} y \; (\text{mod } N)\rangle \]

其中，\(r\) 是 \(x\) 模 \(N\) 的阶。

练习 5.13¶

练习 5.13

证明下式：

\[ \frac{1}{\sqrt{r}} \sum_{s=0}^{r-1} e^{2 \pi i s k / r} |u_s\rangle = |x^k \; (\text{mod } N) \rangle \tag{5.45} \]

进而证明

\[ \frac{1}{\sqrt{r}} \sum_{s=0}^{r-1} |u_s\rangle = |1\rangle \tag{5.44} \]

提示：本题证明过程需要利用到下述结论 (也可以参考练习 5.1 的证明过程)：

\[ \sum_{s=0}^{r-1} e^{-2 \pi i s k / r} = r \delta_{k0} \]

回顾式 (5.37)，并将 (5.37) 中的角标 \(k\) 换成 \(k'\)：

\[ |u_s\rangle = \frac{1}{\sqrt{r}} \sum_{k'=0}^{r-1} e^{- 2 \pi i s k' / r} |x^{k'} \; (\text{mod } N) \rangle \]

代入式 (5.45)，则待证等式左为

\[ \mathrm{LHS} = \frac{1}{r} \sum_{s=0}^{r-1} \sum_{k'=0}^{r-1} e^{2 \pi i s (k-k') / r} |x^{k'} \; (\text{mod } N) \rangle \]

利用题目的提示，上式对 \(s\) 的求和可以化为

\[ \mathrm{LHS} = \frac{1}{r} \sum_{k'=0}^{r-1} r \delta_{k' k} |x^{k'} \; (\text{mod } N) \rangle = |x^k \; (\text{mod } N) \rangle \]

因此，式 (5.45) 证明完毕。

对于式 (5.44) 的证明，我们需要利用到练习 5.8 的其中一个证明步骤：对于态 \(\sum_s c_s |u_s\rangle\)，其中 \(|u_s\rangle\) 必须是 \(U\) 的本征态且对应本征值 \(\lambda_s\)，那么 \(U^m\) 作用于该混合态的结果是

\[ U^m \sum_s c_s |u_s\rangle = \sum_s c_s \lambda_s^m |u_s\rangle \]

因此，我们对式 (5.45) 等式两边作用 \(U^{-k}\) (这里的 \(-k\) 尽管是负整数，但由于 \(U^r = I\)，因此其实也可以用 \(U^{r-k}\) 替代作证明)。等式右边为

\[ \mathrm{RHS} = U^{-k} |x^k \; (\text{mod } N) \rangle = | x^{-k} x^k \; (\text{mod } N) \rangle = |1\rangle \]

我们回顾到式 (5.39)，\(|u_s\rangle\) 的本征值是 \(\lambda_s = e^{2 \pi i s / r}\)。因此，

\[\begin{split} \begin{align*} \mathrm{LHS} &= \frac{1}{\sqrt{r}} U^{-k} \sum_{s=0}^{r-1} e^{2 \pi i s k / r} |u_s\rangle = \frac{1}{\sqrt{r}} \sum_{s=0}^{r-1} e^{2 \pi i s k / r} \lambda_s^{-k} |u_s\rangle \\ &= \frac{1}{\sqrt{r}} \sum_{s=0}^{r-1} e^{2 \pi i s k / r} e^{- 2 \pi i s k / r} |u_s\rangle = \frac{1}{\sqrt{r}} \sum_{s=0}^{r-1} |u_s\rangle \end{align*} \end{split}\]

因此，式 (5.44) 证明完毕。

练习 5.14¶

练习 5.14

若我们将第二寄存器初始化为 \(|1\rangle\)，在逆 Fourier 变换之前，求阶算法产生的量子状态是

\[ |\psi\rangle = \sum_{j=0}^{2^t-1} |j\rangle U^j |1\rangle = \sum_{j=0}^{2^t-1} |j\rangle |x^j \; (\text{mod } N)\rangle \tag{5.46} \]

证明如果我们把 \(U^j\) 替换为酉变换 \(V\)，它计算的是

\[ V |j\rangle |k\rangle = |j\rangle |k + x^j \; (\text{mod } N) \rangle \tag{5.47} \]

且让第二寄存器从 \(|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\)。联立两式，得到

\[ \frac{\alpha}{\beta} = \frac{b}{a} \]

我们希望 \(\alpha, \beta\) 要尽可能小；但由于 \(a, b\) 互质，因此 \(\alpha, \beta\) 最小分别是 \(b, a\)。因此，

\[ t = b a g = ag \times bg / g = xy / \gcd(x, y) \]

但至于求最小公倍数的消耗，在附录 D.2 节的 Euclid 辗转相除法叙述中，我们知道 \(\gcd\) 消耗是 \(O(L^3)\) 的；因此总的耗时应该是 \(O(L^3)\)，或许题目给错了。

但不论怎么说，求 \(\gcd\) 是多项式时间可完成的；而且完全可以交给经典计算机完成。

练习 5.16¶

练习 5.16

对所有的 \(x \geqslant 2\)，证明

\[ \int_x^{x+1} \frac{1}{y^2} \, \mathrm{d} y \geqslant \frac{2}{3 x^2} \]

进而证明下式

\[ \sum_{q} \frac{1}{q^2} \leqslant \frac{3}{2} \int_2^{+\infty} \frac{1}{y^2} \, \mathrm{d} y = \frac{3}{4} \tag{5.59} \]

由上式，可知式 (5.58) 成立：

\[ 1 - \sum_{q} p(q| s_1') p(q| s_2') \geqslant 1 - \sum_{q} \frac{1}{q^2} \geqslant \frac{1}{4} \tag{5.58} \]

这里关于 \(q\) 的求和是对素数的求和。

首先我们验证定积分

\[ \int_x^{x+1} \frac{1}{y^2} \, \mathrm{d} y = \frac{1}{x(x+1)} \geqslant \frac{2}{3x^2} \quad \text{i.e.} \quad \frac{1}{x^2} \leqslant \frac{3}{2} \int_x^{x+1} \frac{1}{y^2} \, \mathrm{d} y \]

之所以不等式成立，是因为我们利用了 \(x \geqslant 2\) 的条件：

\[ x \geqslant 2 \Rightarrow x^2 \geqslant 2x \Rightarrow 3x^2 \geqslant 2x^2 + 2x \xrightarrow{\text{divided by } 3 x^3(x+1)} \frac{1}{x(x+1)} \geqslant \frac{2}{3 x^2} \]

随后证明 \(\sum_q q^{-2}\) 的不等式 (注意关于素数 \(q\) 的求和范围比对 \(x\geqslant 2\) 的范围要小一些)：

\[ \sum_q \frac{1}{q^2} < \sum_{x=2}^\infty \frac{1}{x^2} \leqslant \frac{3}{2} \sum_{x=2}^\infty \int_x^{x+1} \frac{1}{y^2} \, \mathrm{d} y = \frac{3}{2} \int_2^{+\infty} \frac{1}{y^2} \, \mathrm{d} y = \frac{3}{2} \times \frac{1}{2} = \frac{3}{4} \]

因此，式 (5.58) 成立。事实上，即使是使用上述粗糙的证明过程，式 (5.58) 的后一个不等号 \(\geqslant\) 也完全可以写为 \(>\)。

作为简单的补充，实际上下述过程成立：

\[ \sum_q \frac{1}{q^2} < \sum_{x=2}^\infty \frac{1}{x^2} = \frac{\pi^2}{6} - 1 \simeq 0.645 \]

因此，

\[ 1 - \sum_{q} p(q| s_1') p(q| s_2') > 2 - \frac{\pi^2}{6} \simeq 0.355 \]

即作两次相位估计给出 \(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\) 的阶。

\[\begin{split} \begin{alignat*}{10} 4^1 &= &&= 4 &&= 4 && \; (\text{mod } 91) \\ 4^2 &= 4 \times 4 &&= 16 &&= 16 && \; (\text{mod } 91) \\ 4^3 &= 16 \times 4 &&= 64 &&= 64 && \; (\text{mod } 91) \\ 4^4 &= 64 \times 4 &&= 256 &&= 74 && \; (\text{mod } 91) \\ 4^5 &= 74 \times 4 &&= 296 &&= 23 && \; (\text{mod } 91) \\ 4^6 &= 23 \times 4 &&= 92 &&= 1 && \; (\text{mod } 91) \\ \end{alignat*} \end{split}\]

因此，阶 \(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) 所言。

量子计算与量子信息 习题解答 文档