2021-2022学年高二物理竞赛课件：相位确定算法的应用

1、相位确定算法的应用相位确定算法可以用来解决一系列的问题: order-finding, factoring.这两个问题在本质上是等价的.应用 :order-finding算法和 factoring算法Provide evidence that quantum computers may be inherently more powerful than classical computer.Justify interest in novel algorithmEfficient algorithms can be used to break the RSA public-key cryptosy

2、stem.快速量子算法的优势对于满足 xN的任意正整数x和N, 二者没有公因子, x modulo N的阶的定义是最小的r，使得下式成立: e.g: if x = 3, N = 5, then r = 4.Order-finding算法We have efficient procedures to implement a operation.We must be able to prepare the eigenstateRequirements to use phase estimation初始态制备It requires to know r . So we circumvent the p

3、roblem , since :order-finding算法的量子线路一般步骤 区分素数和合数，以及将合数分解为素因子的问题，是整个算术中最重要和最有用的一个问题。科学的尊严似乎要求，每一个有助于解决这样一个优雅和著名问题的努力要得到热情支持。 -高斯大数分解：将求阶算法变换成因子分解的快速算法Algorithms: 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

4、 even, return the factor 2.2.Determine whether for integers and if so return the factor a。3.Randomly choose x in the range 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.ProceduresFactoring 15 quantum mechanicallyExampleperiod-findingdiscrete l