秀尔算法
维基百科,自由的 encyclopedia
秀尔算法(英语:Shor's algorithm)是一个于1994年发现的,以数学家彼得·秀尔命名,针对整数分解题目的的量子算法(在量子电脑上面运作的算法)。不正式地说,它解决的题目是:给定一个整数 ,找出它的质因数。在一个量子电脑上面,要分解整数,秀尔算法的运作需要多项式时间(时间是 的某个多项式这么长, 在这里的意义是输入的文件长度)。准确来说,该算法花费 的时间,展示出质因数分解问题可以使用量子电脑以多项式时间解出,因此在复杂度类BQP里面。这比传统上已知的最快的因数分解算法普通数域筛选法所花费的次指数时间——大约 还要快了一个指数。
秀尔算法非常重要,它意味着:假如有可用的量子电脑,我们可以破解基于公开密钥加密的算法(比如RSA加密算法)。RSA算法的基础在于假设了我们不能有效率的分解一个已知的整数。就目前所知,这假设对传统(即非量子)的电脑为真;没有已知的传统算法可以在多项式时间内解决这个问题。但秀尔算法展示了因数分解问题在量子电脑上可以很有效率的解决,所以一个足够大的量子电脑可以破解RSA。这对于建立量子电脑和研究新的量子电脑算法是一个强大的动力。
2001年,IBM的一个小组展示了秀尔算法的实例,使用NMR实验的量子电脑及7个量子比特,将15分解成3×5。[1]不过,对于IBM的实验是否是量子计算的真实展示,有一些疑虑出现,因为没有发现纠缠现象。[2]IBM的实验之后,也有其他的团队以光学量子比特实验秀尔算法,并强调可观察到其纠缠现象。[3][4]