CN115829047A - 量子程序最终映射的确定方法、装置及量子计算机 - Google Patents

Abstract

本发明公开了一种量子程序最终映射的确定方法、装置及量子计算机，方法包括：获取量子程序的有向无环图，根据量子程序的有向无环图，确定量子程序的最大子图集合及最大子图对应的同构子图集合，分别确定同构子图集合中每个同构子图映射到量子芯片拓扑结构的成本，根据每个同构子图映射到量子芯片拓扑结构的成本，确定待执行量子程序的最终映射，以使最终映射的成本最低，既解决因单个物理比特因素对整个量子线路产生影响的问题，也可以确定量子芯片拓扑结构的最终映射线路，使得整个量子芯片的资源利用最大化。

Description

量子程序最终映射的确定方法、装置及量子计算机

技术领域

本发明属于量子计算技术领域，特别是一种量子程序最终映射的确定方法、装置及量子计算机。

背景技术

量子计算机是一类遵循量子力学规律进行高速数学和逻辑运算、存储及处理量子信息的物理装置。当某个装置处理和计算的是量子信息，运行的是量子算法时，它就是量子计算机。量子计算机因其具有相对普通计算机更高效的处理数学问题的能力，例如，能将破解RSA密钥的时间从数百年加速到数小时，故成为一种正在研究中的关键技术。

在嘈杂中型量子计算(Noisy Intermediate-Scale Quantum)阶段，对于同一块物理芯片上的多个物理比特，其各个物理比特的状态是不稳定的，例如两比特量子逻辑门操作噪声、测量噪声以及物理比特的退相干时间等因素，均会对物理比特的有效利用造成干扰，从而对整个量子线路的运行结果产生未知影响。

例如，由于各个物理比特的退相干时间不同，若是因为某个物理比特退相干时间短而限制了整个量子芯片可运行的量子线路深度，必然导致其他物理比特资源的浪费。因此如何确定待执行量子程序的最终映射线路，从而减少单个物理比特对整个量子线路的影响，并且使得整个量子芯片的资源利用最大化是一个亟需解决的问题。

发明内容

本发明的目的是提供一种量子程序最终映射的确定方法、装置及量子计算机，以解决现有技术中的不足，它能够解决因单个物理比特因素对整个量子线路产生影响的问题，并且可以确定量子程序的最终映射线路，使得整个量子芯片的资源利用最大化。

本申请的一个实施例提供了一种量子程序最终映射的确定方法，所述方法包括：

获取待执行量子程序的有向无环图；

根据所述待执行量子程序的有向无环图，确定所述待执行量子程序的最大子图集合及最大子图对应的同构子图集合，其中，所述同构子图集合是所述最大子图根据量子芯片的拓扑结构得到的逻辑比特-物理比特初始映射关系图集合；

分别确定所述同构子图集合中每个同构子图映射到所述量子芯片拓扑结构的成本；

根据所述每个同构子图映射到所述量子芯片拓扑结构的成本，确定所述待执行量子程序的最终映射，以使所述最终映射的成本最低。

可选的，所述获取待执行量子程序的有向无环图，包括：

获取待执行量子程序中的节点；

根据所述节点操作的量子比特，确定所述节点之间的关联关系；

根据所述节点及节点之间的关联关系，生成与所述待执行量子程序对应的有向无环图，其中，所述有向无环图中的顶点表征节点，所述有向无环图中的边表征节点之间的关联关系，所述边的方向表征该边相连的顶点对应的节点被执行的时序关系。

可选的，所述根据所述待执行量子程序的有向无环图，确定所述待执行量子程序的最大子图集合及最大子图对应的同构子图集合，包括：

遍历所述待执行量子程序的有向无环图得到最大子图集合，所述最大子图集合包括N个最大子图，N为大于或等于1的整数；

确定所述N个最大子图在量子芯片的拓扑结构中的同构子图，得到N个同构子图集合，所述N个同构子图集合与所述N个最大子图一一对应。

可选的，所述遍历所述待执行量子程序的有向无环图得到最大子图集合，包括：

根据所述有向无环图中入度为零的第一节点，生成第一子图；

删除所述第一节点得到新的有向无环图；

确定所述新的有向无环图中是否存在入度为零的第二节点；

若所述新的有向无环图中不存在所述第二节点，则将所述第一子图确定为一个最大子图。

可选的，所述方法还包括：

若所述新的有向无环图中存在所述第二节点，则确定所述第二节点与所述第一节点的邻接关系；

基于所述邻接关系和所述第一节点，生成一个最大子图。

可选的，所述基于所述邻接关系和所述第一节点，生成一个最大子图，包括：

基于所述第二节点与所述第一节点的邻接关系，将所述第一子图拓展为第二子图，并将所述第二子图作为新的第一子图；

获取删除所述第二节点后的新有向无环图，继续执行所述确定所述新的有向无环图中是否存在入度为零的第二节点的步骤。

可选的，所述分别确定所述同构子图集合中每个同构子图映射到所述量子芯片拓扑结构的成本，包括：

根据所述最大子图集合及最大子图对应的同构子图集合，分别获取每个同构子图映射到所述量子芯片拓扑结构的映射方式；

构建评估所述映射方式的成本公式并计算映射方式的成本。

可选的，所述评估所述映射方式的成本公式为：

其中，T₂为量子芯片比特的退相干时间，G_swap为最终映射方式所需要引入的SWAP门个数，f_double为两比特量子逻辑门保真度，f_measure为测量保真度，a₁、a₂、a₃、a₄为成本公式的预设权重系数。

本申请的一个实施例提供了一种量子程序最终映射的确定装置，所述装置包括：

获取模块，用于获取待执行量子程序的有向无环图；

第一确定模块，用于根据所述待执行量子程序的有向无环图，确定所述待执行量子程序的最大子图集合及最大子图对应的同构子图集合，其中，所述同构子图集合是所述最大子图根据量子芯片的拓扑结构得到的逻辑比特-物理比特初始映射关系图集合；

第二确定模块，用于分别确定所述同构子图集合中每个同构子图映射到所述量子芯片拓扑结构的成本；

第三确定模块，用于根据所述每个同构子图映射到所述量子芯片拓扑结构的成本，确定所述待执行量子程序的最终映射，以使所述最终映射的成本最低。

可选的，所述获取模块，包括：

