一种二维架构下的量子电路布局与优化方法.pdf
《一种二维架构下的量子电路布局与优化方法.pdf》由会员分享,可在线阅读,更多相关《一种二维架构下的量子电路布局与优化方法.pdf(12页珍藏版)》请在咨信网上搜索。
1、第 40 卷 第 4 期2023 年 7 月量 子 电 子 学 报CHINESE JOURNAL OF QUANTUM ELECTRONICSVol.40 No.4Jul.2023一种二维架构下的量子电路布局与优化方法一种二维架构下的量子电路布局与优化方法张 超,管致锦*,冯世光,牛义仁,朱明强(南通大学信息科学技术学院,江苏 南通 226019)摘要:为解决将量子电路映射到二维架构并实现量子位近邻问题,提出了一种二维架构下的量子电路布局与优化方法。首先根据量子门在量子电路中的执行顺序和相互作用,提出基于量子位权重的深度优先搜索量子位映射次序,再考虑到映射次序的已放入量子位、待放入量子位和未放
2、入量子位的关系进行量子位的初始布局实现量子位的初始映射;进而对近邻过程中的相同前瞻量子代价的选择进行了优化,再根据优化后的代价结果,插入SWAP门,实现所有双量子门的最近邻。最后利用实验对提出的方法进行了验证,并与已有的方法进行了比较。结果表明所提出方法在中小规模的基准电路上平均优化率达到18%,在中大规模的基准电路上平均优化率达到17%。关 键 词:量子物理;量子电路;量子映射;最近邻;二维架构中 图 分 类 号:TP302.2 文 献 标 识 码:A 文章编号:1007-5461(2023)04-00570-12A quantum circuit layout and optimizati
3、on method in twodimensional architectureZHANG Chao,GUAN Zhijin*,FENG Shiguang,NIU Yiren,ZHU Mingqiang(School of Information Science and Technology,Nantong University,Nantong 226019,China)AbstracAbstract t:In order to solve the problem of mapping quantum circuits to two-dimensional architecture and r
4、ealizing qubit nearest neighbor,a quantum circuit layout and optimization method in two-dimensional architecture is proposed.Firstly,according to the execution order and interaction of quantum gates in quantum circuit,a depth-first search qubit mapping order based on the weight of qubits is proposed
5、,then the initial qubit mapping is realized by taking into account the relationship between the put qubits in the mapping order,the qubits to be put in and the unput qubits.Secondly,the selection of the same look-ahead quantum cost in the nearest neighbor process is optimized,then according to the o
6、ptimized cost results,SWAP gates are inserted to realize the nearest neighbor of all double quantum gates.Finally,the proposed method is verified by experiments and compared with the existing methods,and it is shown that DODOI I:10.3969/j.issn.1007-5461.2023.04.016基金项目:国家自然科学基金面上项目(62072259),江苏省研究生科
7、研与实践创新计划项目(SJCX20_1151)作者简介:张 超(1996-),江苏扬州人,研究生,主要从事计算机辅助量子逻辑综合方面的研究。E-mail:chao_z_导师简介:管致锦(1962-),江苏连云港人,博士,教授,博士生导师,主要从事量子计算、逻辑综合、信息安全、计算机辅助智能制造等方面的研究。E-mail:收稿日期:2021-04-12;修改日期:2021-05-24*通信作者。第 4 期张 超 等:一种二维架构下的量子电路布局与优化方法the average optimization rate of the propsed method reaches 18%on the sm
8、all and medium-sized Benchmark and 17%on the medium and large-scale Benchmark.K Keyey wordswords:quantum physics;quantum circuits;quantum mapping;nearest neighbor;two-dimensional architecture0 引 言量子计算能够比经典计算更快地解决某些重要问题,如整数因子分解1、未排序数据库搜索2等。许多研究工作都致力于发现新的量子算法和量子技术,然而,当前的超导3、量子点4等量子技术具有相当大的局限性。目前的量子技术要
9、求双量子位门之间发生相互作用时必须是近邻的状态且量子技术所支持的物理架构大多是二维的,最新的量子计算平台IBMQ5上支持的物理架构也都是二维的。量子电路是量子算法的一种描述方法。而实现量子线路描述的量子算法,需要将量子电路映射在物理架构上。此外,考虑到当前量子技术的局限性,映射过程中还需要考虑双量子门的近邻约束。为了解决上述问题,研究人员提出各种将量子逻辑电路映射在物理架构上的方法610。Shen等6提出的和谐算法在小规模量子电路上具有很好的表现,但是随着电路规模的扩大,时间复杂度较高,极易产生超时问题。Hattori等7提出SAT求解器来处理初始映射问题,但是在最近邻过程中采用的是A*算法。
10、A*算法的搜索空间随着电路规模呈指数增长,不适用于映射大规模电路。Zulehner等8提出了基于IBM QX架构的量子电路映射方法,该方法虽然可以处理任意量子位的耦合,但由于是穷尽搜索,运行时间较长,且初始映射缺乏全局优化能力。Zhang等 9提出了一种基于量子位活跃度的将一维量子电路映射在二维量子电路上的方法,该方法在大规模电路中的表现较好,但是在中小规模电路上表现不佳。Farghadan等10提出了量子位放置优先级的概念,将映射方法分为三个部分:量子位映射次序搜索;二维映射布局;最近邻优化。该方法具有很好的扩展性,但是仍然存在两个问题:1)量子位次序搜索采用的方法只考虑了两个量子位之间关联
11、的量子门数,没有考虑量子门在量子电路的先后次序;2)最近邻优化过程中没有考虑相同前瞻量子代价调整的问题。本文提出了一种二维物理架构下的量子位布局和最近邻方法。该方法分为两个部分:量子位初始映射算法、最近邻优化算法。并且在最近邻优化上引入了相同前瞻量子代价的调整方法,该方法能够有效地解决二维物理架构下量子位的映射与最近邻问题。对IBMQ上的多个基准电路进行了实验验证,结果表明所提出的方法在大多数基准电路上均能实现一定程度的优化,其中最大优化率可达69%。1 基本概念1.1 量子比特在经典计算机中,一个经典比特具有0和1两种可能状态。而在量子计算机中,一个量子比特也有两种可能状态:|0和|1。不同
12、于经典比特,量子比特的状态可以落在|0 和|1 之外,量子比特可以是状态的线性组合,称之为叠加态,表示为|=|0+|1,其中、是复数,称为几率幅,且满足归一化条件,即|2+|2=1。表示处在|0 的概率是|2,处在|1 的概率是|2,这里|表示复数 的模。1.2 量子电路量子电路是用于量子计算的模型。量子电路上的量子位通过量子门来实现量子操作。量子门是作用在571量 子 电 子 学 报40 卷量子位上的幺正变换,用来修改量子位的状态。常用的量子门门库有NCV、MCT、Clifford+T门库等;常用的Clifford+T门库里的量子门有CNOT、NOT、H、T门。用符号表示量子门时,代表控制位
13、,代表目标位。一些基本量子门的符号表示如图1所示。图1 基本量子门。(a)NOT门;(b)CNOT门;(c)T门;(d)H门Fig.1 Elementary quantum gates.(a)NOT gate;(b)CNOT gate;(c)T gate;(d)H gate2 量子位初始映射量子位初始映射讨论将一维量子电路如何映射在二维网格布局上。本研究将量子位初始映射问题分为两个子问题进行讨论:1)量子位究竟按照怎样的次序进行映射;2)量子位应该如何映射在二维网格上。为了解决以上问题提出了量子位映射次序搜索算法和二维映射布局算法。2.1 量子位映射次序搜索定义1:在N个量子门、M个量子位的一
14、维量子电路 G=G1G2G3GiGN(0iN)中,给每个量子门的位置编号i,其值 Gi 代表该量子门的位置权重,量子门的权重之和Qwj(0jM)代表该量子位的权值。在一维量子电路中,某个量子门gi的控制位ci或者目标位ti的位置权重 Gi 可以表示为Gi=N-i+1N,(1)量子电路中某条量子电路(量子位)上的权重 Qwj 可以表示为Qwj=i=1NGi.(2)根据定义可知权值最大的量子位代表与其可以交互的量子门个数最多,所以在量子位映射的过程中应该优先考虑量子位权重最大的量子位,且考虑量子门在量子电路中的先后次序。因此,在二维映射布局前要先确定量子位映射的次序,此处提出了一种基于量子位权重的
15、深度优先搜索量子位映射次序的方法。用于初始映射的原始量子电路如图2所示,量子门的序号是111,量子门个数是11。根据(1)、(2)式可以计算出每条量子电路的权重。选出其中权重最大的量子位q3。因为量子位的权重越大表明与之发生交互作用的量子位越多,所以次序中的第一个量子位是权重最大的量子位。考虑到量子门在量子电路中的先后次序,本研究采用深度优先搜索的方式搜索量子位映射次序。所以从量子位q3开始进行深度优先搜索量子位映射次序。如图2所示的一维量子电路的量子位映射顺序是q3、q1、q2、q0、q4。量子位映射次序搜索算法如下:算法算法1:量子位映射次序搜索输入输入:N个量子门,M个量子位的一维量子电
16、路:G=G1G2G3GiGN.(0iN)(0jM)输出输出:量子位映射次序队列queue572第 4 期张 超 等:一种二维架构下的量子电路布局与优化方法1:生成当前量子位上的相关门列表gate2:计算每个量子位上的权重Qwj。3:queuej=max(Qwj)4:初始化临时存储栈stack,栈位置索引s_index,量子位映射次序队列queue5:stack0=queuej,queue0=queuej6:While len(queue)M7:初始化量子位上量子门的临时存储列表temp,临时存储位置索引g_index8:For qbit gatestacks_index do9:If w qu
17、eue do10:stack.append(qbit),q.append(qbit)11:s_index=s_index+112:break13:If w queue do14:temp.append(w)15:g_index=g_index+116:If g_index=len(gatestacks_index)do17:stack.pop()/回溯至上一个量子位18:s_index=s_index-119:End For图2 用于初始映射的原始量子电路Fig.2 The original quantum circuit for the initial mapping2.2 二维映射布局二维
18、映射布局的目标是将由一维量子电路表示的量子算法上的量子位近邻地布局在二维网格上,这样的量子位布局问题已经被证明是NP完全问题11。根据2.1中的量子位映射次序搜索算法,可以找到量子位的映射次序。在映射次序中考虑已放入量子位、待放入量子位和未放入量子位之间的关系,为了衡量每个布局位置的优劣程度,这里引入代价函数f 10。定义2:在mn(m 3,n3)的二维网格中,(m-12 n-12)称为网格的中心位置。如图3所示,是一个3 3的二维网格,中心位置是图中黑色的位置(1,1),中心的位置有更多的位置与之近邻,图中画圈的位置代价与中心相邻的位置。573量 子 电 子 学 报40 卷 012012中心
19、位置:(1,1)图3 3 3的二维网格中心位置示意图Fig.3 A 3 3 two-dimensional grid center location diagram根据2.1节中定义的量子位权重,可知权重越大的量子位表示与其交互的量子位越多。而在二维网格中越是中心的位置越可以与更多近邻位置上的量子位进行交互,因此将量子位映射次序中的第一个量子位映射在二维网格的中心,再根据量子位的映射次序完成量子电路上量子位的二维映射布局。2.2.1量子位交互图量子位交互图可以表示量子位之间的相互关系,也可以描述量子电路中相互作用的量子比特的频率12,其中两量子位之间的关系代表两个量子位之间相关的量子门的个数。
20、如图4所示的量子位交互图是基于图2的一维量子电路构建的,可以反映出该量子电路量子位之间的相互关系。其中有5个点,代表一维量子电路上的5个量子位,两个点之间的数代表两个量子位之间相互关联的量子门个数。图4 量子位交互图Fig.4 Qubit interaction diagram2.2.2代价函数在量子位映射过程中,为了衡量量子位映射位置的优劣,引入代价函数 f。考虑到已放入量子位与待放入量子位之间的关系,引入 f1计算代价;考虑到待放入量子位与未放入量子位之间的关系,引入 f2计算代价。其中已放入量子位、待放入量子位和未放入量子位都是根据量子位映射次序确定的。再根据2.2.1节中提出的量子位交
21、互图可以计算出量子位中已放入量子位、待放入量子位和未放入量子位之间的代价,选择代价最小的位置放置量子位。代价函数 f 可以表示为f=f1+f2 (3)式中:f1=(dist(dloc(nbrvi0)-1)nbrvi1),代表当前量子位与已放入量子位nbrv 之间的代价关系,其中 i 代表与当前量子位相关的已放置量子位索引,nbrv i 0 代表与当前量子位相关的已放置量574第 4 期张 超 等:一种二维架构下的量子电路布局与优化方法子位,nbrv i 1 代表与当前量子位相关的已放置量子位上的量子门个数,d代表当前二维网格类型,loc()代表当前量子位所在位置和已放入量子位位置的欧氏距离;f
22、2=min0deg(v)-frd(v)act()vdeg()v 代表当前量子位与待放置量子位的代价关系,其中 deg(v)代表下一个待放置量子位与未放置量子位在量子位交互图中的度,act(v)代表下一个待放置量子位与未放置量子位在量子位交互图上的度的权值之和,frd(v)表示在当前网格周围可放置量子位的空白网格的个数。根据量子位映射的次序,将第一个量子位映射在网格的中心。然后根据当前所有位置,找出所有位置的未放置的近邻位置,根据代价函数 f 计算每个位置的代价,选择代价最小的位置映射量子位。二维映射布局的算法如下:算法算法 2:二维映射布局输入输入:N个量子门,M个量子位的一维量子电路:G=G
23、1G2G3GiGN.(0iN)(0jM),量子位映射次序队列queue和WH的二维网格grid输出输出:量子位的二维布局1:生成量子位交互图G(V,E),vV2:初始化顶点的待映射量子位与未映射量子位的度deg(v)3:初始化所有度的权值之和表act(v)4:初始化当前量子位放置周围可继续放置位置的个数表frd(v)5:初始化量子位的邻接数组nbrv6:将q0映射在二维网格grid的中心位置。更新deg(v),act(v),frd(v),nbrv7:For temp_q_bit queue1:do8:生成网格中已放置位置的近邻位置列表qbit_mapped_nbr_list9:For d qb
24、it_mapped_nbr_list do10:计算每个位置的代价f(d)11:min(f(d)grid(temp_q_bit)12:更新deg(v),act(v),frd(v),nbrv13:End For14:End For3 最近邻优化初始映射并不能使量子电路上所有的量子门实现近邻,需要插入SWAP门来更新映射,从而在整个映射过程中量子电路的所有双量子门都能够进行近邻化操作。575量 子 电 子 学 报40 卷3.1 量子代价量子代价是衡量量子电路综合优化能力的重要指标。一个量子电路的量子代价通常可以通过量子电路的深度、执行时间、基本门数、最近邻过程中添加的SWAP门数等来衡量。在映射量
- 配套讲稿:
如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。