本期“量子信息”专栏评述

本期『量子信息』专栏主持人 吴热冰

评“从黑盒子到因果律：寻找量子物理的信息原理”魏朝晖

量子力学在现代物理学的宏伟大厦中处于核心地位，但是如何更深入地理解量子力学在一百多年来一直是学术界的重大课题，人们在这方面的追求从未停止。为了彻底理解一个物理理论，人们不仅需要了解其精确的数学形式，更要建立清晰的物理图像和物理直觉，也就是人们需要揭示这些数学背后基本的物理原理。做到这一点的鲜明体现就是能够从一系列最基本的物理原理出发，通过数学推理准确地重构该物理理论，使之与其他理论完全区分开来。如何针对量子力学做到这一点，是学术界长期以来的重大课题，涌现了一系列有影响力的学术工作。这些工作通过从量子力学提炼出不同的物理或者信息学原理，为人们理解量子力学提供了多角度的洞见，如信息因果原理、宏观定域原理和定域正交原理都是其中的代表。该文就是对几十年来学术界在此领域研究成果的一个全面、深刻而难得的总结。

值得强调的是，近年量子计算的崛起为讨论此课题提供了更多的素材和全新的视角。如人们已经认识到如果量子力学的结构发生微小调整，量子计算复杂性的许多分支将产生重大变化。这种联系为人们理解量子力学的本质提供了新的思路。可以说，这篇论文介绍的学术成果不但有助于人们理解量子力学这一深刻的物理领域，也对我们研究和理解量子计算巨大威力的根本来源提供新的思想。



评“精确Grover 量子搜索算法概述”王晓霆

Grover 搜索算法与Shor 因数分解算法是量子计算理论中最为重要的两个算法。同Shor 算法相比，Grover 算法虽然只是具备了平方加速(在特殊的问题假设下也可实现多项式加速)，但它是许多其他量子算法的基础，且有着更加广泛的应用，如对所有NP 问题的求解加速。此外，Grover 搜索算法的查询复杂度下界可被严格证明，因而在量子计算复杂度理论中具有重要地位。然而，标准的Grover 量子算法在处理搜索问题时通常不能完全保证得到目标项，而很多应用则需要算法的结果是确定而非概率的。为此，精确的Grover 量子搜索算法应运而生，其可以精确地求解搜索问题且保持平方加速。

该文对精确Grover 量子搜索算法进行了回顾，系统地梳理了目前已有的3 种精确量子算法：大步小步、共轭旋转和三维旋转，对它们的工作原理及相应的查询复杂度进行了总结。此外，还讨论了在目标元素占比未知和已知两种情况下，精确量子搜索算法的查询下界。该综述对未来Grover 算法及相关研究提供了有益的参考。