获取单元，用于获取待执行量子程序中的节点；

确定单元，用于根据所述节点操作的量子比特，确定所述节点之间的关联关系；

生成单元，用于根据所述节点及节点之间的关联关系，生成与所述待执行量子程序对应的有向无环图，其中，所述有向无环图中的顶点表征节点，所述有向无环图中的边表征节点之间的关联关系，所述边的方向表征该边相连的顶点对应的节点被执行的时序关系。

可选的，所述第一确定模块，包括：

遍历单元，用于遍历所述待执行量子程序的有向无环图得到最大子图集合，所述最大子图集合包括N个最大子图，N为大于或等于1的整数；

得到单元，用于确定所述N个最大子图在量子芯片的拓扑结构中的同构子图，得到N个同构子图集合，所述N个同构子图集合与所述N个最大子图一一对应。

可选的，所述遍历单元，包括：

子图单元，用于根据所述有向无环图中入度为零的第一节点，生成第一子图；

删除单元，用于删除所述第一节点得到新的有向无环图；

判断单元，用于确定所述新的有向无环图中是否存在入度为零的第二节点；

第一子图确定单元，用于若所述新的有向无环图中不存在所述第二节点，则将所述第一子图确定为一个最大子图。

可选的，所述装置还包括：

第二子图确定单元，用于若所述新的有向无环图中存在所述第二节点，则确定所述第二节点与所述第一节点的邻接关系；

最大子图生成单元，用于基于所述邻接关系和所述第一节点，生成一个最大子图。

可选的，所述最大子图生成单元，包括：

拓展单元，用于基于所述第二节点与所述第一节点的邻接关系，将所述第一子图拓展为第二子图，并将所述第二子图作为新的第一子图；

继续执行单元，用于获取删除所述第二节点后的新有向无环图，继续执行所述确定所述新的有向无环图中是否存在入度为零的第二节点的步骤。

可选的，所述第二确定模块，包括：

映射单元，用于根据所述最大子图集合及最大子图对应的同构子图集合，分别获取每个同构子图映射到所述量子芯片拓扑结构的映射方式；

构建单元，用于构建评估所述映射方式的成本公式并计算映射方式的成本。

本申请的又一实施例提供了一种存储介质，所述存储介质中存储有计算机程序，其中，所述计算机程序被设置为运行时执行上述任一项中所述的方法。

本申请的又一实施例提供了一种电子装置，包括存储器和处理器，所述存储器中存储有计算机程序，所述处理器被设置为运行所述计算机程序以执行上述任一项中所述的方法。

本申请的又一实施例提供了一种量子计算机操作系统，所述量子计算机操作系统根据上述任一项中所述方法实现量子程序最终映射的确定。

本申请的又一实施例提供了一种量子计算机，所述量子计算机包括所述的量子计算机操作系统。

与现有技术相比，本申请首先获取量子程序的有向无环图，根据量子程序的有向无环图，确定量子程序的最大子图集合及最大子图对应的同构子图集合，分别确定同构子图集合中每个同构子图映射到量子芯片拓扑结构的成本，根据每个同构子图映射到量子芯片拓扑结构的成本，确定待执行量子程序的最终映射，以使最终映射的成本最低，既解决因单个物理比特因素对整个量子线路产生影响的问题，也可以确定量子芯片拓扑结构的最终映射线路，使得整个量子芯片的资源利用最大化。

附图说明

图1为本发明实施例提供的一种量子程序最终映射的确定方法的计算机终端的硬件结构框图；

图2为本发明实施例提供的一种量子程序最终映射的确定方法的流程示意图；

图3为本发明实施例提供的一种待执行量子线路示意图；

图4为本发明实施例提供的一种待执行量子线路对应有向无环图的示意图；

图5为本发明实施例提供的一种量子芯片物理比特的拓扑结构示意图；

图6为本发明实施例提供的基于图4所示的有向无环图中的第一节点确定的第一子图的示意图；

图7为本发明实施例提供的图4删除第一节点后得到的新的有向无环图的示意图；

图8为本发明实施例提供的基于第二节点在图6上进行拓展得到的第二子图的示意图；

图9为本发明实施例提供的图7删除第二节点后得到的新的有向无环图的示意图；

图10为本发明实施例提供的基于第二节点在图8上进行拓展得到的新的第二子图的示意图；

图11为本发明实施例提供的基于图9删除一个第二节点后得到新的有向无环图的示意图；

图12为本发明实施例提供的基于图11所示的有向无环图中的第二节点确定的第二子图的示意图；

图13为本发明实施例提供的基于图11删除第二节点后得到的新的有向无环图的示意图；

图14为本发明实施例提供的基于图12所示的有向无环图中的第二节点确定的第二子图的示意图；

图15为本发明实施例提供的基于图13删除第二节点后得到的新的有向无环图的示意图；

图16为本发明实施例提供的基于图15所示的新的有向无环图中的第一节点确定的第一子图的示意图；

图17为本发明实施例提供的一种量子程序最终映射的确定装置的结构示意图。

具体实施方式

下面通过参考附图描述的实施例是示例性的，仅用于解释本发明，而不能解释为对本发明的限制。

本发明实施例首先提供了一种量子程序最终映射的确定方法，该方法可以应用于电子设备，如计算机终端，具体如普通电脑、量子计算机等。

下面以运行在计算机终端上为例对其进行详细说明。图1为本发明实施例提供的一种量子程序最终映射的确定方法的计算机终端的硬件结构框图。如图1所示，计算机终端可以包括一个或多个(图1中仅示出一个)处理器102(处理器102可以包括但不限于微处理器MCU或可编程逻辑器件FPGA等的处理装置)和用于存储数据的存储器104，可选地，上述计算机终端还可以包括用于通信功能的传输装置106以及输入输出设备108。本领域普通技术人员可以理解，图1所示的结构仅为示意，其并不对上述计算机终端的结构造成限定。例如，计算机终端还可包括比图1中所示更多或者更少的组件，或者具有与图1所示不同的配置。

