博文

研究快讯 | 量⼦共振搜索

已有 690 次阅读 2020-6-18 07:27 |系统分类:论文交流

原文已发表在CPL Express Letters栏目

Received 24 April 2020;

online 27 April 2020

EXPRESS LETTER

Resonant Quantum Search with Monitor Qubits

Frank Wilczek, Hong-Ye Hu(扈鸿业), Biao Wu(吴飙)

Chin. Phys. Lett. 2020, 37 (5): 050304

文章亮点

⾸次将量⼦共振应⽤于量⼦算法，实现了和Grover算法等效的搜索算法；在辅助量⼦⽐特的帮助下还能实现⾼效的量⼦计数 (quantum counting)。

Wilczek教授应邀为这项工作作了视频讲解：

http://as.iphy.ac.cn/video_detail.php?id=27322

量⼦共振搜索

研究背景

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

内容简介

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

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

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