量子保密通信好与坏?别把“李鬼”当“李逵”

  • 作者能再说说如果证明P=NP对相关领域的影响么?他和量子计算淘汰现有密码的方式有什么不同?还有,文章中说我们现在只是找到了对特定问题有特效的量子算法,那我们有可能找到普适性的对所有问题都比现有计算机更强的量子算法么?

回复1

  • 我对计算机科学了解不多,尝试着回答一下你的问题。一般都猜想NP大于P,但这一点一直没有证明。如果最后证明了NP = P,那么这将对许多领域造成核弹般的冲击。例如,量子计算就失去意义了,因为量子计算机能够处理的问题在NP之内,P = NP就意味着量子计算机与经典计算机能处理的问题集合是完全相同的。此外,公钥密码体制也会崩溃,因为你不可能提出一个能在多项式时间加密却不能在多项式时间内破解的算法了。至于后面那个问题:找到普适性的对所有问题都比现有计算机更强的量子算法,这显然不可能,因为有些问题已经十分快速了,例如加法,还有什么加速的余地?
返回文章

站务

最近更新的专栏

全部专栏