存储器104可用于存储应用软件的软件程序以及模块，如本申请实施例中的实现一种量子程序最终映射的确定方法对应的程序指令/模块，处理器102通过运行存储在存储器104内的软件程序以及模块，从而执行各种功能应用以及数据处理，即实现上述的方法。存储器104可包括高速随机存储器，还可包括非易失性存储器，如一个或者多个磁性存储装置、闪存、或者其他非易失性固态存储器。在一些实例中，存储器104可进一步包括相对于处理器102远程设置的存储器，这些远程存储器可以通过网络连接至计算机终端。上述网络的实例包括但不限于互联网、企业内部网、局域网、移动通信网及其组合。

传输装置106用于经由一个网络接收或者发送数据。上述的网络具体实例可包括计算机终端的通信供应商提供的无线网络。在一个实例中，传输装置106包括一个网络适配器(Network Interface Controller，NIC)，其可通过基站与其他网络设备相连从而可与互联网进行通讯。在一个实例中，传输装置106可以为射频(Radio Frequency，RF)模块，其用于通过无线方式与互联网进行通讯。

需要说明的是，真正的量子计算机是混合结构的，它包含两大部分：一部分是经典计算机，负责执行经典计算与控制；另一部分是量子设备，负责运行量子程序进而实现量子计算。而量子程序是由量子语言如QRunes语言编写的一串能够在量子计算机上运行的指令序列，实现了对量子逻辑门操作的支持，并最终实现量子计算。具体的说，量子程序就是一系列按照一定时序操作量子逻辑门的指令序列。

在实际应用中，因受限于量子设备硬件的发展，通常需要进行量子计算模拟以验证量子算法、量子应用等等。量子计算模拟即借助普通计算机的资源搭建的虚拟架构(即量子虚拟机)实现特定问题对应的量子程序的模拟运行的过程。通常，需要构建特定问题对应的量子程序。本发明实施例所指量子程序，即是经典语言编写的表征量子比特及其演化的程序，其中与量子计算相关的量子比特、量子逻辑门等等均有相应的经典代码表示。

量子线路作为量子程序的一种体现方式，也称量子逻辑电路，是最常用的通用量子计算模型，表示在抽象概念下对于量子比特进行操作的线路，其组成包括量子比特、线路(时间线)，以及各种量子逻辑门，最后常需要通过量子测量操作将结果读取出来。

不同于传统电路是用金属线所连接以传递电压信号或电流信号，在量子线路中，线路可看成是由时间所连接，亦即量子比特的状态随着时间自然演化，在这过程中按照哈密顿运算符的指示，一直到遇上逻辑门而被操作。

一个量子程序整体上对应有一条总的量子线路，本发明所述量子程序即指该条总的量子线路，其中，该总的量子线路中的量子比特总数与量子程序的量子比特总数相同。可以理解为：一个量子程序可以由量子线路、针对量子线路中量子比特的测量操作、保存测量结果的寄存器及控制流节点(跳转指令)组成，一条量子线路可以包含几十上百个甚至千上万个量子逻辑门操作。量子程序的执行过程，就是对所有的量子逻辑门按照一定时序执行的过程。需要说明的是，时序即单个量子逻辑门被执行的时间顺序。

需要说明的是，经典计算中，最基本的单元是比特，而最基本的控制模式是逻辑门，可以通过逻辑门的组合来达到控制电路的目的。类似地，处理量子比特的方式就是量子逻辑门。使用量子逻辑门，能够使量子态发生演化，量子逻辑门是构成量子线路的基础，量子逻辑门包括单比特量子逻辑门，如Hadamard门(H门，哈德玛门)、泡利-X门(X门)、泡利-Y门(Y门)、泡利-Z门(Z门)、RX门、RY门、RZ门等等；多比特量子逻辑门，如CNOT门、CR门、iSWAP门、Toffoli门等等。量子逻辑门一般使用酉矩阵表示，而酉矩阵不仅是矩阵形式，也是一种操作和变换。一般量子逻辑门在量子态上的作用是通过酉矩阵左乘以量子态右矢对应的矩阵进行计算的。

量子态，即量子比特的逻辑状态，在量子算法(或称量子程序)中用二进制表示，例如，一组量子比特为q0、q1、q2，表示第0位、第1位、第2位量子比特，从高位到低位排序为q2q1q0，该组量子比特对应的量子态是该组量子比特对应的本征态的叠加，该组量子比特对应的本征态共有2的量子比特总数次方个，即8个本征态(确定的状态)：|000>、|001>、|010>、|011>、|100>、|101>、|110>、|111>，每个本征态的位与量子比特对应一致，如|000>态，000从高位到低位对应q2q1q0，|>为狄拉克符号。

以单个量子比特说明，单个量子比特的逻辑状态

可能处于|0>态、|1>态、|0>态和|1>态的叠加态(不确定状态)，具体可以表示为

其中，c和d为表示量子态振幅(概率幅)的复数,振幅的平方c²和d²分别表示|0>态、|1>态的概率，|c|²+|d|²＝1。简言之，量子态是各本征态组成的叠加态，当其它本征态的概率为0时，即处于唯一确定的本征态。

参见图2，图2为本发明实施例提供的一种量子程序最终映射的确定方法的流程示意图。

本实施例提供一种量子程序最终映射的确定方法的一实施例，所述量子程序最终映射的确定方法包括：

S201：获取待执行量子程序的有向无环图。

具体的，待执行量子程序主要由几十上百个甚至千上万个量子逻辑门组成。量子程序的执行过程，就是对所有的量子逻辑门按照一定时序执行的过程，需要说明的是，时序即单个量子逻辑门被执行的时间顺序。

有向无环图(DAG图)是有向图的一种，字面意思的理解就是图中没有环，是一个无回路的有向图，如果有一个非有向无环图，从A点出发向B经过C可以回到A点，则形成一个环。若将从C点到A点的方向改为从A点到C点则变成有向无环图，其常被用来表示事件间的驱动依赖关系、任务之间的调度等。

获取待执行量子程序的有向无环图，具体包括如下步骤：

S2011：获取待执行量子程序中的节点。

具体的，量子程序可以理解为一个操作序列，其中主要包含量子逻辑门、测量操作(Measure)等。所谓量子程序中的节点，是指在整个程序的相对位置的一特定结构的数据，可以是量子逻辑门、测量操作(Measure)等，本申请中主要考虑量子逻辑门节点。

具体的，可以通过遍历量子程序的节点，得到量子程序中量子逻辑门节点。

