提个没什么人知道的, 也不算是发现:Shor 算法. 现在说到量子计算的应用, 必然提及破解 RSA 公钥加密系统, 原因自是 Shor 算法能够在多项式时间进行质因数分解. 不过同时期还有个不太 lucky 的人, Kitaev, 如果当年他选对了问题, 那么可能现在大家耳熟能详的就是 Kitaev 算法了.(故事的来源是王正汉老师某次 talk 的录音[1].)在 Richard Feynman(1982) 提出了量子计算机的概念, 以及 David Deutsch 定义了量子图灵机(1985, 1989) 之后. 大家一般相信量子计算相对于经典计算, 计算能力有所增加, 但是基本上都不相信这东西能解决 NP-Complete 问题(事到如今 BQP 类和 NP-Compete 类的关系还是 open 的). 于是想给这东西提供论据的话, 最直接的想法是提出一个被认为属于 NP-Incomplete 类的问题的量子算法. 公认的选择不多, 只有质因数分解问题(Factoring) 和图同构问题(Graph Isomorphism).(图为 Peter Shor, 来自 Wikipedia)众所周知的是, 当时Peter Shor 选择了质因数分解问题.于是, 他在 1994 年提出了一套基于量子 Fourier 变换的质因数分解算法[2], 拿到了 1999 年的 Gödel
...
继续阅读
(35)