《2021-2022学年高二物理竞赛课件：相位确定算法的应用.pptx》由会员分享，可在线阅读，更多相关《2021-2022学年高二物理竞赛课件：相位确定算法的应用.pptx（17页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、相位确定算法的应用相位确定算法的应用相位确定算法可以用来解决一系列的问题:order-finding,factoring.factoring.factoring.factoring.这两个问题在本质上是等价的.应用应用:order-finding:order-finding算法和算法和 factoring factoring算法算法(1)Provide evidence that quantum computers may be inherently more powerful than classical computer.(2)Justify interest in novel algor
2、ithm(3)Efficient algorithms can be used to break the RSA public-key cryptosystem.快速量子算法的优势快速量子算法的优势对于满足 xN的任意正整数x和N,二者没有公因子,x modulo N的阶的定义是最小的r，使得下式成立:e.g:if x=3,N=5,then r=4.Order-findingOrder-finding算法算法(1)We have efficient procedures to implement a operation.(2)We must be able to prepare the eig
3、enstateRequirements to use phase estimationRequirements to use phase estimation初始态制备初始态制备It requires to know r.So we circumvent the problem,since:order-findingorder-finding算法的量子线路算法的量子线路一般步骤一般步骤 区分素数和合数，以及将合数分解为素因子的问题，是整个算术中最重要和最有用的一个问题。科学的尊严似乎要求，每一个有助于解决这样一个优雅和著名问题的努力要得到热情支持。-高斯大数分解：大数分解：将求阶算法变换成因子
4、分解的快速算法AlgorithmsAlgorithms:order-finding order-finding 问题问题Input:A composite number N.Output:A non-trivial factor of N.Runtime:operations.Succeeds with probability O(1).1.IF N is even,return the factor 2.2.Determine whether for integers and if so return the factor a。3.Randomly choose x in the range
5、 1 to N-1.if then return the factor gcd(x,N)。4.Use the order-finding subroutine to find the order r of x modulo N.5.If r is even,and then compute and and test if one of these is a non-trivial factor,returning that factor if so.ProceduresProceduresFactoring 15 quantum mechanicallyExampleExampleperiod-findingdiscrete logarithmsthe hidden subgroup problem其他应用：其他应用：算法算法:量子相位估计量子相位估计Period-findingPeriod-finding一般步骤一般步骤