基于量子力学原理的搜索算法是否远远优于经典方法?

世界并不缺乏复杂的网络,从生物学上的蜂窝网络到技术上错综复杂的网络。这些网络也构成了几乎所有科学领域各种应用的基础,要分析和操作这些网络,需要特定的“搜索”算法。但是,传统的搜索算法速度慢,在处理大型网络时需要很长的计算时间。现在,基于量子力学原理的搜索算法被发现远远优于经典方法。一个这样的例子是“量子行走”算法,它可以用来在给定的N站点图上找到特定点或“顶点”。

量子行走方法不是简单地穿过相邻的顶点,而是采用基于量子力学理论的概率估计,这大大减少了寻找目标所需的步骤。为了实现这一点,在从一个点移动到另一个点之前,需要重复执行名为“oracle call”的操作,以调整量子系统表示中的概率值。一个主要问题是理解Oracle调用的最佳计算时间和网络结构之间的关系,因为对于标准形状和物体,这种关系是很好理解的,但对于复杂的网络,这种关系仍然不清楚。

在发表在《物理评论A》期刊上的一项新研究中,东京科学大学的一组科学家在日井哲郎教授的带领下,更深入地研究了这些网络的错综复杂之处,努力开发出更高效的量子算法。许多现实世界的系统,如万维网和社会/生物网络,都表现出复杂的结构。要充分发掘这些网络系统的潜力,开发一种高效的搜索算法至关重要。首先,科学家们研究了网络的“分形特性”(图形似乎无限复制其整体形状的几何特性)。

研究人员将重点放在一些基本的分形晶格(具有分形网络的结构)上,如“Sierpinski垫片”、“Sierpinski四面体”和“Sierpinski地毯”,试图找出量子行走搜索中顶点数(网络节点)和最佳计算时间之间的关系。为此,研究人员对100多万个顶点进行了数值模拟,并检查结果是否与之前的研究一致,后者提出了一个数学定律或“比例定律”来解释这种关系。研究人员发现,一些分形晶格的标度律,随其光谱维数的不同而不同,这证实了之前对其他晶格的猜测。

令人惊讶的是,他们甚至发现,另一种类型分形格子的标度律取决于其内在特征的组合,这再次表明之前关于最优调用次数的猜测可能是准确的。在分形格子上进行量子空间搜索可能确实是一个事实,它出人意料地受制于分形几何学特征量的组合。为什么调用次数的标度律是由这样的组合给出的,这仍是一个悬而未决的问题。有了这样的理解,研究小组甚至提出了一个新的比例假设。

这个假设与之前提出的略有不同,以便更深入地了解网络的不同分形几何。研究小组希望,有了这个发现,量子搜索将变得更容易进行实验分析,特别是在光学晶格等物理系统上进行量子行走的实验。量子算法在分形格子上的广泛适用性,凸显了这一研究的重要性。由于其令人振奋的发现,研究人员希望其研究能进一步推动复杂网络、数学和量子力学在分形几何方面的跨学科研究。