示例性的，参见图3，图3为本发明实施例提供的一种待执行量子线路示意图，其中，黑色实心圆点代表CNOT量子逻辑门的控制比特，实心黑色圆圈中“+”代表CNOT量子逻辑门的目标比特，可以理解的是，一段量子程序整体上对应有一条总的量子线路，本发明实施例所述待执行量子程序即指该条总的量子线路。其中，待执行量子程序为CNOT(q[0]，q[1])<<CNOT(q[0]，q[2])<<CNOT(q[0]，q[3])<<CNOT(q[1]，q[2])<<CNOT(q[1]，q[3])<<CNOT(q[2]，q[3])，则从CNOT(q[0]，q[1])开始遍历，获取待执行量子程序中的节点1至节点6分别为CNOT(q[0]，q[1])、CNOT(q[0]，q[2])、CNOT(q[0]，q[3])、CNOT(q[1]，q[2])、CNOT(q[1]，q[3])、CNOT(q[2]，q[3])。

S2012：根据所述节点操作的量子比特，确定所述节点之间的关联关系。

具体的，针对每一所述量子操作节点，从该节点操作的量子比特依序执行的所有量子操作节点中，确定该节点的下一节点，得到该节点与下一节点之间的相邻关系。

具体的，在遍历量子线路的节点过程中，记录当前遍历到的节点操作的量子比特序号和唯一标识符，以更新遍历过程中每个比特对应的最后一个节点。并且记录每个比特对应的最后一个节点及当前遍历到的节点的信息和最后一个节点与当前遍历到的节点之间的相邻关系。其中，量子比特对应的最后一个节点是指当前遍历到的量子逻辑门节点的前驱节点。

需要说明的是，量子逻辑门的唯一标识符按照量子逻辑门的执行时序进行标记。

示例性的，如图3所示的一种待执行量子线路示意图，首先，按照节点操作的量子比特依序遍历量子程序的节点。从量子线路的第一层开始，遍历CNOT(q[0]，q[1])，CNOT门操作的量子比特序号为0和1，其唯一标识符为“1”，且当前第一层CNOT门均没有前驱节点。

当遍历至量子线路第二层的起始，即遍历至节点CNOT(q[0]，q[2])时，CNOT门操作的量子比特序号为0和2，唯一标识符为2，此时CNOT(q[0]，q[2])的前驱节点为CNOT(q[0]，q[1])，记录比特之间的相邻关系，以唯一标识符的形式记录，可记为{1,2}，表示节点1和节点2相邻。然后，依序遍历到第三层的CNOT(q[0]，q[3])、第四层的CNOT(q[1]，q[2])、第五层的CNOT(q[1]，q[3])、第六层的CNOT(q[2]，q[3])，获取每一层节点操作的量子比特，确定节点之间的关联关系，处理流程同理，在此不再赘述。

S2013：根据所述节点及节点之间的关联关系，生成与所述待执行量子程序对应的有向无环图，其中，所述有向无环图中的顶点表征节点，所述有向无环图中的边表征节点之间的关联关系，所述边的方向表征该边相连的顶点对应的节点被执行的时序关系。

参见图4，图4为本发明实施例提供的一种待执行量子线路对应有向无环图的示意图。具体的，通过构建与量子操作节点对应的顶点并构建具有相邻关系的节点对应的顶点之间的边，其中，边的方向由具有相邻关系的节点中的前一节点对应的顶点指向下一节点对应的顶点，再根据节点及节点之间的关联关系，生成与待执行量子程序对应的有向无环图。

S202：根据所述待执行量子程序的有向无环图，确定所述待执行量子程序的最大子图集合及最大子图对应的同构子图集合，其中，所述同构子图集合是所述最大子图根据量子芯片的拓扑结构得到的逻辑比特-物理比特初始映射关系图集合。

为了便于区分，一般将量子芯片中的量子比特结构称为物理比特，量子线路中操作的对象比特称为逻辑比特。逻辑比特与物理比特的初始映射关系，指逻辑比特与物理比特之间比特相互“对应”的关系。

示例性的，参见图5，图5为本发明实施例提供的一种量子芯片物理比特的拓扑结构示意图,该量子芯片中包括8个物理比特，分别为Q[0]、Q[1]、Q[2]、Q[3]、Q[4]、Q[5]、Q[6]、Q[7]，这8个物理比特可通过电容耦合，且只有相邻的物理比特之间才具有耦合关系。其中，Q[0]与Q[1]及Q[4]连接，Q[5]与Q[1]、Q[4]及Q[6]连接，Q[2]与Q[1]、Q[6]及Q[3]连接，Q[7]与Q[3]及Q[6]连接。

示例性的，针对一段量子程序CNOT(q[0]，q[1])<<CNOT(q[0]，q[2])<<CNOT(q[0]，q[3])<<CNOT(q[1]，q[2])<<CNOT(q[1]，q[3])<<CNOT(q[2]，q[3])，其操作的逻辑比特分别为q[0]、q[1]、q[2]，q[3]，则逻辑比特与物理比特的初始映射关系可设置为q[0]对应Q[0]、q[1]对应Q[1]、q[2]对应Q[2]，q[3]对应Q[3]等多种初始映射关系。

具体的，根据所述待执行量子程序的有向无环图，确定所述待执行量子程序的最大子图集合及最大子图对应的同构子图集合，包括以下步骤：

步骤S2021：遍历所述待执行量子程序的有向无环图得到最大子图集合，所述最大子图集合包括N个最大子图，N为大于或等于1的整数。

具体的，N个最大子图按照各自得到的顺序依次排列，得到最大子图集合，包括：

1.根据所述有向无环图中入度为零的第一节点，生成第一子图。

具体的，入度是图论算法中重要的概念之一，它通常指有向图中某点作为图中边的终点的次数之和。

示例性的，如图4所提供的一种待执行量子线路对应有向无环图的示意图，其中，入度为零的第一节点为CNOT(q[0]，q[1])，生成如图6所示的第一子图，如图6所示，对于CNOT(q[0]，q[1])对应的节点，包括两个点和一条边，其中两点指q[0]对应的点和q[1]对应的点，一条边指q[0]对应的点和q[1]对应的点之间的边。q[0]对应的点表示逻辑量子比特q[0]，q[1]对应的点表示逻辑量子比特q[1]，q[0]对应的点和q[1]对应的点之间的边可表示作用在逻辑量子比特q[0]和逻辑量子比特q[1]上的CNOT门。

