{ "cells": [ { "cell_type": "markdown", "id": "0d491d0f", "metadata": {}, "source": [ "# 5.3 应用：求阶和因子问题" ] }, { "cell_type": "markdown", "id": "61af74e7", "metadata": {}, "source": [ "## 练习 5.10" ] }, { "cell_type": "markdown", "id": "d19d953c", "metadata": {}, "source": [ ":::{admonition} 练习 5.10\n", "\n", "证明 $x=5$ 模 $N=21$ 的阶是 6。\n", "\n", ":::" ] }, { "cell_type": "markdown", "id": "d63750ea", "metadata": {}, "source": [ "$$\n", "\\begin{alignat*}{10}\n", "5^1 & && &&= 5 &&\\; (\\text{mod } 21) \\\\\n", "5^2 &= 5 \\times 5 &&= 25 &&= 4 && \\; (\\text{mod } 21) \\\\\n", "5^3 &= 5 \\times 4 && &&= 20 && \\; (\\text{mod } 21) \\\\\n", "5^4 &= 5 \\times 20 &&= 100 &&= 16 && \\; (\\text{mod } 21) \\\\\n", "5^5 &= 5 \\times 16 &&= 80 &&= 17 && \\; (\\text{mod } 21) \\\\\n", "5^6 &= 5 \\times 17 &&= 85 &&= 1 && \\; (\\text{mod } 21)\n", "\\end{alignat*}\n", "$$" ] }, { "cell_type": "markdown", "id": "65911327", "metadata": {}, "source": [ "## 练习 5.11" ] }, { "cell_type": "markdown", "id": "9e480041", "metadata": {}, "source": [ ":::{admonition} 练习 5.11\n", "\n", "证明 $x$ 的阶满足 $r \\leqslant N$。\n", "\n", ":::" ] }, { "cell_type": "markdown", "id": "767d9cc3", "metadata": {}, "source": [ "依据阶的定义，$x$ 与 $N$ 无公因子，即互质。由定理 D.9 (Euler)，$x^{\\varphi(N)} = 1 \\; (\\text{mod } N)$，其中 $\\varphi(N)$ 是 Euler $\\varphi$ 函数，即小于 $N$ 且与 $N$ 互质的正整数。因此，阶一定不大于 $\\varphi(N) < N$。" ] }, { "cell_type": "markdown", "id": "a76a18e6", "metadata": {}, "source": [ "但需要注意，阶未必需要是 $\\varphi(N)$。譬如，对于练习 5.10 的例子而言，$\\varphi(21) = 18$ (20 个整数去除 $3, 7$；注意 $1$ 与任何数互质)；但阶是 6。" ] }, { "cell_type": "markdown", "id": "b134ebf7", "metadata": {}, "source": [ "## 练习 5.12" ] }, { "cell_type": "markdown", "id": "a9cd9a64", "metadata": {}, "source": [ ":::{admonition} 练习 5.12\n", "\n", "证明式 (5.36) 所给出的 $U$ 是酉的：\n", "\n", "$$\n", "U |y\\rangle = |xy \\; (\\text{mod } N)\\rangle\n", "$$\n", "\n", "其中，$x$ 与 $N$ 互质，且只有 $0 \\leqslant y \\leqslant N-1$ 时的 $U$ 操作是不平凡的。\n", "\n", ":::" ] }, { "cell_type": "markdown", "id": "1b2b1d1c", "metadata": {}, "source": [ "我们的目标是证明 $U^\\dagger U = I$，即考察矩阵元 $(U^\\dagger U)_{y' y}$ 是否是 $\\delta_{y' y}$。\n", "\n", "$$\n", "(U^\\dagger U)_{y' y} = \\langle y' | U^\\dagger U | y\\rangle = \\langle x y' \\; (\\text{mod } N) | x y \\; (\\text{mod } N) \\rangle\n", "$$" ] }, { "cell_type": "markdown", "id": "8b72eb94", "metadata": {}, "source": [ "若 $y = y'$，显然 $(U^\\dagger U)_{y y} = 1$。\n", "\n", "若 $y \\neq y'$，那么\n", "\n", "$$\n", "x(y-y') \\neq 0 \\; (\\text{mod} N)\n", "$$\n", "\n", "这是因为 $x$ 与 $N$ 互质，因此不存在非零正整数 $y-y'$，使得 $x (y-y')$ 是 $N$ 的倍数。整理上式易知\n", "\n", "$$\n", "xy' \\neq xy \\; (\\text{mod} N)\n", "$$\n", "\n", "因此，若 $y \\neq y'$，则 $(U^\\dagger U)_{y' y} = 0$。证明完毕。" ] }, { "cell_type": "markdown", "id": "7bf2a9ef", "metadata": {}, "source": [ "最后，我们指出，$U^\\dagger = U^{-1}$ 操作相当于\n", "\n", "$$\n", "U^{-1} |y\\rangle = |x^{r-1} y \\; (\\text{mod } N)\\rangle\n", "$$\n", "\n", "其中，$r$ 是 $x$ 模 $N$ 的阶。" ] }, { "cell_type": "markdown", "id": "1c5612eb", "metadata": {}, "source": [ "## 练习 5.13" ] }, { "cell_type": "markdown", "id": "98b7bab7", "metadata": {}, "source": [ ":::{admonition} 练习 5.13\n", "\n", "证明下式：\n", "\n", "$$\n", "\\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\n", "\\tag{5.45}\n", "$$\n", "\n", "进而证明\n", "\n", "$$\n", "\\frac{1}{\\sqrt{r}} \\sum_{s=0}^{r-1} |u_s\\rangle = |1\\rangle\n", "\\tag{5.44}\n", "$$\n", "\n", "提示：本题证明过程需要利用到下述结论 (也可以参考练习 5.1 的证明过程)：\n", "\n", "$$\n", "\\sum_{s=0}^{r-1} e^{-2 \\pi i s k / r} = r \\delta_{k0}\n", "$$\n", "\n", ":::" ] }, { "cell_type": "markdown", "id": "5e280af6", "metadata": {}, "source": [ "回顾式 (5.37)，并将 (5.37) 中的角标 $k$ 换成 $k'$：\n", "\n", "$$\n", "|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\n", "$$" ] }, { "cell_type": "markdown", "id": "dd880fe0", "metadata": {}, "source": [ "代入式 (5.45)，则待证等式左为\n", "\n", "$$\n", "\\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\n", "$$" ] }, { "cell_type": "markdown", "id": "1e8bbe57", "metadata": {}, "source": [ "利用题目的提示，上式对 $s$ 的求和可以化为\n", "\n", "$$\n", "\\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\n", "$$" ] }, { "cell_type": "markdown", "id": "32dd6211", "metadata": {}, "source": [ "因此，式 (5.45) 证明完毕。" ] }, { "cell_type": "markdown", "id": "b3c59d32", "metadata": {}, "source": [ "---" ] }, { "cell_type": "markdown", "id": "a2ac81df", "metadata": {}, "source": [ "对于式 (5.44) 的证明，我们需要利用到练习 5.8 的其中一个证明步骤：对于态 $\\sum_s c_s |u_s\\rangle$，其中 $|u_s\\rangle$ **必须是** $U$ 的本征态且对应本征值 $\\lambda_s$，那么 $U^m$ 作用于该混合态的结果是\n", "\n", "$$\n", "U^m \\sum_s c_s |u_s\\rangle = \\sum_s c_s \\lambda_s^m |u_s\\rangle\n", "$$" ] }, { "cell_type": "markdown", "id": "5a714502", "metadata": {}, "source": [ "因此，我们对式 (5.45) 等式两边作用 $U^{-k}$ (这里的 $-k$ 尽管是负整数，但由于 $U^r = I$，因此其实也可以用 $U^{r-k}$ 替代作证明)。等式右边为\n", "\n", "$$\n", "\\mathrm{RHS} = U^{-k} |x^k \\; (\\text{mod } N) \\rangle = | x^{-k} x^k \\; (\\text{mod } N) \\rangle = |1\\rangle\n", "$$" ] }, { "cell_type": "markdown", "id": "6d1bdc25", "metadata": {}, "source": [ "我们回顾到式 (5.39)，$|u_s\\rangle$ 的本征值是 $\\lambda_s = e^{2 \\pi i s / r}$。因此，\n", "\n", "$$\n", "\\begin{align*}\n", "\\mathrm{LHS} &= \\frac{1}{\\sqrt{r}} U^{-k} \\sum_{s=0}^{r-1} e^{2 \\pi i s k / r} |u_s\\rangle\n", "= \\frac{1}{\\sqrt{r}} \\sum_{s=0}^{r-1} e^{2 \\pi i s k / r} \\lambda_s^{-k} |u_s\\rangle \\\\\n", "&= \\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\n", "= \\frac{1}{\\sqrt{r}} \\sum_{s=0}^{r-1} |u_s\\rangle\n", "\\end{align*}\n", "$$\n", "\n", "因此，式 (5.44) 证明完毕。" ] }, { "cell_type": "markdown", "id": "da074d24", "metadata": {}, "source": [ "## 练习 5.14" ] }, { "cell_type": "markdown", "id": "c6f43b61", "metadata": {}, "source": [ ":::{admonition} 练习 5.14\n", "\n", "若我们将第二寄存器初始化为 $|1\\rangle$，在逆 Fourier 变换之前，求阶算法产生的量子状态是\n", "\n", "$$\n", "|\\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\n", "\\tag{5.46}\n", "$$\n", "\n", "证明如果我们把 $U^j$ 替换为酉变换 $V$，它计算的是\n", "\n", "$$\n", "V |j\\rangle |k\\rangle = |j\\rangle |k + x^j \\; (\\text{mod } N) \\rangle\n", "\\tag{5.47}\n", "$$\n", "\n", "且让第二寄存器从 $|0\\rangle$ 开始，那么将得到同样的状态。同时说明如何仍然用 $O(L^3)$ 个门构造 $V$。\n", "\n", ":::" ] }, { "cell_type": "markdown", "id": "d4979816", "metadata": {}, "source": [ "$V$ 与 $U^j$ 的等价性是显然的；只要将 $k = 0$ 代入即可。由于加法运算的门路估计是 $O(L)$，而 $x^j$ 门路估计是 $O(L^3)$，因此总地来说仍然是 $O(L^3)$ 门路复杂度。" ] }, { "cell_type": "markdown", "id": "c65b2b8c", "metadata": {}, "source": [ "## 练习 5.15" ] }, { "cell_type": "markdown", "id": "4946859d", "metadata": {}, "source": [ ":::{admonition} 练习 5.15\n", "\n", "证明正整数 $x$ 和 $y$ 的最小公倍数是 $xy / \\gcd(x, y)$，其中 $\\gcd (x, y)$ 表示 $x, y$ 的最大公因子。因此若 $x$ 和 $y$ 是 $L$ 比特数，那么最小公倍数可以在 $O(L^2)$ 步运算内算出。\n", "\n", ":::" ] }, { "cell_type": "markdown", "id": "7b0676b1", "metadata": {}, "source": [ "这应该是初中竞赛题里不需要额外说明，就可以使用的定理吧。这里只是简单的说明而已。\n", "\n", "令 $g = \\gcd(x, y)$，那么可以定义整数 $a, b$ 使得 $x = ag, y = bg$。显然 $\\gcd(a, b) = 1$，否则 $\\gcd(x, y)$ 就可以写成 $\\gcd(a, b) g$ 了。\n", "\n", "现在令最小公倍数 $t$，即 $x | t$ 且 $y | t$。那么可以设正整数 $\\alpha, \\beta$ 使得 $t = \\alpha x = \\alpha a g$；同时 $t = \\beta y = \\beta b g$。联立两式，得到\n", "\n", "$$\n", "\\frac{\\alpha}{\\beta} = \\frac{b}{a}\n", "$$\n", "\n", "我们希望 $\\alpha, \\beta$ 要尽可能小；但由于 $a, b$ 互质，因此 $\\alpha, \\beta$ 最小分别是 $b, a$。因此，\n", "\n", "$$\n", "t = b a g = ag \\times bg / g = xy / \\gcd(x, y)\n", "$$" ] }, { "cell_type": "markdown", "id": "ec6cf179", "metadata": {}, "source": [ "---" ] }, { "cell_type": "markdown", "id": "ec495d36", "metadata": {}, "source": [ "但至于求最小公倍数的消耗，在附录 D.2 节的 Euclid 辗转相除法叙述中，我们知道 $\\gcd$ 消耗是 $O(L^3)$ 的；因此总的耗时应该是 $O(L^3)$，或许题目给错了。\n", "\n", "但不论怎么说，求 $\\gcd$ 是多项式时间可完成的；而且完全可以交给经典计算机完成。" ] }, { "cell_type": "markdown", "id": "3d085bdb", "metadata": {}, "source": [ "## 练习 5.16" ] }, { "cell_type": "markdown", "id": "853262af", "metadata": {}, "source": [ ":::{admonition} 练习 5.16\n", "\n", "对所有的 $x \\geqslant 2$，证明\n", "\n", "$$\n", "\\int_x^{x+1} \\frac{1}{y^2} \\, \\mathrm{d} y \\geqslant \\frac{2}{3 x^2}\n", "$$\n", "\n", "进而证明下式\n", "\n", "$$\n", "\\sum_{q} \\frac{1}{q^2} \\leqslant \\frac{3}{2} \\int_2^{+\\infty} \\frac{1}{y^2} \\, \\mathrm{d} y = \\frac{3}{4}\n", "\\tag{5.59}\n", "$$\n", "\n", "由上式，可知式 (5.58) 成立：\n", "\n", "$$\n", "1 - \\sum_{q} p(q| s_1') p(q| s_2') \\geqslant 1 - \\sum_{q} \\frac{1}{q^2} \\geqslant \\frac{1}{4}\n", "\\tag{5.58}\n", "$$\n", "\n", "这里关于 $q$ 的求和是对素数的求和。\n", "\n", ":::" ] }, { "cell_type": "markdown", "id": "82bb6508", "metadata": {}, "source": [ "首先我们验证定积分\n", "\n", "$$\n", "\\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\n", "$$\n", "\n", "之所以不等式成立，是因为我们利用了 $x \\geqslant 2$ 的条件：\n", "\n", "$$\n", "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}\n", "$$" ] }, { "cell_type": "markdown", "id": "b99af947", "metadata": {}, "source": [ "随后证明 $\\sum_q q^{-2}$ 的不等式 (注意关于素数 $q$ 的求和范围比对 $x\\geqslant 2$ 的范围要小一些)：\n", "\n", "$$\n", "\\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}\n", "$$\n", "\n", "因此，式 (5.58) 成立。事实上，即使是使用上述粗糙的证明过程，式 (5.58) 的后一个不等号 $\\geqslant$ 也完全可以写为 $>$。" ] }, { "cell_type": "markdown", "id": "170bf258", "metadata": {}, "source": [ "---" ] }, { "cell_type": "markdown", "id": "74be2686", "metadata": {}, "source": [ "作为简单的补充，实际上下述过程成立：\n", "\n", "$$\n", "\\sum_q \\frac{1}{q^2} < \\sum_{x=2}^\\infty \\frac{1}{x^2} = \\frac{\\pi^2}{6} - 1 \\simeq 0.645\n", "$$\n", "\n", "因此，\n", "\n", "$$\n", "1 - \\sum_{q} p(q| s_1') p(q| s_2') > 2 - \\frac{\\pi^2}{6} \\simeq 0.355\n", "$$\n", "\n", "即作两次相位估计给出 $r_1', r_2'$；而后通过求取最大公倍数的方法得到阶的做法，正确率不止书上提到的 1/4 即 25%；它至少可以达到 35.5% 甚至更高。" ] }, { "cell_type": "markdown", "id": "3bd6ee48", "metadata": {}, "source": [ "## 练习 5.17" ] }, { "cell_type": "markdown", "id": "7ad6062a", "metadata": {}, "source": [ ":::{admonition} 练习 5.17\n", "\n", "设 $N$ 为 $L$ 比特长。本练习的目的是找出一个有效的经典算法，判定 $N = a^b$ 是否对某些整数 $a > 1$ 和 $b \\geqslant 2$ 成立。这可以按如下步骤达到。\n", "\n", "1. 证明若这样的 $b$ 存在，则必满足 $b \\leqslant L$；\n", "2. 证明为计算 $y = \\log_2 N$，对 $b \\leqslant L$ 计算 $x = y / b$，以及计算两个最接近 $2^x$ 的整数 $u_1, u_2$，至多需要 $O(L^2)$ 个运算；\n", "3. 证明为计算 $u_1^b$ 和 $u_2^b$ (反复使用平方) 和检查它们是否等于 $N$，至多需要 $O(L^2)$ 个运算；\n", "4. 将前面的结果结合起来，给出一个 $O(L^3)$ 的算法，以判定 $N=a^b$ 是否对整数 $a$ 和 $b$ 成立。\n", "\n", ":::" ] }, { "cell_type": "markdown", "id": "fc37b8c9", "metadata": {}, "source": [ ":::{warning}\n", "\n", "本题可能存在诸多问题。\n", "\n", "- 整数 $N$ 应当要是 $L \\geqslant 2$ 比特的，否则会出现 $a = 1$ 的情况；这个情况不值得讨论；见下述网站论述：\n", "\n", " > https://serab.net/docs/qcqi/chapter5/#517\n", "\n", "- 第 2 小题已经作更正，即令 $y = \\log_2 N$；见下述网站论述：\n", "\n", " > https://quantumcomputing.stackexchange.com/questions/11394/not-sure-what-do-nielsen-and-chuang-mean-by-number-of-operations\n", " >\n", " > https://math.stackexchange.com/questions/1362724/algorithm-for-determining-whether-n-ab\n", "\n", "- 一些基本数学运算的复杂度可以参考：\n", "\n", " > https://quantumcomputing.stackexchange.com/questions/11394/not-sure-what-do-nielsen-and-chuang-mean-by-number-of-operations\n", " >\n", " > https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations\n", "\n", ":::" ] }, { "cell_type": "markdown", "id": "fdde7662", "metadata": {}, "source": [ "首先，$y = \\log_2 N$ 的操作，目前最优秀的算法应当是 $O(L^2 \\log L)$；但它只需要计算一次。\n", "\n", "1. 若存在，则 $b = \\log_a N \\leqslant \\log_2 N \\leqslant L$；这意味着整个算法可以以 $b = 2, 3, \\cdots, L$ 来循环，循环带来的复杂度是 $O(L)$。\n", "2. 若我们认为乘除法的复杂度是 $O(L^2)$，$2^x$ 运算也是 $O(L^2)$，那么这里总复杂度是 $O(L^2)$。但我不太确定 $2^x$ 作为幂次算法是否确实是 $O(L^2)$ 的，特别是这里的 $x$ 不是整数，因此 $2^x$ 不能简单地通过位移实现。\n", "3. 这里我们不需要直接计算幂次；因为我们对 $b$ 进行迭代，因此这里实际需要的计算是 $u_1^{b-1} \\times u_1$，其中 $u_1^{b-1}$ 是被储存的数值；当然这里以额外内存空间作为代价。因此，计算复杂度与乘法相同，是 $O(L^2)$。\n", "4. 第 2、3 步的总复杂度是 $O(L^2)$，而它们包含在 $O(L)$ 次的循环中，因此总复杂度是 $O(L^3)$。" ] }, { "cell_type": "markdown", "id": "2944709d", "metadata": {}, "source": [ "## 练习 5.18 (因式分解 91)" ] }, { "cell_type": "markdown", "id": "7d96ad1f", "metadata": {}, "source": [ ":::{admonition} 练习 5.18\n", "\n", "假设我们希望因式分解 $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$ 的最有效方法。的确，如果所有的计算都在经典计算机上进行，这个规约不会导致一个有效的因式分解算法；因为上不知道在经典计算机上解决求阶问题的有效算法。\n", "\n", ":::" ] }, { "cell_type": "markdown", "id": "21973f82", "metadata": {}, "source": [ "我们回顾到算法**因式分解到求阶的归约**。第 1 步，若 $N$ 是偶数，返回因子 2；但 91 不是偶数。第 2 步，是否有 $N = 91 = a^b$ 的表达式，但显然不是。第 3 步，$\\gcd(4, 91) = 1$，因此将继续进行到第 4 步求 $x$ 模 $N$ 的阶。" ] }, { "cell_type": "markdown", "id": "83df6a17", "metadata": {}, "source": [ "$$\n", "\\begin{alignat*}{10}\n", "4^1 &= &&= 4 &&= 4 && \\; (\\text{mod } 91) \\\\\n", "4^2 &= 4 \\times 4 &&= 16 &&= 16 && \\; (\\text{mod } 91) \\\\\n", "4^3 &= 16 \\times 4 &&= 64 &&= 64 && \\; (\\text{mod } 91) \\\\\n", "4^4 &= 64 \\times 4 &&= 256 &&= 74 && \\; (\\text{mod } 91) \\\\\n", "4^5 &= 74 \\times 4 &&= 296 &&= 23 && \\; (\\text{mod } 91) \\\\\n", "4^6 &= 23 \\times 4 &&= 92 &&= 1 && \\; (\\text{mod } 91) \\\\\n", "\\end{alignat*}\n", "$$\n", "\n", "因此，阶 $r = 6$；恰巧 $r$ 为偶数且 $4^{r/2} = 64 \\neq -1 \\; (\\text{mod } 91)$。因此，算法成立。" ] }, { "cell_type": "markdown", "id": "2bae77bb", "metadata": {}, "source": [ "第 5 步，我们发现 $\\gcd(4^3-1, 91) = 7 \\; (\\text{mod } 91)$ 且 $\\gcd(4^3+1, 91) = 13 \\; (\\text{mod } 91)$。因此，我们发现 $7, 13$ 都是 91 的因数。" ] }, { "cell_type": "markdown", "id": "dda18fc4", "metadata": {}, "source": [ "事实上，求阶的过程在经典计算机上，需要通过枚举给出；这对于非常大的数而言是非常低效的。在量子计算机上，则可能在一定概率下给出。" ] }, { "cell_type": "markdown", "id": "d286a6d0", "metadata": {}, "source": [ "## 练习 5.19" ] }, { "cell_type": "markdown", "id": "0d3dbd53", "metadata": {}, "source": [ ":::{admonition} 练习 5.19\n", "\n", "证明 $N=15$ 是需要用到求阶子程序的最小数，即它是即非偶数又非更小正整数幂的最小合数。\n", "\n", ":::" ] }, { "cell_type": "markdown", "id": "4b42f3cb", "metadata": {}, "source": [ "若依据书中的算法**因式分解到求阶的归约**，那么第 1 条排除所有偶数；第 2 条排除正整数幂 $3^2=9$。因此，满足条件的最小的合数确实就是 $3 \\times 5 = 15$。在盒子 5.4 中，书中也表明 15 确实可以被量子算法有效地因式分解。" ] }, { "cell_type": "markdown", "id": "bea6a8fc", "metadata": {}, "source": [ "当然，我自己其实比较怀疑，这是否是个偶然。按理来说，如果不考虑第二条性质，那么最小的合数会是 $9$。但在这种情况下，$1$ 是平凡的、$3, 6$ 是有公因子的；\n", "\n", "- $2$ 的阶是 $6$，但 $2^3=8 \\; (\\text{mod } 9) = -1$；\n", "- $4$ 的阶是 $3$，阶恰好不是偶数；\n", "- $5$ 的阶是 $6$，但 $5^3=8 \\; (\\text{mod } 9) = -1$；\n", "- $7$ 的阶是 $3$，阶恰好不是偶数；\n", "- $8$ 的阶是 $2$，但 $8^1=8 \\; (\\text{mod } 9) = -1$；\n", "\n", "因此，在当前的算法下，我们确实无法分解 $9$。我也不清楚是否与偶数和幂次数有关；但这可能确实地表明，基于书中所提到的相位估计的 Shor 算法，不一定完美地分解所有合数。这会是源于阶不是奇数的性质、以及阶除以 2 后幂次恰为 -1 的性质。但可能对于足够大的数而言，这种情况发生的概率非常小，如书中式 (5.60) 所言。" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.8.5" } }, "nbformat": 4, "nbformat_minor": 5 }