shor算法详细分析.pdf

发布时间：2022-06-08 发布人：admin 分类：说明书资料大小：0.77M 资料格式：pdf 举报版权申诉

第1页 / 共7页

passenger12234-12611358-shor算法详细分析.pdf-第2页.png

第2页 / 共7页

passenger12234-12611358-shor算法详细分析.pdf-第3页.png

第3页 / 共7页

passenger12234-12611358-shor算法详细分析.pdf-第4页.png

第4页 / 共7页

passenger12234-12611358-shor算法详细分析.pdf-第5页.png

第5页 / 共7页

passenger12234-12611358-shor算法详细分析.pdf-第6页.png

第6页 / 共7页

passenger12234-12611358-shor算法详细分析.pdf-第7页.png

第7页 / 共7页

文本预览

从逻辑层面谈量子计算 2020 年 7 月 13 日摘要: 本文从量子计算的逻辑层面出发，分析量子计算的逻辑门架构，再以此为基础，讨论两种典型的量子算法，最后再从量子算法所需要的硬件条件来分析当下量子计算的实现困难与发展方向。关键词: 量子逻辑门，Deutsch-Jozsa算法，shor算法 1 基本的量子逻辑门介绍 1.2 Pauli-X门 1.1 Hadamard门 1√ 2 比如输入|0就得到输出 1 态转化为一个叠加态。 1 1 1 −1 2 (|0 + |1)，H门使得基 (1) RX矩阵由Pauli-X门生成 2 ) −isin( θ cos( θ 2 ) −isin( θ cos( θ 2 ) 2 ) (4) RX(θ) = 1 经典计算机在逻辑层面的基础是nand门， or门，and门等一些简单的逻辑门，然后再通过这些逻辑门的组合完成复杂的功能。量子计算机也不例外。但和经典计算机不同的是，单量子比特由于存在叠加态，需要用一个2维向量来表示，自然，n个量子比特状态的统一表示就需要用2n维的向量来进行表示。因此，操纵单量子比特的量子逻辑门应当是一个2*2的矩阵，而操纵2个量子比特的量子逻辑门则是4*4的矩阵。另外，从硬件实现上来讲，因为量子计算机的输入输出都是某一力学量的本征态的叠加，要求系数模的平方和为1。因此表示量子比特的向量必定模长为1，这要求量子逻辑门是酉矩阵，变换不改变向量的长度。 0 1 1 0 (2) Pauli-X门也称为Not门，对于任意一种叠加态输入 α|0 + β |1，输出为 β |0 + α|1。 1.3 Pauli-Y与Pauli-Z门 0 −i 0 i 1 0 0 −1 (3) 左边的矩阵对应Pauli-Y门，右边的矩阵对应Pauli-Z门， 3种Pauli门作为生成元可以构成RX，RY，RZ矩阵。 1.4 RX(θ),RY(θ),RZ(θ)门

(5) (6) RX矩阵由Pauli-Y门生成 RY (θ) = 2 ) −sin( θ cos( θ 2 ) cos( θ sin( θ 2 ) 2 ) RZ矩阵由Pauli-Z门生成 RZ(θ) = 1 0 0 eiθ 1.5 多量子比特逻辑门例如输入为|11时，输出为|10  1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 eiθ  (9) CR(θ) = CR门是受控的相转门，当高位的控制比特为0时，CR门输入输出相同，当高位的控制比特为1时，CR门会将低位目标比特的处于|1态的部分相位增加θ，但不会改变目标比特的处于|0态的部分（这里我们是考虑了低位处于叠加态的情况）。CR门在shor算法中构建量子傅里叶变换十分有用。首先进行一个符号约定，当我们写多量子比特的狄拉克符号来描述多量子系统的状态时，最 2 两种量子算法分析左边的量子比特称为最高位，而最右边的量子比特称为最低位。例如|01,我们称0为最高位，1为最低位。这个狄拉克符号描述了两量子比特系统的状态，低位量子比特处于|1态，高位量子比特处于|0态。向量表示：  =  0 1 0 0 1 0 ⊗ 0 1 |01 = 其中⊗表示张量积一些常用的两量子比特逻辑门：   1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 CON T = 2.1 Deutsch–Jozsa算法 Deutsch-Jozsa算法是第一个被提出来的量子算法（尽管它的实际意义并不明显）。它关心的是如下问题：给出函数f (x)，接收n个比特的输入，输出0或者1，那么输入一共有2n种可能，假设f (x)仅有两种情况，要么恒为常数（称为好函数），要么针对一半的输入会输出0（称为坏函数），另一半的输入会输出1。现在需要判断f (x)属于哪种函数。在经典计算机中，要确保得到正确的结果，显然，在最坏的情况下，我们需要进行2n−1 + 1次输入才能确保得到正确的结果。而Deutsch–Jozsa算法指出，在量子计算机中，只需要一次输入即可得到结果。 2.1.1 算法的逻辑电路实现 (7) (8) 这种形式的CNOT门对应高位为控制比特，低位为目标比特，CNOT门不改变控制比特的状态，当输入的控制比特为0时，不改变目标比特的状态，当输入控制比特为1时，将目标比特翻转。图 1: 该算法的逻辑电路 ⊗n表示该行实际上有n行，因此电路中 2

不论x = 0或者1，总有 H |x = 1√ 2 (−1)x·z |z (14) 由此可得 H |x1 H |x2 = 1√ 22 因此我们可以得到一般的结果 (−1)x1·x2+z1·z2 |z1|z2 (15) z∈{1,2} z1,z2∈{0,1} 2n−1 z=0 H⊗n |x = 1√ 2n (−1)x·z |z (16) 这里的x，z都是用十进制数字来表示n个量子比特的状态，x · z应该理解为x1 · z1 + ··· + xn · zn，其中x1 ··· xn, z1 ··· zn是x和z的二进制表示这样我们得到了前n个量子比特的系统此时的状态（这里我们忽略了第n+1个比特，因为最后不会对它进行测量） 2n−1 2n−1 x=0 z=0 1√ 2n (−1)f (x)+x·z |z (17) 逻辑电路图中的M表示测量，我们来分析一下不同的f (x)对应的测量结果会有什么不同。如果f (x)是好函数，则f (x)恒为0或者1，当z = 0时（注意是十进制的0），(−1)f (x)+x·z对于任意的x都是同号的，因此我们得到|0前面的系数为1或者-1，这意味着如果f (x)是好函数，我们必定测量到系统的状态为|0，如果f (x)是坏函数，当z = 0时，(−1)f (x)+x·z对于一半的x是1，对于另一半的x是-1，因此|0前面的系数为0.我们测到系统的状态不可能是|0，这样我们通过一次输入，根据最终的测量结果便能够判断f (x)的类型。有n个处于|0态的量子比特输入，1个处于|1态的量子比特输入，每个量子比特都会经过一个hadamard门，这里的黑匣U由f (x)包装而成，接收n + 1个量子比特的输入，输入输入关系为：|y|x ⇒ |y (|x ⊕ |f (y)，注意这个|y是描述的是n个量子比特系统，而x是描述的是1个量子比特系统，⊕表示模2的加法。再做一个符号约定：由于多量子比特系统可以通过描述子系统的狄拉克符号的张量积表示，为了简便，我们通常省略张量积符号(例如上面的y和x)。此外，由于多量子系统的本征态是用一串0，1序列的狄拉克符号表示，因此我们可以用直接用一个十进制数替代01序列(例如上面的y就可以理解为取值为0到2n − 1的整数) 2.1.2 算法过程分析该电路接收的输入为|0|1(注意这个0是十进制的0，描述n个量子比特的系统)，每个量子比特经过H门，系统状态变为 (|0) + |1)··· (|0 + |1) (|0 − |1) (10) 1√ 2n+1 或者可以写为 1√ 2n+1 n 2n−1 x=0 |x (|0 − |1) (11) 经过算子U作用后，系统状态演化为 |x (|0 ⊕ f (x) − |1 ⊕ f (x)) (12) 容易看出，不论f (x)的值为0还是1，系统的状态都可以表示为 2n−1 x=0 1√ 2n+1 2n−1 1√ 2n+1 (−1)f (x) |x (|0 − |1) 2.1.3 Deutsch–Jozsa算法的评析 (13) x=0 本质上来说，我们之所以能够通过一次输然后将n个H门作用在前n个量子比特上，我们需要计算H⊗n |x，注意到在单量子比特的情况下，入判断出f (x)的类型，是因为我们能够输入叠加态，而输入的这种叠加态恰好能够把f (x)的 3

性质完全地反应出来（或者说,当我们向f (x)输 (|0 + |1)时，相当于同时输入了0和1，实入 1√ 2 现了并行计算，因此我们把初始比特通过H门之后再作为U的输入，就相当于一次性把所有情况都输入进去了。但是我们并不能直接拿到并行计算的结果，这依赖于测量）。而经典计算机只能输入0,1，没有办法同时输入多种状态。要得到f (x)的可能输出，就需要重复输入，这花费了大量时间。这种同时输入多种状态实现并行计算的想法在shor算法中我们还会看到。 2.2 shor算法 shor算法是Peter shor在1994年提出的一种量子算法，主要用来实现大数分解（说“主要”是因为shor算法的应用不仅于此，还可以用来计算离散对数等）。shor算法的亮眼之处是，平均意义上来讲，它可以在多项式时间内实现大数分解，这对RSA加密算法构成了威胁。因此接下来的算法描述我们仅考虑待分解的大数由两个不同的素因子组成这种情况，即N = p ∗ q（RSA加密算法采用的大数就是如此）度的计算。算法步骤3是shor算法的核心，由量子计算机完成。 2.2.2 算法步骤3的概要图 2: 步骤3的逻辑电路其中CU是受控模指元件，QF T −1是量子傅里叶变换的逆变换，但实际上，使用正变换和逆变换的效果是相同的。在下面的实际搭建中，我们采用的是正变换。 2.2.3 使用逻辑门搭建QFT QFT变换从矩阵的角度来说，实际上是一个由单位根构成的酉矩阵 2.2.1 shor算法的主要流程给定大数N，采用如下步骤对N进行分解 QF T = 1√ M  1 1 1 ω 1 ωM−1 1 ωM−1 ··· ··· ... ··· ω(M−1)(M−1)  M×M 1. 随机选择正整数a，1 < a < N ； 2. 计算gcd(a, N ),如果结果gcd(a, N ) = 1,返回第一步； 3. 寻找a模N的阶，即最小的正整数r，使得ar ≡ 1(modN )； 4. 如果找到的r是奇数，或者a 返回第一步； r 5. 计算gcd(a 2 + 1, N )和gcd(a 算结果分别对应p和q，分解完成算法步骤1，2，4，5由经典计算机完成（算法步骤5的正确性只需要用一点点的数论知识便可得到），我们知道，加百利cdot拉梅已经证明了辗 2 − 1, N )，两个计 2 ≡ −1(modN )， r r 转相除法的时间复杂度为O(log(a + b))，因此，经典计算机上进行的运算是一个线性时间复杂 4 2πi (18) M ，矩阵的第i行j列对应的元素其中ω = e 为ωi·j，约定矩阵的行列指标是从0开始的，即从第0行到第M-1行。容易验证这个矩阵确实是酉矩阵。在shor算法用到的QFT矩阵的大小M是2的幂次，我们假设M = 2n，则我们可以知道n个量子比特的系统的本征态|j1j2 ··· jn经过QFT之后状态演化为 (|0 + e2πi0.jn |1)(|0 + e2πi0.jn−1jn |1)··· (|0 + e2πi0.j1···jn) 其中0.jkjk+1 ··· jn =n (19) 2t−k+1 我们来分析上述结论成立的合理性。首先注意到一个性质，若 t=k 2 n 2 jt

设j1j2 ··· jn对应的十进制为x，则|x对应的2n次方维向量表示v,v的第x位是1，其它位是0（约定位数指标是从0开始，与矩阵的行列指标约定一致），这个性质可直接由张量积的运算法则得到。因此QFT作用在|j1j2 ··· jn之后，系统状态变为 ωs·x |s (20) M−1 s=0 1√ M 接下来只需证明(19)式与(20)式等价，对任意一个态|s，设s的二进制表示为m1m2 ··· mn我们比较两个式子的|s态前的系数。显然，(20)式的|s态前的系数为  1 0 0 0 1 0 0 0 1 0 0 0 e 0 0 0 2πi 2k 是受控的CR门，图中的黑点表示CR门的控制比特，Rk所在线路对应的是目标比特。并注意到我们有 H |j = 1√ 2 (|0 + e2πi0.j |1) (23) 回顾一下在量子逻辑门中对CR门性质的介绍，可知上面的逻辑电路确实等价于一个QFT矩阵。 e2πi· (m1m2···mn)(j1j2···jn) 2n (21) 2.2.4 CU门概述 = 由于e2πi 1，我们在计算(m1m2 ··· mn)(j1j2 ··· jn)时只需要在mod2n的意义下进行即可。可知任意一位mk，若mk = 0，则mk对指数大小的贡献为 mk · 2n−k · (jn−k+1 ··· jn) 2n = 0.jn−k+1 ··· jn (22) 若mk = 0，则它对指数大小没有贡献，现在看(19)式，要在(19)式的展开项中得到|s态，如果mk = 1，就在乘积式的第k项中取|1，该项对指数大小的贡献为0.jn−k+1 ··· jn，如果mk = 0，就在乘积式的第k项中取|0，该项对指数大小无贡献。由此可以得到|s的在两式中的系数是相等的。因此(19)与(20)式等价。通过(19)式，我们很容易发现下面的逻辑电路等价于一个QFT矩阵其中Rk = 每个CU门是一个受控的模指电路，图2中的黑点表示控制位，如果控制位是0，那么不改变目标比特（目标比特是图中的Lower Regsiter）。如果控制位是1，那么将目标比特的状态从输入的|s变为|k · s(modN )，k是图2中CU门上的数值，不同的CU门k是不一样的。因此，CU门就类似于经典计算机中的一个乘法元件，它的具体搭建方式也类似于经典的计算机电路，先用量子逻辑门搭建基本的加法器··· ，这里就没有详细论述的必要了。 2.2.5 输入设置与系统状态演化了解了QFT和CU门的功能之后，我们来分析图2中的输入。首先我们选取一个2的方幂Q， Q = 2n，要求N 2 ≤ Q ≤ 2N 2，这个Q的选取方式显然是唯一的（后面会讨论这样选取Q的原因），N是待分解的大数。取图2中的Upper Regsiter是一个n量子比特的输入（且输入状态是|0），则QF T −1是一个2n的酉矩阵，下面的Lower Regsiter输入规模也取为n量子比特（其实只要保证2n > N 就可以了，因为Lower Regsiter的作用是表示modN 的余数），输入状态是|1。接下来我们分析图2的系统演化。初始状态图 3: QFT的逻辑电路 5

Q−1 k=0 1√ Q Q−1 k=0 1√ Q 为|0|1，经过H门之后，系统的状态变为 |k|1 (24) 记f (x) = ax(modN )，则经过一系列的CU门，系统的状态演化为 |k|f (k) (25) (25)式的合理性很容易想清楚。在经过CU门之前，系统状态为(24)式，是一系列本征态|k|1的叠加。当本征态|k|1经过CU门时，写出k相应的二进制表达式，根据CU门的输入输出规则，很容易发现输出的状态为|k|f (k)，再叠加回来，便得到(25)式（也可以认为这样做的合理性在于CU门本质上是一个线性变换的矩阵）。接下来用QFT矩阵作用于Upper Regsiter，根据(20)式可知此时系统状态演化为示sr模Q的余数。我们计算测到这样的s的概率，上式可以写为 P (s, f (k)) = | 1 Q b{sr}Q Q |2 e2πi (29) Q−k−1 r b=0 {sr}Q Q −1)) Q−k−1 上式是对b的离散求和，我们把绝对值内部的项转化为积分，写做 b{sr}Q (Q − k − 1)/r r 0 Q e2πi Q db+O( 1 (e2πi Q (30) 第二项是误差项，由于−r/2 ≤ {sr}Q ≤ r/2，对误差项直接取模进行估计，可知误差项不超过O(1/Q)，现在我们做代换u = rb/Q,我们得到上式可写为 Q· Q−k−1 r u{sr}Q r e2πi du + O(1/Q) (31) r 0 1 r 我们把积分上限放大到1，容易看出产生的误差不超过1/Q，因此上式化为 e2πi s·k Q |s|f (k) (26) 1 r u{sr}Q r e2πi du + O(1/Q) (32) 1 0 Q−1 Q−1 k=0 s=0 1 Q 最后我们对进行测量。假设a模N的阶为r，即r为f (x)的最小正周期，f (x)仅有r种可能的取值，对这r种取值中的任意一种f (k)，0 ≤ k ≤ r − 1我们知道测量得到状态|s|f (k)的概率为 P (s, f (k)) = | 1 Q e2πi s·j Q |2 (27) 不妨设j = br + k，并注意到k不受求和，因此上式可以化为 j≡k(modr) Q−k−1 r b=0 计算该定积分，我们知道当{sr}Q = 0时，该定积分的模长取到最大值1/r，当{sr}Q = ±1/2时，该定积分的模长取到最小值 2 πr ，由于r < N 且Q = N 2，结合N是一个大数，可知误差项可忽略不计。总之，我们得到对于一个满足余数要求的s，测量到态|s|f (k)的概率满足 P (s, f (k)) > 4 π2r2 > 1 3r2 (33) 假设我们测量得到了这样的s，即−r/2 ≤ {sr}Q ≤ r/2，因此存在一个非负整数d满足 P (s, f (k)) = | 1 Q Q |2 e2πi sbr (28) −r 2 ≤ sr − dQ ≤ r 2 容易想到，当 sr Q 越靠近整数时，上面的概率越大，由于s的取值是在0到Q-1，因此可知使得−r/2 ≤ {sr}Q ≤ r/2的s总是存在的，{sr}Q表上式也可以写作 | s Q − d r | ≤ 1 2Q 6 (34) (35)

只能输入本征态的经典计算机没办法做到的（如果我们依次计算ak，这个时间复杂度是O(N )，就成了一个指数时间复杂度的算法了）。这个想法与Deutsch–Jozsa算法很相似。 3 量子计算机的困难与发展方向从shor算法中可以看出，如果我们希望利用shor算法破解RSA加密体系，例如需要分解一个400位的整数，我们需要几千个量子比特，而当下的硬件技术还远远不能达到这一要求。其次，shor算法虽然是多项式时间复杂度的算法，在分解大整数时也需要一定的时间，这对量子比特的相干状态的维持提出了很高的要求。实际上，对于单量子比特系统而言，目前最好的相干时间是10分钟左右。而对于多量子比特系统，能维持的相干时间就更短了。一旦在程序运行过程中量子比特退相干，那么这些依赖于叠加态实现并行计算的算法就失效了。因此，到实际应用shor算法来破解RSA加密体系，还需要一段较长的时间来发展量子计算机的硬件。此外，目前提出的行之有效且明显优于经典算法的量子算法也很少，我们也需要更多的有效的量子算法，才能让量子计算机发挥出它应有的作用。参考文献 [1] 郭国平，陈昭昀，郭光灿著：《量子计算机与编程入门》北京，科学出版社 [2] Peter W.shor:Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer[J]. Siam Review, 1999 [3] D.Deutsch,R.Jozsa:Rapid solutions of problems by quantum computaion,Proc.Royal Society of London A,439,553,1992 注意这个时候s,Q都是已知量，我们证明满足(35)式的且分母小于N的分数至多只有1个，假设存在 d1 r1 都满足要求，则 = d2 r2 1 N 2 < 1 r1r2 ≤ | d1 · r2 − d2 · r1 r1r2 | ≤ 1 Q (36) 这与我们对Q的选取相违。既然上面的讨论表明，如果我们测到了一个满足余数要求的s，我们就可以利用连分数逼近算法唯一地得到 d r 。这里要求gcd(d, r) = 1，否则得到的分母是r的一个因子，并不是我们真正想要的r。因此我们每做一次测量，得到一个s，得到一个c利用连分数逼近算法得到(也有可能得不到)r∗，然后检验它是否是我们要找的r，如果是，那么输出这个r，整个步骤3结束，如果r∗并不是我们要的r，那么重复进行步骤3。我们来计算测到满足要求的s的概率，首先s需要满足余数要求，其次需要保证gcd(d, r) = 1。满足gcd(d, r) = 1的d有ϕ(r)个，其中ϕ(r)是欧拉函数。对每一个这样的d，显然都能找到一个满足(34)式的s，又对于每个s，处于Lower Regsiter的态f (k)有r种本征态，因此我们得到测到满足要求的s的概率 P (|s) > rϕ(r) · 1 3r2 = ϕ(r) 3r (37) 由欧拉函数性质，存在正常数δ，使得对大于3的正整数r有 ϕ(r) loglogr （《数论导引》定理328 （哈代））因此，我们重复测量O(loglogr) < r > δ O(loglogN )次后，有足够高的概率得到正确的r,因此整个步骤3是多项式时间复杂度的算法。 2.2.6 shor算法的评析 shor算法能做到在多项式时间内分解整数，最为关键的是算法步骤3，而算法步骤3最为关键的步骤在于先让n位量子比特的Upper Regsiter通过H门，得到|k，k取遍0到Q-1所有的Q个本征态(参见(24)式)，此时这个叠加态通过CU门，相当于同时计算了ak(modN )，k取遍0到Q-1。这是 7

分享到：

赞收藏

资料库

shor算法详细分析.pdf

相关推荐

课程资源

热门标签

最新资料