在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确保了在每次迭代中都能有效地引导系统向精确解靠拢,并最终实现对目标状态的准确收敛。
图 6. DEGGA与改进的Grover 算法的简单比较。
来源:Distributed Exact Generalized Grover’s Algorithm by Xu Zhou, etc.
DEGGA的另一个显著特点是其性能主要取决于子函数划分策略,而不是数据库的规模大小。这种设计使得DEGGA在处理大规模数据时更加灵活和高效。
图 7. 6 量子比特DEGGA 的量子线路。
来源:Distributed Exact Generalized Grover’s Algorithm by Xu Zhou, etc.
图 8. DEGGA 与现有分布式 Grover 算法的简单比较。
来源:Distributed Exact Generalized Grover’s Algorithm by Xu Zhou, etc.
DEGGA 的开发是分布式量子算法设计的一大进步,其优势有:
灵活性:DEGGA允许计算节点的数量扩展至不高于数据库规模n的任意多个。
多目标搜索能力:DEGGA能够精确解决广义搜索问题,将量子搜索算法的应用范围从单一目标扩展到多目标搜索。
可扩展性:无需辅助量子比特,算法可在多个计算节点上分割问题,高效扩展算法规模同时不会相应地增加资源需求,使得总比特数得以控制在n以内。
减少资源使用:与Grover的改进版相比,DEGGA 将量子门的利用率降低了 90.7% ,量子线路深度也减少了91.3%,这减少了出错率和运行成本。
易于实现:对于许多量子算法而言,实际实施是一个挑战。DEGGA的优势在于它可以利用量子模拟软件实现,并且能够轻松集成到现有的量子计算框架中。
适用于 NISQ 时代: DEGGA 的设计考虑到了当前量子技术的局限性,使其成为在现有量子系统上实施的实用选择。这种与当前技术的相关性增加了它的重要性,因为它可以应用于提高当今正在开发的量子系统的性能。
结语与展望
DEGGA 符合当前NISQ时代量子硬件的能力和局限性的现状。通过在多个量子节点上分配工作量,DEGGA 有效地应对由相干时间和错误率带来的挑战,研究结果展示了DEGGA的实用性和效率,将影响分布式量子计算机以及量子计算网络的发展。
面对量子计算在可扩展性方面的挑战,分布式QPU-CPU混合计算技术正成为解决之道。这种技术通过在量子和经典计算资源之间分配量子算法,实现了超越单一计算资源的计算能力,推动了量子计算向更实用、可扩展和高效的方向发展,为未来实现复杂量子计算奠定了坚实的基础。
启科量子是亚洲首家离子阱量子计算公司,多年来专注于离子阱量子计算机的研发。2023年年初,启科量子推出了国内首台离子阱量子计算工程机“天算1号”。在“天算1号”的基础上,启科量子将着力发展以“离子-光子”纠缠为基础的分布式技术。
目前启科量子已开展分布式离子阱量子计算机的研发,有望早日实现分布式精确广义Grover算法的真机演示。未来,该系列量子计算机可以在经济建设、新兴产业培育、国防和科技发展等诸多重要领域发挥作用,推动信息技术演进和产业升级,并极大地减少经典计算产生的能源消耗,助力达成国家“双碳”战略目标。
