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

2024-05-31 09:20:03     来源:

在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算法的真机演示。未来,该系列量子计算机可以在经济建设、新兴产业培育、国防和科技发展等诸多重要领域发挥作用,推动信息技术演进和产业升级,并极大地减少经典计算产生的能源消耗,助力达成国家“双碳”战略目标。

 

标签:

猜你喜欢

除了华为、比亚迪,这些科技国牌也是全球冠军!
同程旅行与鲸鸿动能达成战略合作,共筑智慧旅游新生态
鲸鸿动能与泰国旅游局合作,共促中泰旅游业繁荣
东阳光&华为云,全面合作签约!
华欣国际与鲸鸿动能签约,共同开拓国际教育新市场
助力汽车促消费,懂车帝等头部平台成为“加速器”
贴吧神机再登神坛!宏碁暗影骑士·擎6正式开售!
蓝光存储助推新质生产力 新国都智盾加入深圳市信创联盟
鲸鸿动能:架起成都与马来西亚文化旅游交流的桥梁
老字号焕“新”,端点科技助力卫岗乳业全渠道领“鲜”
工业元宇宙时代下的CAE技术革新 让梦想之车触手可及
西南地区首座百万千瓦级抽水蓄能电站全面投产
鲸鸿动能携手天际通精彩亮相2024 ITB China,激发更多合作火花
淘宝“动刀”年中大促,李佳琦直播间的缓冲期“真香”
2024年工业企业数字化转型(工业互联网) 提升培训班第三期顺利举办
百度李小婉:AI时代,百度APP将带来全新信息获取方式
百度薛苏:文心一言APP致力于成为每个人的随身智能助手
制造业单项冠军!鹏力塑造成功上榜!
第九届金蝶云会计节盛大启幕,引领AI时代会计转型成长
Creo软件:赋能工业设计与制造的全流程
探索中小企业数字化转型新路径,“数智笃行”数字化赋能生态大会成功举行
大学生在抖音开拓就业新方向,全职探店为宝藏小店带去生意增量
颠覆传统开发!青云QingCloud云原生助力金融数据腾飞
茉酸奶坚守原料品质,持续强化品牌影响力
毫末获颁浦东新区首批无人驾驶装备创新应用识别标牌 5台小魔驼上海当起配送员
宏碁即将亮相台北电脑展!如何用科技创新“打破AI的藩篱”?
AI工具助力高效办公 三星Galaxy S24系列释放生产力潜能
助燃新质生产力,江苏移动启动“AI+”行动计划
WiFi万能钥匙助力创作梦想:小人物也能成为大V
节能减碳有成效!时链科技推动医院零碳数智化转型