2.删除所述第一节点得到新的有向无环图。

示例性的，接上述示例，删除入度为零的第一节点CNOT(q[0]，q[1])，生成如图7所示的新的有向无环图。

3.确定所述新的有向无环图中是否存在入度为零的第二节点。

具体的，参照确定第一节点的方法，判断新的有向无环图中是否存在入度为零的第二节点。若所述新的有向无环图中存在所述第二节点，则确定所述第二节点与所述第一节点的邻接关系，基于所述邻接关系和所述第一节点，生成一个最大子图。

所述基于所述邻接关系和所述第一节点，生成一个最大子图，包括：

基于所述第二节点与所述第一节点的邻接关系，将所述第一子图拓展为第二子图，并将所述第二子图作为新的第一子图。

示例性的，根据如图7所示的新的有向无环图，存在入度为零的第二节点CNOT(q[0]，q[2])，确定所述第二节点与所述第一节点CNOT(q[0]，q[1])的邻接关系。需要说明的是，节点间的有向边用于表示量子逻辑门按逻辑量子比特的量子态演化时序的邻接关系，并基于所述邻接关系和所述第一节点，生成一个如图8所示的将第一子图拓展为第二子图的示意图。

获取删除所述第二节点后的新有向无环图，继续执行所述确定所述新的有向无环图中是否存在入度为零的第二节点的步骤。

示例性的，接上述示例，获取删除所述第二节点后的新有向无环图，生成如图9所示的另一个新的有向无环图，继续执行上述步骤3，确定另一新的有向无环图中是否存在入度为零的第二节点。

4.若所述新的有向无环图中不存在所述第二节点，则将所述第一子图确定为一个最大子图。

具体的，若新的有向无环图中不存在第二节点，则说明完成了整个待执行量子程序的遍历，可将所述第一子图确定为一个最大子图。

需要说明的是，若新的有向无环图中存在入度为零的第二节点，则存在两种情况：一种是可以基于第二节点继续拓展子图，从而得到相较于先前更大的子图；另一种是不可以基于第二节点继续拓展子图，那么当前的子图即为最大子图。

步骤S2022：确定所述N个最大子图在量子芯片的拓扑结构中的同构子图，得到N个同构子图集合，所述N个同构子图集合与所述N个最大子图一一对应。

具体的，同构子图是最大子图基于电子设备中量子芯片的拓扑结构映射得到的在量子芯片上的比特关系图。例如，假设最大子图为“q[0]—q[1]”，电子设备中量子芯片的拓扑结构为链式的“Q[0]—Q[1]—Q[2]—Q[3]”，则可以将“q[0]—q[1]”映射到“Q[0]—Q[1]”，也可以映射到“Q[1]—Q[2]”，还可以映射到“Q[2]—Q[3]”，那么最大子图“q[0]—q[1]”的同构子图为：“Q[0]—Q[1]”、“Q[1]—Q[2]”、“Q[2]—Q[3]”。

下面为本申请实施例提供的最大子图集合确定方法的一具体应用示例。

示例性的，针对如图3所示的一段量子程序CNOT(q[0]，q[1])<<CNOT(q[0]，q[2])<<CNOT(q[0]，q[3])<<CNOT(q[1]，q[2])<<CNOT(q[1]，q[3])<<CNOT(q[2]，q[3])，该段量子程序对应的有向无环图为图4所示。

根据图4所示的有向无环图确定最大子图集合的步骤如下：

首先确定入度为零的第一节点为CNOT(q[0]，q[1])，如图6所示，图6为基于图4所示的有向无环图中的第一节点确定的第一子图的示意图；删除入度为零的第一节点CNOT(q[0]，q[1])，如图7所示，图7为图4删除第一节点后得到的新的有向无环图的示意图；根据如图7所示的新的有向无环图，存在入度为零的第二节点CNOT(q[0]，q[2])，确定所述第二节点与所述第一节点CNOT(q[0]，q[1])的邻接关系，并基于所述邻接关系和所述第一节点，生成如图8所示的示意图，图8为基于第二节点在图6上进行拓展得到的第二子图的示意图；获取删除所述第二节点后的新有向无环图，如图9所示，图9为图7删除第二节点后得到的新的有向无环图的示意图，存在入度为零的第二节点CNOT(q[0]，q[3])和CNOT(q[1]，q[2])，因此这里存在两个第二节点。确定CNOT(q[0]，q[3])对应的节点和CNOT(q[1]，q[2])对应的节点的执行优先级，由于CNOT(q[0]，q[3])对应的节点中的一个点在第二子图(如图8所示)中，而CNOT(q[1]，q[2])对应的节点中的两个点均在第二子图中，但两个点间的边却不在第二子图中，因此CNOT(q[1]，q[2])的执行优先级低于CNOT(q[0]，q[3])的执行优先级。先执行CNOT(q[0]，q[3])对应的节点，即以q[0]对应的点作边，将第二子图拓展为如图10所示，图10为基于第二节点在图8上进行拓展得到的新的第二子图的示意图；再执行CNOT(q[1]，q[2])对应的节点，虽然该节点中的两个点均在新的第二子图中但两个点间的边却不在新的第一子图中，则将上述得到的如图10所示的新的第二子图确定为一个最大子图。

获取删除第二节点CNOT(q[0]，q[3])后的新有向无环图，生成如图11所示的基于图9删除一个第二节点后得到新的有向无环图的示意图，存在入度为零的第二节点CNOT(q[1]，q[2])，如图12所示，图12为基于图11所示的有向无环图中的第二节点确定的第二子图的示意图；删除入度为零的第二节点CNOT(q[1]，q[2])，如图13所示，图13为基于图11删除第二节点后得到的新的有向无环图的示意图，根据如图13所示的新的有向无环图，存在入度为零的第二节点CNOT(q[1]，q[3])，如图14所示，图14为基于图12所示的有向无环图中的第二节点确定的第二子图的示意图；删除入度为零的第二节点CNOT(q[1]，q[3])，如图15所示，图15为基于图13删除第二节点后得到的新的有向无环图的示意图，然后确定该新的有向无环图中是否存在第二节点，由于CNOT(q[2]，q[3])对应的节点的入度为0，因此CNOT(q[2]，q[3])对应的节点为第二节点，CNOT(q[2]，q[3])对应的节点中的两个点均在第二子图(图14)中但两个点间的边却不在第二子图中，则将上述得到的如图14所示的第二子图确定为一个最大子图。

