量子信息学引论第讲.ppt

连分数展开 把求阶问题还原为相位估计, 是通过从相位估计算法的结果 来得到希望的答案 r。 我们只知 近似到 2L+1位, 但我们事先知道 为一个有理数 ( 两个有界整数的比值)。 这样，如果我们能够计算最近于此 的分数，就可得到r。 * 第二十页，共七十一页，2022年，8月28日 定理 5.1 设 s / r 是一个有理数, 使得 则 s / r 是 的连分数的一个渐近值. * 第二十一页，共七十一页，2022年，8月28日 注意，j是对 s/r的近似，精确到2L+1位。 又因为 , 所以： 定理5.1的应用 * 结论： 给定 j, 连分数算法可有效地产生出没有公因子的 s\ 和 r\， 使得s/r = s\/r\, r\ 是阶的候选对象，可以通过计算xr\ mod N, 看是否为1，如果是，r是x 模N的阶 。我们的任务就完成了。 第二十二页，共七十一页，2022年，8月28日 进行相位估计的两个条件 (1) 能够用有效的步骤来实施一个 操作, 其中j为任意常数. (2) 能够有效地制备本征态 ，或本征态的叠加态。而 的本征值并不是简单的值。 * 第二十三页，共七十一页，2022年，8月28日 实现第一个条件 通过模幂(modular exponentiation)可满足相位估计的第一个条件. 采用模幂,则可用 个门来实现相估位计中需要的 * 第二十四页，共七十一页，2022年，8月28日 Box 5.2 模幂 (modular exponentiation) * 用可逆运算得到xz(mod N),首先计算x2(mod N)，x4(mod N),…, 直到x2 j(mod N), 即可得到： 第二十五页，共七十一页，2022年，8月28日 实现第二个条件 需要一些技巧：制备 要求我们知道 r ，而我们事先并不知道r， 所以直接制备 不可能。 幸运的是, 如果我们注意到, 则我们可以绕过制备 的问题。 * 第二十六页，共七十一页，2022年，8月28日 推导: (5.44)式 * 第二十七页，共七十一页，2022年，8月28日 推导过程 由于 第二十八页，共七十一页，2022年，8月28日 相位估计步骤的第一阶段 注意: 右边省略了归一化因子 * 第二十九页，共七十一页，2022年，8月28日 图5.4 求阶算法的量子线路 第二个寄存器已被证明可以被初始化到|1态完成求解运算。 不过, 若利用练习5.14, 它也可被初始化到|0态. 这个线路也可用来进行因数分解。 * 第三十页，共七十一页，2022年，8月28日 量子Fourier变换的乘积表示 * 第三十一页，共七十一页，2022年，8月28日 图5.1 量子Fourier变换的有效线路 此线路可从量子Fourier变换的乘积表示式中推出。 图中没示出线路末尾的交换门( swam gate), 用交换门把量子位的次序反过来。 图中也没有显示出输出中的归一化因子 。 * 第三十二页，共七十一页，2022年，8月28日 其中x与N互质； （2） 算法: 量子求阶 输入：（1）一个黑箱Ux,N能执行变换： （3）L个量子位初始化到|1, 位初始化到|0 输出：满足xr=1(modN)的最小整数r 0。 运行时间：O(L3)个操作。成功率：O(1) * 第三十三页，共七十一页，2022年，8月28日 算法: 量子求阶(步骤) * 第三十四页，共七十一页，2022年，8月28日 5.3.2 应用: 因数分解 (factoring) 给定一个正合数N，它是由哪些素数相乘而得？ 最好的经典算法：O(exp(N)) 因数分解有什么用？ 破解密码 * 参考文献： A. Ekert and J. Jozsa, Rev. Mod. Phys. 68, 733 (1996). 第三十五页，共七十一页，2022年，8月28日 合数和素数 素数(又称质数)指在一个大于1的自然数中，除了1和此整数自身外，没法被其他自然数整除的数 合数指在一个大于1的自然数中，除了1和此整数自身外，还有其他自然数整除的数 第三十六页，共七十一页，2022年，8月28日 * MIPS是Million Instructions Per Second的缩写，每秒处理的百万级的机器语言指令数。这是衡量CPU速度的一个指标。像是一个Intel 80386 电脑可以每