Hardware-Aware Realization of Deterministic Quantum-Walk Search on Complete Bipartite Graphs
本文报告了首次利用数字门控处理器在完全二部图上实现确定性离散时间量子行走搜索的实验结果,该研究在小规模实例中实现了高成功概率,并展示了通往应用级量子搜索的 扩展路径。
原始论文采用 CC BY 4.0 许可(http://creativecommons.org/licenses/by/4.0/)。 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性,请参阅原始论文。 阅读完整免责声明
在现代计算的广袤版图中,一场静默的革命正在量子力学领域悄然发生,在这里,微观世界的规则挑战着我们的日常直觉。这场革命的核心在于“量子行走”(quantum walk)的概念,这一过程是人类所能构想出的最强大的搜索算法之一的引擎。不同于在街道上行走的人必须在每个交叉路口选择单一路径,量子行走者可以同时探索每一条可能的路径,这种特性被称为“叠加”(superposition)。这种能力使量子计算机能够比传统机器更快地筛选海量信息,为特定类型的问题提供潜在的二次加速。然而,为了让这种速度在现实世界中发挥作用,搜索必须是确定性的,这意味着它必须以近乎确定的方式找到正确答案,而不仅仅是具有高概率。虽然科学家们早已了解如何在简单的全连接网络上实现这些搜索,但挑战在于如何将其适配到更复杂、更具结构性的系统中,以更好地反映现实,例如那些仅在两个不同项目组之间存在连接的网络。
一支研究团队现在通过在一种被称为“完全二部图”(complete bipartite graph)的特定结构化网络上成功演示这种确定性搜索,迈出了重要的一步。想象一个分为两组的系统,例如一份求职者名单和一份可用职位名单,其中每位求职者都与每个职位相连,但求职者之间互不相连。这种结构模拟了许多现实场景,从生物相互作用到推荐系统。研究人员使用了一台数字量子处理器——一种通过使用精确的逻辑门序列来操纵称为“量子比特”(qubits)的单个信息单元来运行的机器——在该网络上执行搜索。他们的目标是在图中找到一个特定的、被标记的项目,例如某个特定的求职者或职位。通过精心设计搜索过程以适应这种两组网络独特的形状,他们实现了一种能在特定时刻将寻找目标的概率全部集中在正确答案上的搜索。
该团队在名为“祖冲之 3.1”的超导量子处理器上执行了实验,这是一种使用量子比特网格排列的设备。他们首先采用一种将整个网络直接编码进机器内存的方法来解决问题,他们称之为“全空间编码”(full-space encoding)。对于一个包含四个项目的微型网络,他们的搜索成功率达到了 97.6%。当他们将网络规模扩大到八个项目时,成功率仍保持在 70.8% 的稳健水平。在处理八个项目的网络时,研究人员观察到找到目标的概率急剧上升,并超过了经典计算机在相同尝试次数下所能达到的水平。这一结果提供了具体的证据,证明量子行走可以有效地在二部图复杂的干涉模式中导航,从而高精度地定位目标。
意识到全编码方法在处理更大规模网络时会变得过于深层且易出错,研究人员还开发了一种更高效的方法。他们意识到,搜索的核心动力学可以在一个更小、更简化的空间内得以保留,而无需显式映射每一个连接。通过使用这种简化编码,他们能够在多达 16 个项目的网络上模拟搜索,实现了 66% 的成功率。值得注意的是,他们还将这种简化方法扩展到测试代表多达 256 个项目的网络的底层物理机制。即使在这种规模下,搜索仍保持了接近 50% 的成功概率,这表明只要去除了全编码中不必要的复杂性,该算法的核心机制即使在问题规模增长时也能保持稳定。
通过详细分析,团队发现限制此类搜索扩展到大规模现实规模的主要障碍并非网络中项目的数量,而是每次机器执行逻辑操作时产生的微小误差的累积。他们的计算表明,对于规模约为十万项的国家级职位匹配计划,量子门的错误率需要达到低于千万分之一的近乎完美的水平。虽然目前的硬件尚无法在如此大规模的问题上达到这种精度水平,但该实验成功绘制了从算法到物理机器的精确路径。通过展示搜索在小规模下的有效性,并量化硬件需要达到何种程度的改进,研究人员为未来的发展建立了一条清晰的路线图。这项工作证实了在结构化图上的确定性量子搜索不仅是一个理论上的可能性,更是一个随着量子处理器不断进步而可以实现的切实的工程挑战。
您所在领域的论文太多了?
获取与您研究关键词匹配的最新论文每日摘要——附技术摘要,使用您的语言。