2010年6月7日星期一
量子计算机解决不了NP问题 zz
NP是指非确定性图灵机（nondeterministic polynomial），“非确定性图灵机”在多项式时间内计算的问题，它就被称为NP 问题，比如旅行商问题便是一个经典的NP问题。从理论上说，量子计算机计算NP问题肯定比电子计算机（即古典计算机）快得多，但它真的能在多项式 时间内解决NP问题吗？2007年，D-Wave公司声称制造出了有16个qubit的绝热量子计算机，通过让计算机的温度维持在绝对零度左右，减少对量 子效应的干涉，使量子计算机能正常工作。
根据即将发表在《美国国家科学院学报》上的一篇研究论文（论文尚未上线），哥伦比亚大学 和NEC实验室的研究人员调 查了绝热量子计算机的解决问题分能力，发现这种计算机解决不了NP问题。研究人员的结论是，对绝热量子计算机而言，NP问题仍然是难以攀登的高 峰。
根据即将发表在《美国国家科学院学报》上的一篇研究论文（论文尚未上线），哥伦比亚大学 和NEC实验室的研究人员调 查了绝热量子计算机的解决问题分能力，发现这种计算机解决不了NP问题。研究人员的结论是，对绝热量子计算机而言，NP问题仍然是难以攀登的高 峰。
标签： NP Hard, Quantum Computer
// 发贴者：放牛娃的春天 @ 六月 07, 2010 
订阅 博文 [Atom]