面向可靠性的CNOT量子线路最近邻综合.pdf

第 40 卷 第 4 期2023 年 7 月量 子 电 子 学 报CHINESE JOURNAL OF QUANTUM ELECTRONICSVol.40 No.4Jul.2023面向可靠性的面向可靠性的CNOTCNOT量子线路最近邻综合量子线路最近邻综合朱明强,申文杰,牛义仁,张 超,程学云*,管致锦,陈 亮(南通大学信息科学技术学院,江苏 南通 226019)摘要:在噪声中等规模量子(NISQ)设备上,量子线路可靠性受到量子噪声的影响。为了实现CNOT量子线路在量子芯片上高效可靠的执行,以相邻量子位交互错误率为权重,给出了计算最小Steiner噪声路径长度的代价度量方法,提出了噪声感知的CNOT量子线路最近邻综合算法。实验结果表明,与现有方法相比,所提出的综合算法在保证线路可靠性的前提下,有效地降低了综合过程中所使用CNOT门的数量,CNOT门代价的平均优化率达到27.7%,其中200门级的CNOT量子线路优化率达到了93.79%。关 键 词:量子计算;CNOT 量子线路;Steiner 树;噪声;可靠性中 图 分 类 号:TP302.2 文 献 标 识 码:A 文章编号:1007-5461(2023)04-00560-10Reliabilityoriented nearest neighbor synthesis of CNOT quantum circuitsZHU Mingqiang,SHEN Wenjie,NIU Yiren,ZHANG Chao,CHENG Xueyun*,GUAN Zhijin,CHEN Liang(School of Information Science and Technology,Nantong University,Nantong 226019,China)AbstracAbstract t:In noisy intermediate-scale quantum(NISQ)devices,the reliability of quantum circuits is affected by quantum noise.In order to realize the efficient and reliable execution of controlled-NOT(CNOT)quantum circuit on a quantum chip,a cost measurement method for calculating the minimum Steiner noise path length is presented,taking the interaction error rate of adjacent qubits as the weight.Then based on this method,a noise-aware nearest neighbor synthesis algorithm for CNOT quantum circuits is proposed.The experimental results show that,compared with the existing methods,the proposed algorithm can effectively reduce the number of CNOT gates used in the synthesis process on the premise of ensuring the reliability of the circuit.The average optimization rate of CNOT gate cost reaches 27.7%,and the optimization rate of 200-gate CNOT quantum circuits reaches 93.79%.K Keyey wordswords:quantum computation;CNOT quantum circuits;Steiner tree;noise;reliabilityDODOI I:10.3969/j.issn.1007-5461.2023.04.015基金项目:国家自然科学基金(62072259),江苏省研究生科研与实践创新计划项目(SJCX21_1448)作者简介:朱明强(1996-),江苏南通人,研究生,主要从事物理受限的CNOT量子线路综合方面的研究。E-mail:zhu_.导师简介:程学云(1978-),女,江苏南通人,副教授,硕士生导师,主要从事可逆计算和可逆线路优化方面的研究。E-mail:收稿日期:2021-05-14;修改日期:2021-06-15*通信作者。第 4 期朱明强等:面向可靠性的CNOT量子线路最近邻综合0 引 言随着噪声中等规模量子(NISQ)时代的到来,量子计算机可以执行超越当前经典计算机能力范围的任务1。由于量子计算在因式分解2、数据库搜索3、量子模拟4等应用中有很大潜力,近年来其已成为非常重要的研究领域之一。IBM、英特尔和谷歌已经分别发布了65、49和72量子比特的量子计算机5,6,促进了量子计算的发展。当前主流的技术如超导7、离子阱8等对量子位交互施加了连接限制。在量子线路综合时需要考虑量子比特之间严格的内在约束,如相互作用距离、退相干性等,这些约束条件要求在量子线路综合时考虑最近邻(NN)约束。CNOT量子线路是量子计算机实现量子算法的基本线路,研究CNOT量子线路的综合对量子线路在实际量子芯片上的可靠运行非常重要9。文献10将CNOT量子线路表示为布尔矩阵,提出了一种基于高斯消元和LU分解的CNOT量子线路综合算法。文献11通过遗传算法找到较好的初始映射,然后利用高斯消元实现CNOT量子线路的综合。目前绝大多数CNOT量子线路的最近邻综合研究只考虑了量子位之间是否近邻,主要通过直接法12或启发式方法13插入SWAP门来实现线路近邻,忽略了实际量子芯片上其他的物理约束。文献14考虑了相邻量子位交互错误率的噪声因素,并给出了映射方法,但仍是基于插入SWAP门来实现线路近邻,在减小CNOT门代价方面仍有改进空间。因此,本文提出了一种噪声感知的CNOT量子线路最近邻综合方法,将量子位之间的CNOT错误率作为实际体系结构下二维拓扑图的权值,给出了计算最小Steiner噪声路径的代价函数。该方法可以在保证线路可靠性的前提下,减少CNOT量子线路最近邻综合过程中使用的CNOT门数量。实验结果表明所提方法的平均优化率达到27.7%,最大优化率达到93.79%。1 基本概念1.1 CNOT量子线路在经典计算机中,最基本的单元是bit,即0和1这两个有确定性状态的基本信息单元。在量子计算机中,最基本的单元是量子比特(Qubit),它不仅可以存在于状态|0或|1,也可以存在于这两个状态线性组合的中间状态上,这种状态称为叠加态,可以表示为:|=|0+|1,其中 和 是复数,并且满足条件|2+|2=1。量子门是应用在量子位上的幺正操作,用于修改量子位状态。用符号表示量子门时,表示控制位,表示目标位。一个量子位上应用一个单量子位门,CNOT门是一个双量子位的操作,它会通过控制位的状态值决定目标位的值是否进行取反操作。如图1所示,在线性结构下,a 是控制位量子比特,b 是目标位量子比特,记为CNOT(a,b),输出 b=ba,式中 表示异或运算。如果控制位输入1,则目标位上的输出值取反,否则输出值保持不变。如果控制位和目标位的位置相邻,则称为最近邻CNOT门。量子线路是量子算法的一种表示,其中每一行代表一个量子比特,通过这些行上的一组门的操作表示量子算法。如果量子线路仅由CNOT门级联而成,则称为CNOT量子线路。图2显示了具有3个CNOT门的CNOT量子线路,CNOT量子线路中CNOT门的数量称为CNOT量子线路的长度。561量 子 电 子 学 报40 卷1.2 布尔矩阵CNOT门可以由布尔矩阵表示15。矩阵阶数对应量子位的位数,矩阵的每一行代表一个量子位,每一列代表一个输入变量。就某一列而言,当存在以当前列量子位为控制位的输入变量时,目标位所在行为1,否则为0。表1为图1所示CNOT门的布尔矩阵,其输入为单位矩阵,输出为CNOT门对应的矩阵。表1 CNOT门的布尔矩阵表示Table 1 Boolean matrix representation of a CNOT gateLinea bIdentity matrix 1001Boolean matrix 1011对于任意一个在n量子位体系结构下的CNOT门,在变量域x1x2xixjxn中,xi是控制位,xj是目标位,则对应的 nn 布尔矩阵为:除主对角线外,第j行的第i 列元素为1,其余元素为0,这种矩阵称为基本矩阵。图2所示CNOT量子线路的布尔矩阵是从110100000000100110010000010010011001000000101001=1101000001101001 ()1中得出的,此式是线路中每个CNOT门的布尔矩阵的逆积。该过程等同于从单位矩阵开始,将每个CNOT门对应的矩阵依次左乘当前矩阵。例如,应用第一个门g1时,将当前矩阵中控制量子位所在的第1行与目标量子位所在的第4行对应元素一一执行异或操作,就可以得到g1门作用后的布尔矩阵。2 噪声感知的CNOT量子线路最近邻综合2.1 量子噪声经典计算机利用晶体管实现设备的运行,出错的概率非常小。而量子计算机中使用的是量子比特,其在相互作用的粒子环境中会失去概率量子行为和存储的信息,执行量子计算会产生量子退相干或噪声。量子噪声会影响量子算法的执行结果,使得量子线路可靠性降低。因此,为了降低退相干等引起的误差,实现量子计算,在进行映射时需尽可能考虑实际量子架构上相邻量子位交互错误率。图3是IBM Q官网提供的图1 CNOT门Fig.1 CNOT gate图2 CNOT线路Fig.2 CNOT circuit562第 4 期朱明强等:面向可靠性的CNOT量子线路最近邻综合ibmq_5_yorktown架构图,表2是该架构的部分校准参数信息,其中CNOT error表示相邻两个量子位运算的错误率,且不同量子位之间的CNOT错误率并不等价。表2 ibmq_5_yorktown 校准数据Table 2 Calibration data of ibmq_5_yorktownQubitQ0Q1Q2Q3Q4T1/s41.1767.1371.8946.7354.5T2/s22.7425.9969.8129.1241.67Single-qubit Pauli-X error2.2610-31.2310-34.9610-44.1110-46.5310-4CNOT error0_2:4.1810-2;0_1:1.12310-21_2:1.01810-2;1_0:1.12310-22_4:1.46310-2;2_3:1.11810-2;2_1:1.01810-2;2_0:4.1810-23_4:1.42910-2;3_2:1.11810-24_2:1.46310-2;4_3:1.42910-2注：T1、T2为量子位退相干时间,Single-qubit Pauli-X error是单量子门泡利X误差在量子线路映射过程中感知量子线路的可靠性,构建可靠的实现量子算法的映射线路,对于提升量子计算成功率和可映射量子线路规模都有着重要意义。图3 ibmq_5_yorktown架构Fig.3 ibmq_5_yorktown architecture2.2 基于Steiner树的CNOT量子线路最近邻综合量子线路综合的目的是合成高效的线路去执行所需的量子计算。对CNOT量子线路综合而言,就是要实现物理最近邻线路,它可以映射为 nn 布尔矩阵上的行消除问题,如高斯消除和LU分解10。用布尔矩阵来描述CNOT门,等价于用当前矩阵乘以相应的基本矩阵,即对当前矩阵执行基本行变换。任意一个可逆布尔矩阵都可以通过应用一系列CNOT门转换为恒等矩阵,在二维拓扑架构上应用CNOT门时,必须考虑最近邻约束。图 4 为一个根据初始映射更新原始矩阵的示例。CNOT 线路中的 CNOT 门序依次为 CNOT(0,2)、CNOT(0,3)、CNOT(1,4)、CNOT(4,1)、CNOT(4,1)。首先,通过文献11提供的遗传算法模型获得逻辑量子位在实际体系结构上的最佳映射,如图4(a)所示;图4(b)为根据原始线路生成的原始布尔矩阵;在保证行列对应关系的前提下,更新原始布尔矩阵获得更好的初始映射布尔矩阵,如图4(c)所示。其次,对矩阵进行综合。先逐列处理矩阵的下三角部分,从二维拓扑图中抽取对应的Steiner树,利用Steiner树消除主对角线元素下方所有值为1的元素,形成上三角矩阵。最后,在不影响已处理好的下三角部分的情况下,同样利用563量 子 电 子 学 报40 卷Steiner树处理上三角矩阵,消除主对线元素上方所有值为1的元素,该过程称为二维拓扑图上的最近邻Steiner消除(SR)方法。此时所有最近邻CNOT门的逆序级联就对应于原始矩阵的等价量子线路。图4 原始布尔矩阵更新示例。(a)初始映射图;(b)原始布尔矩阵;(c)初始映射布尔矩阵Fig.4 An example of update the original Boolean matrix.(a)The initial mapping graph;(b)The original Boolean matrix;(c)The initial mapping Boolean matrix图5 给出了图4(c)中第一列的Steiner消除过程。根据第1列为1的量子位,在ibmq_5_yorktown架构图上找到对应的实际位置,以对角线所在元素为根,从图中提取出当前列的Steiner树,如图5(b)所示,该Steiner树以量子位0为根,量子位4为叶子结点。此时量子位0与3相邻,量子位3与4相邻,可以将量子位3视为传递了量子位0的状态 1。从矩阵角度而言,可以不用第1行来消第4行,而是直接用第3行消第4行,此时既保证了CNOT门的近邻约束,又完成了矩阵的行消除。接着,由于量子位0和3也是近邻的,可以将矩阵的第1行异或到第3行,实现第1列的Steiner消除。图5Steiner消除示例。(a)布尔矩阵第一列消除过程;(b)Steiner消除量子位3和4过程Fig.5An example of Steiner-tree elimination.(a)Elimination of the first column of a Boolean matrix;(b)Eliminates qubit 3 and 4 with Steiner-Tree 2.3 含噪声的CNOT线路综合算法根据含噪声的量子体系结构,提出了一种基于权重查找综合路径的优化方式。利用IBM Q提供的CNOT error参数,得到带权量子拓扑结构图,通过寻找噪声路径长度最低的Steiner树,完成CNOT量子线路最近邻综合。以CNOT错误率为权重的拓扑图称为含噪声拓扑图,通过Floyd算法得到当前拓扑图的多源最短路径集合为Wij,其状态转移方程为564第 4 期朱明强等:面向可靠性的CNOT量子线路最近邻综合Wij=min Wij Wik+Wkj,(2)式中:Wi j表示顶点i到顶点j的最短距离,k是i到j之间可能经过的所有中间点。初始状态W00=0,根据Floyd算法,当中间点为k时,对集合中i到j 的路径长度Wij 进行更新,对所有可能经过的中间点进行遍历以得到全局最优的最短带权路径。记多源最短路径集合Wij的某一中间状态为Wtij,此时顶点i 到顶点j 的边对应的CNOT错误率集合为 e1 e2eien,则Wtij=ni=1ei.(3)定义1:根据矩阵当前列中值为1的量子位,从含噪声拓扑图上得到具有最小噪声路径长度的Steiner树,称为最小噪声Steiner树,该Steiner树中结点i到结点j的路径称为i到j的最小Steiner噪声路径。最小Steiner噪声路径长度可以通过查找当前拓扑图的多源最短路径集合Wij得到。Steiner树中值为0的非叶子结点称为Steiner点,用来传递主对角线所在量子位或其他近邻量子位的状态1。消去下三角时,通过子结点将Steiner点置1;消去上三角时,通过父节点将Steiner点置1。经过Steiner点的路径有着最低的CNOT错误率,这意味着综合后的CNOT量子线路可以得到更优的可靠性。下面给出噪声感知的CNOT量子线路最近邻综合算法。以图4(c)矩阵所示的CNOT量子线路为例进行CNOT量子线路最近邻综合,综合过程如表3所示。可以看到,在考虑噪声因素的情况下,第1列的Steiner消除和不考虑噪声时的消除过程发生了改变。通过计算含噪声Steiner树的最小Steiner噪声路径长度,发现路径0,2,3的噪声代价低于路径0,3,尽管量子位0和量子位3近邻,但需选择噪声较低的路径,故选择路径0,2,3,此时量子位2为Steiner点。利用量子位3将量子位2置1,实现状态1的传递,对应矩阵的第3行异或到第2行;然后先用量子位3消去量子位4,对应矩阵的第3行异或到第4行;再用量子位2消去量子位3,对应矩阵的第2行异或到第3行;最后用量子位0消去量子位2,对应矩阵的第1行异或到第2行,直到第1列主对角线下方元素为0。处理第2列,通过算法找到最小Steiner噪声路径2,3,1,先用量子位3消去量子位1,再用量子位2消去量子位3,对应矩阵先把第3行异或算法1:噪声感知的CNOT量子线路Steiner消除综合算法(NASR)输入输入:输出输出:step1:step2:step3:step4:step5:step6:step7:任意CNOT量子线路对应的布尔矩阵matrix,当前架构名architecture近邻化综合中CNOT门的代价CNOT_gates获取矩阵的阶数N,给定当前循环变量 n=0,CNOT门代价数 CNOT_gates=0.若n0,设置Steiner消除方式为向上消除,标志位 upper 为false,获取第n列值为1的量子位,生成向上消除Steiner树,执行step3.输出CNOT_gates,并存储到CNOT_gates.csv文件中.算法结束.565量 子 电 子 学 报40 卷到第5行,再把第2行异或到第3行。处理第3列,最小Steiner噪声路径为3,4,用量子位3消去量子位4,对应矩阵的第3行异或到第4行。第4列和第5列不需要处理。下三角数据处理完成,原矩阵变为上三角矩阵。处理上三角时,只有第3列主对角线上存在不为0的元素,直接对第3列执行向上的Steiner消除,根据最小Steiner噪声路径3,2,只需要用量子位3消去量子位2即可。此时矩阵变成一个对角线元素为1的恒等矩阵,实现当前量子线路的最近邻综合,综合过程中需要的CNOT门数量称为CNOT量子线路综合代价。表3 CNOT量子线路最近邻综合过程Table 3 The nearest neighbor synthesis process of CNOT quantum circuits566第 4 期朱明强等:面向可靠性的CNOT量子线路最近邻综合3 实验结果与分析所提出方法使用Python语言实现,实验环境为macOS Big Sur(11.2.3)操作系统,Intel core i5 7267U3.1 GHZ双核处理,16 GB内存。本实验选取文献11中提供的5量子位随机CNOT量子线路,为提高实验规模,在已有线路的基础上又进行了门数的拓展,实验的量子线路对应的门级为2、4、5、8、10、15、20、30、40、80、100、200,每种量子门级有20条量子线路。文献 14 给出了一种考虑CNOT错误率插入SWAP门实现CNOT线路近邻的HA方法。在IBM Q的ibmq_5_yorktown架构上使用相同线路分别测试HA方法和本研究提出的方法,实验统计了12种门级下CNOT量子线路最近邻综合过程中噪声路径长度和最近邻CNOT门数,取20条线路的平均值作为每个门级的最终结果。噪声路径长度实验数据对比如表4所示,其中Size表示量子线路中的CNOT门数,Min noise path length为实验得到的噪声路径长度,HA为文献 14 方法得到的实验数据,NASR为本研究所提方法得到的实验数据,Reduction1表示NASR方法相对于HA方法减少的噪声路径长度、Imp1为噪声路径长度优化率。从表4可以看到,NASR方法较文献 14 的方法在减小噪声路径长度上有较大改进,对15个量子门以后的门级(包括15),噪声路径长度都得到了优化,门数越多优化效果越明显,200门级时优化率达到93.10%。实验数据表明,在超过15个门数的CNOT量子线路上,NASR方法以较低的错误率实现了CNOT量子线路的综合,这对提高量子线路的可靠性有很大意义。表4 噪声路径长度对比Table 4 Comparison of noise path lengthNO.123456789101112Size2458101520304080100200Min noise path lengthHA0.02960.05770.05910.09370.10970.18220.22460.32130.43390.92041.17932.3505NASR0.03700.06760.07860.12700.13480.15180.17490.14150.15930.14760.17520.1622Reduction10.00740.00980.01960.03330.02510.03040.04970.17980.27460.77271.00412.1883Imp1/%25.1117.0333.1035.6022.8816.6822.1155.9663.2983.9685.1493.10表5为量子线路综合需要的最近邻CONT门数对比结果,其中Adjacent CNOT gate counts为线路综合需要的最近邻CNOT门数,Reduction2表示NASR方法相对于HA方法减少的CNOT门数,Imp2为CNOT门数优化率。综合表4和表5的实验数据可以看到,与文献14方法相比,本研究所提NASR方法通过计算最小Steiner噪声路径长度,在量子线路综合时尽可能减小错误率,提高了量子线路运行结果的正确性,在保证线路可靠性的前提下,减少了量子线路综合时的CNOT门数量。12种门级中有7种实现了优化,平均优化率为27.7%。当CNOT量子线路的门数达到200时,优化率将近94%。图6为使用NASR方法与文献 14 的方法在同一体系结构上的相同CNOT量子线路实现近邻所需的CNOT门代价对比图。567量 子 电 子 学 报40 卷考虑到所提算法基于Steiner树的矩阵综合算法,与文献 14 中直接插入SWAP门以实现近邻的算法不同,在小规模门级时,利用Steiner树来实现最近邻综合的优势不明显,因此门级为2、4、5、6、10的线路综合结果与文献 14 接近,但随着门级的增大,优化效果越来越好,200门级时CNOT门优化率为93.79%。表5 相邻CNOT门计数对比Table 5 Comparison of adjacent CNOT gate countsNO.123456789101112Size2458101520304080100200Adjacent CNOT gate countsHA1.653.153.34.655.79.311.716.823.150.2564.8130.35NASR1.93.354.056.256.87.78.757.158.17.258.958.1Reduction20.250.200.751.601.101.602.959.6515.0043.0055.85122.25Imp2/%15.156.3522.7334.4119.3017.2025.2157.4464.9485.5786.1993.79图6 CNOT门代价对比Fig.6 Comparison of CNOT gate cost4 结 论基于以CNOT错误率为权重的二维拓扑图,提出了一种噪声感知的CNOT量子线路最近邻综合方法。对任意给定的非近邻CNOT量子线路,在对应的二维拓扑图上通过Floyd算法找到噪声路径长度最小的Steiner树,获取最小Steiner噪声路径,以较小的CNOT门代价得到满足最近邻约束的等价CNOT量子线路。门数代价的降低,可以在相同噪声的NISQ架构上得到更高正确率的等价近邻线路,优化真实量子计算机的计算能力。所提算法能够在确保线路可靠性的前提下,减少CNOT线路最近邻综合过程中使用的CNOT门568第 4 期朱明强等:面向可靠性的CNOT量子线路最近邻综合数,提高线路的正确性。未来将进一步将算法适配到更多的实际体系结构中,同时优化初始映射以及综合算法,以提高面向实际物理约束的CNOT线路综合的性能。参考文献参考文献:1Preskill J.Quantum computing in the NISQ era and beyond J.Quantum,2018,2:79.2Shor P W.Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer J.SIAM Journal on Computing,1997,26(5):1484-1509.3Grover L K.A fast quantum mechanical algorithm for database search C.Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing,1996:212-219.4Peruzzo A,McClean J,Shadbolt P,et al.A variational eigenvalue solver on a photonic quantum processor J.Nature Communications,2014,5(1):4213.5Zhu G,Cross A.Hardware-aware approach for fault-tolerant quantum computation OL.https:/ J.CES 2018:Intels 49-qubit chip shoots for quantum supremacy OL.https:/spectrum.ieee.org/techtalk/computing/hardware/intels-49qubit-chip-aims-for-quantum-supremacy.7Reagor M,Osborn C B,Tezak N,et al.Demonstration of universal parametric entangling gates on a multi-qubit lattice J.Science Advances,2018,4(2):eaao3603.8Ballance C J,Harty T P,Linke N M,et al.High-fidelity quantum logic gates using trapped-ion hyperfine qubits J.Physical Review Letters,2016,117(6):060504.9Cheng X Y,Guan Z J,Ding W P,et al.Linear nearest neighbor quantum circuit synthesis based on valid Boolean matrix J.Chinese Journal of Quantum Electronics,2016,33(6):743-750.程学云,管致锦,丁卫平,等.基于有效布尔矩阵的线性最近邻量子电路综合 J.量子电子学报,2016,33(6):743-750.10Patel K N,Markov I L,Hayes J P.Optimal synthesis of linear reversible circuits J.Quantum Information and Computation,2008,8(3&4):282-294.11Kissinger A,de Griend A M.CNOT circuit extraction for topologically-constrained quantum memoriesJ.Quantum Information and Computation,2020,20:581-596.12Zhu P C,Cheng X Y,Guan Z J.An exact qubit allocation approach for NISQ architectures J.Quantum Information Processing,2020,19(11):391.13Zulehner A,Paler A,Wille R.An efficient methodology for mapping quantum circuits to the IBM QX architectures J.IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2018,38(7):1226-1236.14Niu S Y,Suau A,Staffelbach G,et al.A hardware-aware heuristic for the qubit mapping problem in the NISQ era J.IEEE Transactions on Quantum Engineering,2020,1:1-14.15Schaeffer B,Perkowski M.Linear reversible circuit synthesis in the linear nearest-neighbor model C.2012 IEEE 42nd International Symposium on Multiple-Valued Logic,2012:157-160.569