基于交换门的前瞻启发式量子线路映射算法.pdf
《基于交换门的前瞻启发式量子线路映射算法.pdf》由会员分享,可在线阅读,更多相关《基于交换门的前瞻启发式量子线路映射算法.pdf(9页珍藏版)》请在咨信网上搜索。
1、基于交换门的前瞻启发式量子线路映射算法张辰逸,尚涛*,刘建伟(北京航空航天大学网络空间安全学院北京海淀区100083)【摘要】含噪声中规模量子硬件的耦合约束使得大多数量子算法通过插入附加量子门改变量子位映射,令量子算法直接运行在硬件上。为了降低量子线路的运行时间及提高量子线路的保真度,设计了一种基于交换门的前瞻双向启发式映射算法。首先,利用前瞻机制考虑前端层信息,提高了附加门数结果的稳定性。其次,设计搜索策略评估物理上近邻的候选交换门,降低交换门搜索空间的复杂度。最后,采用双向遍历全局考虑量子线路的门信息,得到更高质量的初始映射。此外,该算法适用于任意耦合量子硬件架构,同时具有线路深度和附加门
2、数的选择能力。实验结果表明,相较于主流算法 A*-based 算法和 SABRE 算法,该文提出的 SPBHA 算法可减少约 68%与 34%的附加门数,线路执行时间缩短,保证了量子程序结果的可靠性。关键词耦合约束;映射;前瞻双向;量子计算;量子线路中图分类号TP38;O413文献标志码Adoi:10.12178/1001-0548.2022339SWAP-BasedProspectiveHeuristicQuantumCircuitMappingAlgorithmZHANGChenyi,SHANGTao*,andLIUJianwei(SchoolofCyberScienceandTechno
3、logy,BeihangUniversityHaidianBeijing100083)Abstract The coupling constraint of noisy intermediate-scale quantum hardware makes most quantumalgorithmschangequantumbitmappingbyinsertingadditionalquantumgates,sothatquantumalgorithmsrundirectlyonthehardware.Inordertoreducethequantumcircuitrunningtimeand
4、improvethequantumcircuitfidelity,thispaperdesignsaSWAP-basedprospectiveheuristicquantumcircuitmappingalgorithm.First,theprospective mechanism is used to consider the front layer information,which improves the stability of theadditionalgatecountresults.Secondly,thesearchstrategyisdesignedtoevaluateth
5、ephysicallyclosecandidateSWAPgatestoreducethesearchspacecomplexityofSWAPgates.Finally,abidirectionaltraversalisusedtogloballyconsiderthegateinformationofquantumcircuitstoobtainhigherqualityinitialmappings.Theproposedalgorithmissuitableforarbitrarycoupledquantumhardwarearchitecture,andhastheabilityto
6、selectcircuitdepthandadditionalgatenumber.TheexperimentalresultsshowthatcomparedwiththemainstreamalgorithmsA*-basedalgorithm(AlgorithmbasedonA*search)andSABREalgorithm(SWAP-basedBidiREctionalheuristicsearchalgorithm),theSPBHA(SWAP-basedProspectiveBidirectionalHeuristic)algorithmproposedinthispaperca
7、nreducethenumberofadditionalgatesbyabout68%and34%,shortenthecircuitexecutiontime,andensurethereliabilityofthequantumprogramresults.Keywordscouplingconstraint;mapping;prospectivebidirectional;quantumcomputing;quantumcircuit量子计算强大的并行计算加速能力使其在量子模拟、整数分解、数据库搜索以及机器学习等领域具有巨大潜力14。未来量子计算将进入有噪声的中规模量子计算机(noisy
8、intermediate-scalequantumcomputer,NISQ)时代5。谷歌、IBM、华为等公司相继提供了 72、50、42 个量子位的量子计算模拟器6-7,量子计算的加速潜力正在逐步实现。由于 NISQ 时代技术限制,只有在量子硬件耦合架构上允许相连的量子位上可以发生交互。通过量子线路映射算法,量子程序才能高效地编译并运收稿日期:20220930;修回日期:20221015基金项目:国家自然科学基金(61971021);河北省重点研发计划(22340701D);航空科学基金(2018ZC51016)作者简介:张辰逸(2000),博士生,主要从事网络安全、量子计算方面的研究.*通
9、信作者:尚涛,E-mail:第52卷第4期电子科技大学学报Vol.52No.42023 年 7 月JournalofUniversityofElectronicScienceandTechnologyofChinaJul.2023行在量子硬件上。在量子程序编译的过程中如何高效地进行量子线路映射至关重要。研究成果表明,优秀的量子线路映射算法8可以将量子线路中的附加量子门数降低 80%,甚至无需附加量子门,缩短量子线路运行时间,保证运行结果的可靠性。量子线路映射问题已经被证明是 NP 完全问题9,在量子线路规模日益增大、架构日益复杂的今天,更为灵活、扩展性更佳的启发式算法是量子线路映射算法的主要研
10、究方向10。目前,国内外学者对量子线路启发式映射算法已开展了许多研究。文献 11 令初始映射优先满足物理上相邻的CNOT 门,每次量子位移动,只解析一个双量子位门,根据它们之间的双量子位门数量决定是否移动量子位。虽然算法速度很快,但过于简单,效果一般。文 献 12 尝 试 将 A*-based(algorithm basedonA*search)算法引入启发式成本函数,将双量子位门划分为独立的层,最小化层中耦合量子位之间的距离之和,同时减少最终输出线路的深度。不足在于搜索所有可能的并发 SWAP 门组合仍然需要指数时间,初始映射只由线路开始时的两个量子位门决定,不考虑全局性。文献8 提出了SA
11、BRE(SWAP-basedBidiREctionalheuristicsearchalgorithm)算法,对量子映射进行更加精准的建模,通过优化每次搜索尝试,将指数复杂度的搜索空间缩小至线性复杂度,但存在附加门数不稳定的问题。文献 13 使用动态分配并回收量子位来对占用的计算资源进行优化。现有的量子线路映射算法相关研究主要关注量子位映射的中间变换策略,对量子位映射的初始化方式关注较少。研究表明初始量子位映射对量子线路映射算法的结果有很大影响8,在中间映射变换之前利用已知量子线路信息提前对量子位映射初始化是一种行之有效的优化方式。本文致力于设计高效的量子线路映射算法,利用前端层信息初始化量子
12、位映射,采用耦合图节点近邻化代替全局搜索,有助于降低量子程序执行时间,提高量子线路保真度。1量子线路映射问题由于量子位具有连接脆弱、串扰和状态不稳定等特性14,因而量子线路运行在实际量子硬件中可能会遇到以下 3 种错误类型:相干时间15、量子位保真度16与量子位耦合约束17。相干时间与量子位保真度需要量子硬件的技术进步来改善,量子位的耦合约束则可以通过软件层面的量子线路映射算法解决。Q1,Q2 Q2,Q4 Q4,Q3 Q3,Q1Q1,Q4Q2,Q3q1 Q1,q2 Q2,q3 Q3,q4 Q4结合一个小规模量子线路示例进一步解释量子线路映射问题,如图 1 和图 2 所示。4 量子位硬件模的硬件
13、架构采用图 2a 所示的硬件耦合图。该硬件模型允许在以下量子位对上使用双量子位门:,,不允许在和上使用双量子位门。假设有一个小规模量子线路要在图 2 所示的 4 量子位设备上执行。该量子线路由 6 个 CNOT 门组成(如图 2b 所示),假设初 始 的 逻 辑 量 子 位 到 物 理 量 子 线 路 映 射 为。q2q1q2q1HHHHa.SWAP 操作b.换向操作图1更改映射关系的量子操作q1(Q1)q2(Q2)q3(Q3)q4(Q4)原始线路CNOT q2 q1CNOT q3 q4CNOT q2 q3CNOT q1 q4CNOT q4 q3CNOT q1 q2Q1Q2Q3Q4a.量子芯片
14、物理耦合架构图b.原始量子线路图2更新前的量子线路及其硬件架构由图 2a 可见,6 个 CNOT 门中有 4 个可以直接执行,第 3 个和第 4 个 CNOT 门无法执行,因为相应的量子位对没有连接到硬件上。图 2 的量子线路示例中不存在满足所有双量子位门依赖关系的完美初始映射,需要在程序执行期间更改量子位映射,使所有 CNOT 门都可执行。q1q2q1 Q2,q2 Q1,q3 Q3,q4 Q4主流的更改映射方法为使用 SWAP 门(即交换门),通过在两个量子位之间交换状态来改变量子线路映射(如图 1a 所示)。SWAP 门由 3 个 CNOT门组成。如果两个量子位在量子器件上并不相邻,可以使
15、用多个 SWAP 门将 1 个逻辑量子位移动到任意物理量子位的位置,然后在线路中应用双量子位门。如图 3 所示,在第 2 个 CNOT 门之后的 和之间插入 1 个 SWAP 门,更新后量子线路是可以执行的。前两个 CNOT 门可以在初始映射下执行。插入SWAP 门后,映射更新为,所有剩余的 4 个 CNOT 门都可在此映射下执行。当量子线路应用在非对称硬件模型时,即只允许运行方向符合连通关系的双量子位门时,可使用490电子科技大学学报第52卷|01|+基变换技术,添加 4 个 Hadamard 门,将基转换为,从而实现 CNOT 门换向操作,如图 1b所示。q1(Q1)q2(Q2)q3(Q3
16、)q4(Q4)q1(Q1)q2(Q2)q3(Q3)q4(Q4)CNOT q2 q1CNOT q3 q4SWAP q1 q2CNOT q2 q3CNOT q1 q4CNOT q4 q3CNOT q1 q2更新线路图3更新硬件映射后的量子线路在量子线路中引入额外的 SWAP 门可以解决所有双量子位门的依赖性,并在不改变原有功能的情况下生成硬件兼容线路。由于 NISQ 硬件设备的限制,在量子线路中插入 SWAP 门会导致以下问题。1)量子线路中的操作次数增加,由于操作不完美,会引入噪声,导致总体错误率会增加。2)量子线路深度会增加,导致执行时间将增加,且量子线路的退相干可能会累积许多错误。比较图 2
17、b 和图 3 中的原始线路和更新线路,量子门的数量从 6 增加到 9,线路深度从 5 增加到8。额外的 SWAP 门将在保真度和执行时间方面带来巨大的开销,需要量子线路映射算法来尽量减少额外 SWAP 门的数量,降低总体错误率和总执行时间。2SPBHA 算法本文在量子线路映射算法 SABRE 算法8的基础上,保留 SABRE 算法双向遍历和就近搜索候选SWAP 门空间的特点,使用前端层信息初始化量子线路映射代替随机初始化量子位映射,并对遍历流程和启发式代价函数进行改进,设计了基于交换门的前瞻双向启发式算法(SWAP-basedprospectivebidirectional heuristic
18、 algorithm,SPBHA)。SPBHA算法包含 4 个部分:预处理、单次遍历、双向遍历更新映射与启发式代价函数,表 1 定义了 SPBHA算法使用的数学符号。2.1预处理SPBHA 算法预处理的具体步骤如下。DijQiQj计算距离矩阵:给定量子器件的耦合图,通过Floyd-Warshall18算法计算所有点对最短路径(allpairsshortestpath,APSP),以获得距离矩阵 D,耦合图每条边距离为 1。表示将逻辑量子位从物理量子位移动到所需的最小 SWAP 数。表 1SPBHA 算法数学符号定义数学符号定义n逻辑量子位数q1,2,n量子线路中的逻辑量子位Q1,2,n量子设备
19、中的物理量子位d量子线路的深度g量子线路的量子门序号N物理量子位数G(V,E)量子硬件的耦合图DDijQiQj物理量子位的距离矩阵,表示到的距离q1,2,nQ1,2,n到的映射关系1Q1,2,nq1,2,n到的映射关系F前端层E扩展集qiqjCNOT(qi,qj)q2g1g3g1g3g3g1生成量子线路有向无环图(directedacylicgraph,DAG):使用 DAG表示量子线路中受控非门 CNOT门的依赖顺序。单量子位门只在一个量子位上执行,不会对其他量子位产生依赖,因而量子线路映射算法不考虑单量子位门。当 CNOT 门的两个量子位 或上所有之前的 CNOT 门都已执行时,才能执行。
20、遍历整个量子线路,并构造一个 DAG。图 4b 的 DAG 是由图 4a 的量子线路生成的。如由于量子位同时存在于量子门 和量子门中,而在之前不能执行,所以量子门依赖于量子门。以此类推,根据量子门之间的依赖关系生成 DAG。q1g1g1g3g4g5g6g7g2g3g4g5g6g7g2q2q2q3q4q1q3q3q2q2q4q1q3q4HHHZTYSTT.前端层a.原始线路b.量子线路 DAG图4原始线路生成 DAG 的示例以及前端层初始化CNOT(qi,qj)qiqj初始化前端层:前端层(F)被定义为 DAG 中没有未执行前导的所有 CNOT 门的集合,意味着对应的双量子位门没有依赖性,可以立
21、即在硬件上执行。对于,当 CNOT 门的两个量子位 或上所有之前的量子门都被执行时,它可以被放置在集合 F 中。遍历第二步得到 DAG,并找第 4 期张辰逸,等:基于交换门的前瞻启发式量子线路映射算法491g1g2到图中入度为 0 的所有顶点(量子门),将这些量子门放入 F,以初始化 F。图 4 中,初始化的前端层包含 和,因为它们没有前导。CNOT(q1,q3)q1Q1Q1q3Q2q1q3CNOT(q2,q6)q6Q6q2Q3利用前瞻机制初始化量子位映射:SPBHA 算法使用前端层量子门的信息,在进行单次遍历算法之前利用前瞻机制对量子位映射进行出初始化。图 5c 线路使用图 5a 量子硬件架
22、构,并根据定义(见表 1)划分出前端层、前端层的后继门组成的短期层和远离前端层的长期层。在前端层的中,将 映射到,并根据相邻的物理量子位情况,将映射到,使得 和的物理量子位相邻,该 CNOT 门无需插入任何 SWAP 门可以直接在硬件上运行。同理,中,映射到,映射到。在满足前端层的量子门均可以直接在硬件上运行后,剩余未映射的量子位进行随机分配。图 5b 中虚线框的映射为利用前瞻信息初始化的映射,实线框映射为随机初始化映射。由于量子程序具有与经典程序类似的局部性原理,作用在相同量子位对上的量子门可能在短时间内再次运行。利用局部性原理,SPBHA 算法可以进一步减少附加门的数量,提高算法效率。由于
23、前端层的量子门之间没有依赖性,因此必然可以找到一个使得满足前端层量子门均可以直接在硬件上运行的初始量子位映射。Q1q1Q1q2Q2q3Q3q4Q4q5Q5q6Q6Q4Q2Q5Q3Q6a.量子硬件架构b.量子线路与基于前端层的初始化映射CNOT q1 q3CNOT q2 q6CNOT q4 q1CNOT q2 q5.前端层短期层(前端层后继门)长期层(暂不考虑)图5利用前瞻机制初始化量子位映射2.2单次遍历算法 1单次遍历算法Input:距离矩阵 D、线路 DAG、初始 F 和初始映射uOutput:更新的量子映射,插入 SWAP门的信息F=whiledoExecute_gate_list /*
24、初始化可执行门集合*/;gate Ffordoif量子门可直接在硬件上运行thenExecute_gate_list.add(gate)/*添加可执行门*/;endendExecute_gate_list,ifthengate Execute_gate_listfordoF.remove(gate);从 DAG 中获得 F 的后继门 successor_gate;F.add(successor_gate);/*添加后继门*/;endendelsescore /*初始化评分数组*/;SWAP_Candidate_list GetSWAP(F.G)/*根据前端层和耦合图得到候选插入的 SWAP 门
25、*/;SWAP SWAP_Candidate_listfordotemp.update(SWAP)/*用 当 前SWAP 门暂时更新映射*/;scoreSWAP H(temp,F,D,DAG,SWAP);/*根据启发式代价函数获得 SWAP 门的评分*/;F.add(successor_gate);end找到最佳评分的 SWAP 门;.update(SWAP)/*用当前 SWAP 门更新映射*/;endend算法 1 描述了 SPBHA 的单次遍历算法流程,算法扫描整个 DAG 并插入 SWAP 门,以使所有CNOT 门都可执行。在单次遍历算法的每次迭代中,检查 F 中是否有任何可以直接在硬件
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 交换 前瞻 启发式 量子 线路 映射 算法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。