将CNOT(q[2]，q[3])对应的节点作为新的第一节点，将第一节点包括两个点(q[2]对应的点和q[3]对应的点)作为第一子图中的两个端点，将第一节点包括的边作为第一子图的边得到第一子图，如图16所示，图16为基于图15所示的新的有向无环图中的第一节点确定的第一子图的示意图。删除CNOT(q[2]，q[3])对应的节点，得到的新的有向无环图为空，此时遍历完成，将第一子图确定为一个最大子图。

综上，根据如图3所示的一段待执行量子程序可以得到三个最大子图：分别为CNOT(q[0]，q[1])<<CNOT(q[0]，q[2])<<CNOT(q[0]，q[3])构成的最大子图(如图10所示)；CNOT(q[1]，q[2])<<CNOT(q[1]，q[3])构成的最大子图(如图14所示)；CNOT(q[2]，q[3])构成的最大子图(如图16所示)，将三个最大子图按照得到的获取顺序依次排列即可得到最大子图集合。

S203：分别确定所述同构子图集合中每个同构子图映射到所述量子芯片拓扑结构的成本。

具体的，可以根据所述最大子图集合及最大子图对应的同构子图集合，分别获取每个同构子图映射到所述量子芯片拓扑结构的映射方式。

示例性的，参见图5，该量子芯片中包括8个物理比特，分别为Q[0]、Q[1]、Q[2]、Q[3]、Q[4]、Q[5]、Q[6]、Q[7]，其中，Q[0]与Q[1]及Q[4]连接，Q[5]与Q[1]、Q[4]及Q[6]连接，Q[2]与Q[1]、Q[6]及Q[3]连接，Q[7]与Q[3]及Q[6]连接。

将上述获取的第一个最大子图(图10)在图5所示的量子芯片中进行映射，可以得到24个第一同构子图，该24个第一同构子图组成第一个同构子图映射方式集合；将上述获取的第二个最大子图(图14)在图5所示的量子芯片中进行映射，可以得到32个第二同构子图，该32个第二同构子图组成第二个同构子图映射方式集合；将上述获取的第三个最大子图(图16)在图5所示的量子芯片中进行映射，可以得到20个第三同构子图，该20个第三同构子图组成第三个同构子图映射方式集合，每个第一同构子图映射方式、每个第二同构子图映射方式、每个第三同构子图映射方式的具体形式，在此不一一列举。

分别确定上述第一个同构子图映射方式集合、第二个同构子图映射方式集合、第三个同构子图映射方式集合中每个同构子图映射到所述量子芯片拓扑结构的成本。

构建评估所述映射方案的成本公式并计算映射方式的成本。

其中，所述评估所述映射方案的成本公式为：

其中，T₂为量子芯片比特的退相干时间，G_swap为最终映射方式所需要引入的SWAP门个数，f_double为两比特量子逻辑门保真度，f_measure为测量保真度，a₁、a₂、a₃、a₄为成本公式的预设权重系数。

需要说明的是，通过上述成本公式评估各个映射方式的成本，综合考虑了最短路径、两比特量子逻辑门保真度、测量保真度和退相干时间等多方面因素，然后依次加权求和分别得到每个同构子图映射到所述量子芯片拓扑结构的消耗成本，在每个同构子图映射方式集合中选择消耗成本最小的同构子图映射方式，然后继续寻找下一个同构子图集合中映射到量子芯片拓扑结构的消耗成本，直至整个待执行量子线路中的所有逻辑门都映射到量子芯片拓扑结构的物理比特上。

S204：根据所述每个同构子图映射到所述量子芯片拓扑结构的成本，确定所述待执行量子程序的最终映射，以使所述最终映射的成本最低。

示例性的，上述第一个同构子图映射方式集合包括24个第一同构子图，每个第一同构子图根据上述成本公式分别对应一个消耗成本；第二个同构子图映射方式集合包括32个第二同构子图，每个第二同构子图根据上述成本公式分别对应一个消耗成本；第三个同构子图映射方式集合包括20个第三同构子图，每个第三同构子图根据上述成本公式也分别对应一个消耗成本；第一个同构子图映射方式集合与第二个同构子图映射方式集合间存在24×32个消耗成本，第二个同构子图映射方式集合与第三个同构子图映射方式集合间存在32×20个消耗成本。因此可以基于第一个同构子图映射方式集合、第二个同构子图映射方式集合、第三个同构子图映射方式集合组合出24×32×20个映射方式，每个映射方式对应一个消耗成本，每个消耗成本基于上述成本公式确定，可以选取消耗成本最小的方式确定待执行量子程序的最终映射，以使所述最终映射的成本最低。

本申请实施例提供了一种量子程序最终映射的确定方法，通过计算出所有映射方式的消耗成本，然后确定消耗成本最小的最终映射，确定待执行量子程序的最终映射线路，使得整个量子芯片的资源利用最大化。

需要说明的是，待执行量子程序的有向无环图中单量子逻辑门的存在并不影响最大子图的构建和最终映射的确定，通过有单量子逻辑门的有向无环图得到的最大子图与通过不包含单量子逻辑门的有向无环图得到的最大子图相同。因此，在这里为了简便，删除了单量子逻辑门，仅以包含两比特量子逻辑门的有向无环图举例。

与现有技术相比，本申请首先获取量子程序的有向无环图，根据量子程序的有向无环图，确定量子程序的最大子图集合及最大子图对应的同构子图集合，分别确定同构子图集合中每个同构子图映射到量子芯片拓扑结构的成本，根据每个同构子图映射到量子芯片拓扑结构的成本，确定待执行量子程序的最终映射，以使最终映射的成本最低，既解决因单个物理比特因素对整个量子线路产生影响的问题，也可以确定量子芯片拓扑结构的最终映射线路，使得整个量子芯片的资源利用最大化。

参见图17，图17为本发明实施例提供的一种量子程序最终映射的确定装置的结构示意图，与图2所示的流程相对应，该装置可以包括：

获取模块1701，用于获取待执行量子程序的有向无环图；

