量子计算
发布时间：2013-11-22 13:58:54 点击浏览：次
量子计算是量子物理学向我们展示的又一种强大的能力。量子计算的概念最先由Richard Feynman提出，源自于对真实物理系统的模拟。模拟多粒子系统的行为时，描述系统的希尔伯特空间（Hilbert space）的维数会随着粒子的数目成指数增长。而当需要模拟的粒子数目很多时，一个足够精确的模拟所需的运算时间则变得相当可观，甚至是不切实际的天文数字。例如，考虑模拟一个由40 个自旋为1/2 的粒子构成的量子系统，经典计算机至少需要内存为1000G比特，而计算时间演化则需要求一个维矩阵的指数，以目前的经典计算机水平将无法胜任此类任务。Feynman当时认为如果用量子系统所构成的计算机来模拟量子现象则运算时间可大幅度减少，从而量子计算机的概念诞生。
Peter Shor提出的大数因式分解算法（Shor算法）第一次实际地揭示出量子计算的威力。RSA公钥体系的安全性建立在两个大质数的积易于得到而难于分解之上。利用经典THz计算机分解300位的10进制数，需计算1024步，耗时将达到150000年。因此对于经典计算机，RSA是安全的。然而，利用Shor算法THz计算机分解同样的整数则只需计算1010步，耗时仅仅1秒！RSA公钥体系的安全性将变得极其脆弱！
此外，还有1997年由Grover提出的搜索算法。对于在大小为N的数据库中搜索一个指定数据的运算，经典计算机需要N步，而按照Grover算法则只需要 步。比如当数据库中有256个数的情况下，经典计算机需要100年才能完成这一搜索任务，而运行Grover算法的量子计算机只需要4分钟！这意味着安全性依赖于密钥难以被穷举搜索的私钥算法，其安全性也大大下降了！
一旦量子计算机进入实用化阶段，它的强大威力就会直接威胁到经典密码体系的安全性，尤其是公钥密码体系。目前来看，保证通信安全性的唯一解决方案是发展量子通信技术。
热点标签:
