科学家提出量子共振搜索算法

　　科学家提出量子共振搜索算法。 量子计算机虽然比经典计算机强大，但是迄今为止人们只找到了少数比经典算法更优越的量子算法，比如Shor算法和Grover算法。好量子算法少的原因之一是量子计算机的工作原理和人的思维直觉相差太大。Farhi和他的合作者自1998年开始提出了通过构建哈密顿量，利用量子效应或过程来设计量子算法的新思路。这个思路的好处可以更好地利用物理学家在多年研究中形成的对量子物理的直觉。但是迄今为止，被充分讨论和利用的量子过程只有量子绝热演化，即大家熟知的量子绝热算法。

　　 最近，麻省理工教授和李政道研究所所长维尔切克（Wilczek），加州大学圣地亚哥分校的研究生扈鸿业，和北京大学教授吴飙合作，首次通过构建哈密顿量将常见的量子共振应用于量子算法，提出了量子共振搜索算法。这种算法和Grover搜索算法一样快。由于Grover搜索算法已经被严格证明是理论上最快的，这说明当应用于其他问题时，量子共振有潜力发现最快的算法。

　　 很多问题有多个解，估算到底有多少个解（approximate counting）是计算机科学中最基本的问题之一。基于Grover算法和量子傅里叶变换，人们已经提出了多种量子近似计数(quantum approximate counting)算法。这些算法有一个共同点，它们只能估算而且估算精度越高计算时间越长。

　　 维尔切克教授他们在量子共振搜索算法中进一步引入了跟踪量子振动的辅助量子比特。利用辅助跟踪量子比特，他们设计了两种新的量子计数(quantum counting)方案。第一种方案叫非共振排除法（predictive dissonance），利用这种算法可以精确确定解的个数，而不是估算。第二种方案则是通过增加辅助量子比特的数量，希望通过监测辅助量子比特的振动来确定解的个数。辅助量子比特个数越多和监测时间越长，第二种方法的精度就越高。这两种算法的时间复杂度都和以前的量子近似计数算法一致。（来源：中国物理快报）

　　 相关论文信息：DOI: 10.1088/0256-307X/37/5/050304

　　 特别声明：本文转载仅仅是出于传播信息的需要，并不意味着代表本网站观点或证实其内容的真实性；如其他媒体、网站或个人从本网站转载使用，须保留本网站注明的“来源”，并自负版权等法律责任；作者如果不希望被转载或者联系转载稿费等事宜，请与我们接洽。
作者：吴飙等 来源：《中国物理快报》