第一确定模块1702，用于根据所述待执行量子程序的有向无环图，确定所述待执行量子程序的最大子图集合及最大子图对应的同构子图集合，其中，所述同构子图集合是所述最大子图根据量子芯片的拓扑结构得到的逻辑比特-物理比特初始映射关系图集合；

第二确定模块1703，用于分别确定所述同构子图集合中每个同构子图映射到所述量子芯片拓扑结构的成本；

第三确定模块1704，用于根据所述每个同构子图映射到所述量子芯片拓扑结构的成本，确定所述待执行量子程序的最终映射，以使所述最终映射的成本最低。

具体的，所述获取模块，包括：

获取单元，用于获取待执行量子程序中的节点；

确定单元，用于根据所述节点操作的量子比特，确定所述节点之间的关联关系；

生成单元，用于根据所述节点及节点之间的关联关系，生成与所述待执行量子程序对应的有向无环图，其中，所述有向无环图中的顶点表征节点，所述有向无环图中的边表征节点之间的关联关系，所述边的方向表征该边相连的顶点对应的节点被执行的时序关系。

具体的，所述第一确定模块，包括：

遍历单元，用于遍历所述待执行量子程序的有向无环图得到最大子图集合，所述最大子图集合包括N个最大子图，N为大于或等于1的整数；

得到单元，用于确定所述N个最大子图在量子芯片的拓扑结构中的同构子图，得到N个同构子图集合，所述N个同构子图集合与所述N个最大子图一一对应。

具体的，所述遍历单元，包括：

子图单元，用于根据所述有向无环图中入度为零的第一节点，生成第一子图；

删除单元，用于删除所述第一节点得到新的有向无环图；

判断单元，用于确定所述新的有向无环图中是否存在入度为零的第二节点；

第一子图确定单元，用于若所述新的有向无环图中不存在所述第二节点，则将所述第一子图确定为一个最大子图。

具体的，所述装置还包括：

第二子图确定单元，用于若所述新的有向无环图中存在所述第二节点，则确定所述第二节点与所述第一节点的邻接关系；

最大子图生成单元，用于基于所述邻接关系和所述第一节点，生成一个最大子图。

具体的，所述最大子图生成单元，包括：

拓展单元，用于基于所述第二节点与所述第一节点的邻接关系，将所述第一子图拓展为第二子图，并将所述第二子图作为新的第一子图；

继续执行单元，用于获取删除所述第二节点后的新有向无环图，继续执行所述确定所述新的有向无环图中是否存在入度为零的第二节点的步骤。

具体的，所述第二确定模块，包括：

映射单元，用于根据所述最大子图集合及最大子图对应的同构子图集合，分别获取每个同构子图映射到所述量子芯片拓扑结构的映射方式；

构建单元，用于构建评估所述映射方式的成本公式并计算映射方式的成本。

与现有技术相比，本申请首先获取量子程序的有向无环图，根据量子程序的有向无环图，确定量子程序的最大子图集合及最大子图对应的同构子图集合，分别确定同构子图集合中每个同构子图映射到量子芯片拓扑结构的成本，根据每个同构子图映射到量子芯片拓扑结构的成本，确定待执行量子程序的最终映射，以使最终映射的成本最低，既解决因单个物理比特因素对整个量子线路产生影响的问题，也可以确定量子芯片拓扑结构的最终映射线路，使得整个量子芯片的资源利用最大化。

本发明实施例还提供了一种存储介质，所述存储介质中存储有计算机程序，其中，所述计算机程序被设置为运行时执行上述任一项中方法实施例中的步骤。

具体的，在本实施例中，上述存储介质可以被设置为存储用于执行以下步骤的计算机程序：

S201：获取待执行量子程序的有向无环图；

S202：根据所述待执行量子程序的有向无环图，确定所述待执行量子程序的最大子图集合及最大子图对应的同构子图集合，其中，所述同构子图集合是所述最大子图根据量子芯片的拓扑结构得到的逻辑比特-物理比特初始映射关系图集合；

S203：分别确定所述同构子图集合中每个同构子图映射到所述量子芯片拓扑结构的成本；

S204：根据所述每个同构子图映射到所述量子芯片拓扑结构的成本，确定所述待执行量子程序的最终映射，以使所述最终映射的成本最低。

具体的，在本实施例中，上述存储介质可以包括但不限于：U盘、只读存储器(Read-Only Memory，简称为ROM)、随机存取存储器(Random Access Memory，简称为RAM)、移动硬盘、磁碟或者光盘等各种可以存储计算机程序的介质。

与现有技术相比，本申请首先获取量子程序的有向无环图，根据量子程序的有向无环图，确定量子程序的最大子图集合及最大子图对应的同构子图集合，分别确定同构子图集合中每个同构子图映射到量子芯片拓扑结构的成本，根据每个同构子图映射到量子芯片拓扑结构的成本，确定待执行量子程序的最终映射，以使最终映射的成本最低，既解决因单个物理比特因素对整个量子线路产生影响的问题，也可以确定量子芯片拓扑结构的最终映射线路，使得整个量子芯片的资源利用最大化。

本发明实施例还提供了一种电子装置，包括存储器和处理器，所述存储器中存储有计算机程序，所述处理器被设置为运行所述计算机程序以执行上述任一项中方法实施例中的步骤。

具体的，上述电子装置还可以包括传输设备以及输入输出设备，其中，该传输设备和上述处理器连接，该输入输出设备和上述处理器连接。

具体的，在本实施例中，上述处理器可以被设置为通过计算机程序执行以下步骤：

S201：获取待执行量子程序的有向无环图；

S202：根据所述待执行量子程序的有向无环图，确定所述待执行量子程序的最大子图集合及最大子图对应的同构子图集合，其中，所述同构子图集合是所述最大子图根据量子芯片的拓扑结构得到的逻辑比特-物理比特初始映射关系图集合；

S203：分别确定所述同构子图集合中每个同构子图映射到所述量子芯片拓扑结构的成本；

S204：根据所述每个同构子图映射到所述量子芯片拓扑结构的成本，确定所述待执行量子程序的最终映射，以使所述最终映射的成本最低。

与现有技术相比，本申请首先获取量子程序的有向无环图，根据量子程序的有向无环图，确定量子程序的最大子图集合及最大子图对应的同构子图集合，分别确定同构子图集合中每个同构子图映射到量子芯片拓扑结构的成本，根据每个同构子图映射到量子芯片拓扑结构的成本，确定待执行量子程序的最终映射，以使最终映射的成本最低，既解决因单个物理比特因素对整个量子线路产生影响的问题，也可以确定量子芯片拓扑结构的最终映射线路，使得整个量子芯片的资源利用最大化。

