推荐Strilanc · 2023-01
“One of the things that stands out to me about Shor's paper is how meticulous he is.”
称赞 Shor 这篇论文非常严谨,细致分析了量子分解的失败情形
量子计算机上多项式时间的整数分解与离散对数算法
论文指出,若考虑量子力学,数字计算机未必能以多项式因子的开销模拟任何物理计算设备。作者针对整数分解和离散对数这两个被认为在经典计算机上很难、且是多种密码系统基础的问题,给出了假想量子计算机上的高效随机算法,所需步数是输入规模(如待分解整数的位数)的多项式。
HN 评论者在谈量子计算对密码学的影响时引用它,称赞 Shor 的分析极为严谨,并指出原文讨论了需要多次运行及时间复杂度。
候选只有一篇与量子计算能力边界相关的论文,它是目标论文之后的回顾性材料,帮助判断量子算法究竟强在哪里。
讨论量子计算能解决什么、不能解决什么,可以带着它回头衡量 Shor 算法的意义与边界。
读量子计算在黑箱搜索等问题上的上下界,以及为何不能期待量子计算机轻易解决 NP 完全问题。
目标论文:给出量子计算机上整数分解与离散对数的多项式时间算法。
读把分解归约为求周期,量子傅里叶变换如何提取周期,以及离散对数的处理思路;物理模型细节可略读。
“One of the things that stands out to me about Shor's paper is how meticulous he is.”
“Supposedly his proof is valid, predicated on the existence of quantum computers.”
“Shor's original paper discusses the fundamental need for several runs and gives the time complexity.”