科研进展：启科量子发表“分布式精确广义 Grover 算法”论文

【天极网IT新闻频道】在NISQ(含噪声的中等规模量子)时代,分布式量子计算被认为是一种有前途且具有优势的量子计算大规模扩展方案。分布式量子算法作为分布式量子计算的重要组成部分,受到了广泛的关注。

近日,中山大学和启科量子的联培博士后周旭博士、中山大学物理与天文学院的罗乐教授等人,在预印本平台arXiv发表题为“Distributed Exact Generalized Grover's Algorithm”的学术论文。论文提出了一种分布式精确广义 Grover 算法(DEGGA),可实现多目标精确搜索,同时降低了每个计算节点的量子门和量子比特数量需求,加快搜索过程。与其他Grover算法相比,DEGGA 保证了100%的搜索成功率,这对于密码学、科学研究中的复杂数据库搜索等无序大数据搜索场景具有重要意义。

图1. 论文截图

不断改进的Grover量子算法

Grover算法,由Lov Grover于1996年提出,是一种在无序数据搜索方面表现卓越的量子算法。相较于传统经典算法,Grover算法的搜索速度具有明显优势(平方级加速),充分展示了量子计算在运行机制和计算能力上与经典计算的显著差异。

图2. Grover算法的可视化示意图。

来源:Quantum Computation and Quantum Information by Nielsen, etc.

图 3. Grover算法量子线路图。

来源:Distributed Exact Generalized Grover’s Algorithm by Xu Zhou, etc.

*初的Grover算法存在搜索目标的概率问题,即搜索概率接近*佳,但不能保证为100%。为了解决这个问题,2001年,清华大学的龙桂鲁教授改进了该算法,通过改进Grover算子以及调整迭代次数,实现了100%的搜索成功率。

图 4. 改进Grover算法的可视化示意图。

来源:Distributed Exact Generalized Grover’s Algorithm by Xu Zhou, etc.

图 5. 改进的Grover算法量子线路图。

来源:Distributed Exact Generalized Grover’s Algorithm by Xu Zhou, etc.

随着分布式量子计算的日益重视,科学家们对Grover算法进行了分布式化改造。2023年,周旭、邱道文教授(中山大学计算机学院)、罗乐教授等人在《物理前沿》(Frontiers of Physics)上发表了题为“Distributed exact Grover’s algorithm”的论文(期刊封面),通过该算法巧妙地解决了单目标串精确搜索的问题。

分布式精确广义Grover算法

DEGGA是分布式精确Grover算法的广义版本,允许寻找多个目标状态。该算法将广义搜索问题拆分成多个搜索子问题,由不同的量子计算节点并行处理,每个节点配备独立量子线路,专注于特定子串的搜索,再通过节点间的操作,*终实现多目标精确搜索。

与传统的量子搜索算法相比,DEGGA在设计上无需使用辅助量子比特,这一点显著简化了算法的实现。此外,DEGGA还大幅减少了量子门的使用。以文中的具体实现例子(搜索000000和111111)来说,相比于改进的Grover算法,DEGGA的量子门的利用率降低了90.7%,量子线路深度也减少了91.3%。通过应用量子振幅放大等关键技术,DEGGA确保了在每次迭代中都能有效地引导系统向精确解靠拢,并*终实现对目标状态的准确收敛。