本发明实施例还提供了一种量子计算机操作系统，所述量子计算机操作系统根据本发明实施例中提供的上述任一方法实施例实现量子程序最终映射的确定。

本申请的实施例还提供了一种量子计算机，所述量子计算机包括所述的量子计算机操作系统。

与现有技术相比，本申请首先获取量子程序的有向无环图，根据量子程序的有向无环图，确定量子程序的最大子图集合及最大子图对应的同构子图集合，分别确定同构子图集合中每个同构子图映射到量子芯片拓扑结构的成本，根据每个同构子图映射到量子芯片拓扑结构的成本，确定待执行量子程序的最终映射，以使最终映射的成本最低，既解决因单个物理比特因素对整个量子线路产生影响的问题，也可以确定量子芯片拓扑结构的最终映射线路，使得整个量子芯片的资源利用最大化。

以上依据图式所示的实施例详细说明了本发明的构造、特征及作用效果，以上所述仅为本发明的较佳实施例，但本发明不以图面所示限定实施范围，凡是依照本发明的构想所作的改变，或修改为等同变化的等效实施例，仍未超出说明书与图示所涵盖的精神时，均应在本发明的保护范围内。

Claims (13)

1.一种量子程序最终映射的确定方法，其特征在于，所述方法包括：

获取待执行量子程序的有向无环图；

根据所述待执行量子程序的有向无环图，确定所述待执行量子程序的最大子图集合及最大子图对应的同构子图集合，其中，所述同构子图集合是所述最大子图根据量子芯片的拓扑结构得到的逻辑比特-物理比特初始映射关系图集合；

分别确定所述同构子图集合中每个同构子图映射到所述量子芯片拓扑结构的成本；

根据所述每个同构子图映射到所述量子芯片拓扑结构的成本，确定所述待执行量子程序的最终映射，以使所述最终映射的成本最低。

2.根据权利要求1所述的方法，其特征在于，所述获取待执行量子程序的有向无环图，包括：

获取待执行量子程序中的节点；

根据所述节点操作的量子比特，确定所述节点之间的关联关系；

根据所述节点及节点之间的关联关系，生成与所述待执行量子程序对应的有向无环图，其中，所述有向无环图中的顶点表征节点，所述有向无环图中的边表征节点之间的关联关系，所述边的方向表征该边相连的顶点对应的节点被执行的时序关系。

3.根据权利要求2所述的方法，其特征在于，所述根据所述待执行量子程序的有向无环图，确定所述待执行量子程序的最大子图集合及最大子图对应的同构子图集合，包括：

遍历所述待执行量子程序的有向无环图得到最大子图集合，所述最大子图集合包括N个最大子图，N为大于或等于1的整数；

确定所述N个最大子图在量子芯片的拓扑结构中的同构子图，得到N个同构子图集合，所述N个同构子图集合与所述N个最大子图一一对应。

4.根据权利要求3所述的方法，其特征在于，所述遍历所述待执行量子程序的有向无环图得到最大子图集合，包括：

根据所述有向无环图中入度为零的第一节点，生成第一子图；

删除所述第一节点得到新的有向无环图；

确定所述新的有向无环图中是否存在入度为零的第二节点；

若所述新的有向无环图中不存在所述第二节点，则将所述第一子图确定为一个最大子图。

5.根据权利要求4所述的方法，其特征在于，所述方法还包括：

若所述新的有向无环图中存在所述第二节点，则确定所述第二节点与所述第一节点的邻接关系；

基于所述邻接关系和所述第一节点，生成一个最大子图。

6.根据权利要求5所述的方法，其特征在于，所述基于所述邻接关系和所述第一节点，生成一个最大子图，包括：

基于所述第二节点与所述第一节点的邻接关系，将所述第一子图拓展为第二子图，并将所述第二子图作为新的第一子图；

获取删除所述第二节点后的新有向无环图，继续执行所述确定所述新的有向无环图中是否存在入度为零的第二节点的步骤。

7.根据权利要求1所述的方法，其特征在于，所述分别确定所述同构子图集合中每个同构子图映射到所述量子芯片拓扑结构的成本，包括：

根据所述最大子图集合及最大子图对应的同构子图集合，分别获取每个同构子图映射到所述量子芯片拓扑结构的映射方式；

构建评估所述映射方式的成本公式并计算映射方式的成本。

8.根据权利要求7所述的方法，其特征在于，所述评估所述映射方式的成本公式为：

其中，T₂为量子芯片比特的退相干时间，G_swap为最终映射方式所需要引入的SWAP门个数，f_double为两比特量子逻辑门保真度，f_measure为测量保真度，a₁、a₂、a₃、a₄为成本公式的预设权重系数。

9.一种量子程序最终映射的确定装置，其特征在于，所述装置包括：

获取模块，用于获取待执行量子程序的有向无环图；

第一确定模块，用于根据所述待执行量子程序的有向无环图，确定所述待执行量子程序的最大子图集合及最大子图对应的同构子图集合，其中，所述同构子图集合是所述最大子图根据量子芯片的拓扑结构得到的逻辑比特-物理比特初始映射关系图集合；

第二确定模块，用于分别确定所述同构子图集合中每个同构子图映射到所述量子芯片拓扑结构的成本；

第三确定模块，用于根据所述每个同构子图映射到所述量子芯片拓扑结构的成本，确定所述待执行量子程序的最终映射，以使所述最终映射的成本最低。

10.一种存储介质，其特征在于，所述存储介质中存储有计算机程序，其中，所述计算机程序被设置为运行时执行所述权利要求1至8任一项中所述的方法。

11.一种电子装置，包括存储器和处理器，其特征在于，所述存储器中存储有计算机程序，所述处理器被设置为运行所述计算机程序以执行所述权利要求1至8任一项中所述的方法。

12.一种量子计算机操作系统，其特征在于，所述量子计算机操作系统根据权利要求1至8任一项所述的方法实现量子程序最终映射的确定。

13.一种量子计算机，其特征在于，所述量子计算机包括权利要求12所述的量子计算机操作系统。

Images