量子搜索黑科技：Grover算法

在我们的日常生活中，搜索是一项非常常见而且重要的任务。无论是查找最短的驾车路线、寻找特定书籍的内容，还是在互联网上查找信息，我们都需要通过搜索来找到我们想要的东西。

用经典计算机的语言来说，搜索问题可以被总结成一个数学问题：如何在一个集合中的众多数据中，找到满足条件的那一个？

撰文 | 张文昊

自然，我们使用的搜索算法也是基于经典逻辑的，例如线性搜索或二分搜索——但是这些方法要么效率较低，要么对数据的结构有一定的要求。举个具体的例子来说，就好比我们现在有许多外形相同、标有编号的小球，需要在这堆小球中找到上面写有“ ”的那一个。如果这些小球已经整整齐齐地按照数字大小排列好了，那我们自然可以使用二分法来快速定位我们要找的小球；但是如果所有的小球都乱七八糟地堆在一起，那我们似乎别无他法，只能挨个抓起来检查，期待好运气尽快把我们想要的那一个小球带到眼前。

上述情境便是无结构化搜索（Unstructured Search）的一个例子。在这一问题中，待搜索的数据集是混乱的、没有额外限制的。抽象地说，我们可以把待搜索的数据集合看作一堆二进制字符串，需要在其中找到一个满足要求的字符串——就好比我们有一大堆形状各异的钥匙，需要在其中找到能打开门锁的那一把。这一问题的数学表述是：

除了这一理论上的困难之外，Grover 算法的实际应用还面临着更严重的阻碍。在真正的量子计算机上，Grover 算法或者其他量子算法的实现仍然受到当前量子硬件发展水平的掣肘。即使对于目前最先进的量子计算机来说，其可靠性、稳定性和能够处理的量子比特数目水平也远远未达到能大幅超越经典计算机的表现[4]。近年来，量子科学家们主要的关注点还是在如何将规模和稳定性有限的量子计算机与经典优化算法相结合，从而高效地解决一些实际问题。可以说，我们目前在量子计算机领域的发展阶段还处在 NISQ 时代——即中等规模量子比特数目、且由于有噪声，无法实现可靠量子计算的时代（Noisy Intermediate-Scale Quantum Era），距离实现容错量子计算（Fault-Tolerant Quantum Computing）的量子设备问世还有很长的路要走。

不过，尽管在近期稳定实现的机会渺茫，Grover 算法仍然是量子计算领域的一个重要里程碑。它展示了量子计算的巨大潜力，并为未来的量子算法研究提供了宝贵的经验和启示。随着量子软硬件技术的不断发展和成熟，我们可以期待看到 Grover 算法及相关的思路发展出更多的应用，并且在今后的容错量子计算时代，真正得以在量子计算机上稳定实现，为未来的高速计算带来无限可能。

参考文献

[1] Grover, L. K. (1996). A Fast Quantum Mechanical Algorithm for Database Search. In Proceedings, 28th Annual ACM Symposium on the Theory of Computing (STOC).

[2] Nielsen, Michael A., and Isaac L. Chuang. Quantum Computing and Quantum Information. Cambridge University Press, 2000.

[3] Watrous, J. Lecture Notes on Quantum Computing and Quantum Information. https://johnwatrous.com/wp-content/uploads/2023/08/QC-notes.pdf

[4] Mandviwalla A, Ohshiro K, Ji B. Implementing Grover's algorithm on the IBM quantum computers[C]//2018 IEEE international conference on big data (big data). IEEE, 2018: 2531-2537.

[5] Yuan, Xiao. Lecture Notes on Quantum Information.

[6] Lin L. Lecture notes on quantum algorithms for scientific computation[J]. arXiv preprint arXiv:2201.08309, 2022.

本文经授权转载自微信公众号“北京大学前沿计算研究中心”。

特 别 提 示

1. 进入『返朴』微信公众号底部菜单“精品专栏“，可查阅不同主题系列科普文章。

2. 『返朴』提供按月检索文章功能。关注公众号，回复四位数组成的年份+月份，如“1903”，可获取2019年3月的文章索引，以此类推。