PRL| 北京计算科学研究中心薛鹏团队实现确定性量子搜寻算法

撰稿|由课题组供稿

近日，北京计算科学研究中心薛鹏教授团队及合作者在连续时间量子行走的研究中取得重要进展。他们通过交替使用连续时间量子行走与oracle查询，提出基于星图上量子行走的确定性的搜寻算法，并实验演示了对于115个数据的无序库的搜寻。研究成果以“Deterministic Search on Star Graph via Quantum Walks”为题，于2022年2月1日发表于 Physical Review Letters 128, 050501 (2022).

Grover搜寻算法是量子计算的一个标志性应用，在对未排序的数据库进行搜寻时，与经典搜寻算法相比具有平方根加速的优势。Grover搜寻算法证明在包含N个元素的数据库中去找到一个标记的元素，需要oracle查询的次数最优为大约。 然而Grover算法并不是确定性的，存在1/N的数量级的失败几率。

量子行走作为经典随机行走在量子世界的对应，其平方式增长的扩散速度体现出量子资源的重要优势，也可以实现搜寻算法，相比较于经典算法具有跟Grover算法一致的加速效果。

北京计算科学研究中心薛鹏教授团队及合作者在基于前期对量子行走研究的积累下，通过交替使用连续时间量子行走与oracle查询，设计一种基于星图上量子行走的搜寻算法。他们将Grover搜寻算法中的Grover算子替换为连续时间的量子行走，此种新型的量搜寻算法与Grover算法相比有着相同的效率，而且是确定性的，即成功几率为1，除此之外还具有其他算法不具备的抗噪声能力。

该团队利用单光子和线性光学系统实验实现了任意的幺正演化的方案，实验演示了对于7至115个数据的无序库的搜寻，证明了该算法的可扩展性。这一工作首次在实验中实现了这种全新的确定性的量子搜寻算法为量子行走在量子算法和量子信息处理中的应用提供了新的证据。

图1：实验装置。

图2:  实验结果。

该工作的理论合作者为西澳大学的Jingbo Wang教授。论文第一作者为薛鹏教授指导的博士生曲登科，Samuel Marsh为共同第一作者。上述研究得到了国家杰出青年科学基金的支持。

https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.128.050501