量子连通图谱的聚团划分方法、装置、终端及存储介质与流程

1.本技术涉及量子计算技术领域，具体而言，涉及一种量子连通图谱的聚团划分方法、装置、终端及存储介质。


背景技术：

2.随着量子计算技术的普及，实施量子计算的量子芯片，成为了研究的重点对象。量子芯片相对较传统的集成芯片，具有强大的并行计算能力，且并行计算能力随着量子芯片的位数(量子比特数)呈指数式提升。
3.相关技术中，量子算法是在量子线路中进行模拟，并需要在量子芯片上运行的用于实施量子计算的方法。当量子算法编译到量子芯片上时，通常会基于预先生成的量子算法的量子连通图谱对量子芯片的结构进行设计。然而，当量子连通图谱中存在连通的聚团结构时，由于聚团结构间的连接比聚团结构内部连接稀疏，因此就导致如果要寻找一条连接两个不同聚团结构的图谱节点的路径，那么选择会变少，如果把所有连通路径都计算出来，统计所有连通路径途径所有连线的次数，那么途径聚团结构之间连线的次数会明显高于途径聚团内部的连线，导致算法运行效果不佳。


技术实现要素：

4.基于现有设计的不足，本技术提供一种量子连通图谱的聚团划分方法、装置、终端及存储介质，通过将量子连通图谱划分为多个不连通的目标子图谱聚团，从而可以便于后续单独基于每个不连通的目标子图谱聚团进行后续的量子算法设计，提高算法运行效果。
5.根据本技术的第一方面，提供一种量子连通图谱的聚团划分方法，所述方法包括：
6.获取目标量子算法的量子连通图谱，所述量子连通图谱包括多个图谱节点以及两个图谱节点之间的连线，其中，所述图谱节点用于表示所述目标量子算法中的逻辑比特，所述连线用于表示两个所述逻辑比特之间的量子比特逻辑门；
7.计算所述量子连通图谱中所有连线的连线中介度，并计算所述量子连通图谱中所有图谱节点的节点中介度；
8.根据所述所有连线的连线中介度和所述所有图谱节点的节点中介度将所述量子连通图谱划分为多个不连通的目标子图谱聚团。
9.在第一方面的一种可能的实施方式中，所述计算所述量子连通图谱中所有连线的连线中介度的步骤，包括：
10.计算每两个图谱节点在所述量子连通图谱中的最短连通路径；
11.基于所述最短连通路径计算每两个图谱节点之间的连线的连线中介度。
12.在第一方面的一种可能的实施方式中，所述计算每两个图谱节点在所述量子连通图谱中的最短连通路径的步骤，包括：
13.针对每个图谱节点，初始化赋予该图谱节点与其它图谱节点在所述量子连通图谱中的第一距离为0、第一节点权重为1；
14.对于每一个与该图谱节点相邻的其它第一图谱节点，赋予每个第一图谱节点与该图谱节点之间的第二距离为所述第一距离加1、第二节点权重为所述第一节点权重，并将所述第一图谱节点到该图谱节点之间的连线构成的路径标记为该图谱节点与该第一图谱节点间的最短路径；
15.对于每一个与所述第一图谱节点相邻的第二图谱节点，赋予所述第二图谱节点的第三距离为所述第二距离加1、第三节点权重为所述第二节点权重，并将所述第二图谱节点到所述第一图谱节点、所述第一图谱节点到该图谱节点之间的连线构成的路径标记为该图谱节点与该第二图谱节点间的最短路径。
16.在第一方面的一种可能的实施方式中，所述基于所述最短连通路径计算每两个图谱节点之间的连线的连线中介度的步骤，包括：
17.获取所述最短连通路径中根节点关联的所有叶节点，并计算所有连接所述叶节点和所述叶节点的邻接节点之间的连线的第一连线评分；
18.从距离所述根节点最远的叶节点开始遍历，分别计算每相邻的两个叶节点之间的连线的第二连线评分，直到到达根节点时，获得所有连线的第二连线评分；
19.将所述第一连线评分和所有第二连线评分进行求和，获得每两个图谱节点之间的连线的连线中介度。
20.在第一方面的一种可能的实施方式中，所述计算所述量子连通图谱中所有图谱节点的节点中介度的步骤，包括：
21.计算穿过每个图谱节点的最短连通路径的总数量；
22.基于所述穿过每个图谱节点的最短连通路径的总数量，获得每个所述图谱节点的节点中介度。
23.在第一方面的一种可能的实施方式中，所述根据所述所有连线的连线中介度和所述所有图谱节点的节点中介度将所述量子连通图谱划分为多个不连通的目标子图谱聚团的步骤，包括：
24.获取所述所有图谱节点中节点中介度大于所述所有连线的连线中介度中最大连线中介度的目标图谱节点；
25.计算所述目标图谱节点的点对中介度，并根据所述点对中介度计算所述目标图谱节点的分裂中介度；
26.如果所述目标图谱节点的分裂中介度大于所述最大连线中介度，则对所述目标图谱节点执行点分裂操作，否则对所述目标图谱节点执行去除连线操作；
27.在执行所述点分裂操作或者所述去除连线操作后，检测所述量子连通图谱是否分裂为不连通子图；
28.如果检测到所述量子连通图谱分裂为不连通子图，则采用modularity函数计算分裂的所述不连通子图的划分评估值；
29.根据所述划分评估值重新计算所述所有连线的连线中介度，返回执行计算所述量子连通图谱中所有图谱节点的节点中介度的步骤，直到获得完全不连通的目标子图谱聚团，以将所述量子连通图谱划分为多个不连通的目标子图谱聚团。
30.在第一方面的一种可能的实施方式中，所述计算所述目标图谱节点的点对中介度，并根据所述点对中介度计算所述目标图谱节点的分裂中介度的步骤，包括：
31.计算经过所述目标图谱节点和所述目标图谱节点的每个邻接图谱节点的连线的最短路径总数，作为所述目标图谱节点的点对中介度；
32.将最低点对中介度对应的两个选定图谱节点确定为一个归结图谱节点，所述归结图谱节点的点对中介度为所述两个选定图谱节点的点对中介度的相加值；
33.对于所述目标图谱节点的所有邻接图谱节点构成的子图，通过所述归结图谱节点和辅助图谱节点分别取代所述所有邻接图谱节点分别与所述归结图谱节点之间的连线连接，并将所述辅助图谱节点与所述两个选定图谱节点之间的点对中介度的相加值作为所述作为辅助图谱节点到所述归结图谱节点的点对中介度；
34.重复执行预设次数的所述将最低点对中介度对应的两个选定图谱节点确定为一个归结图谱节点的步骤，其中，所述预设次数为所述目标图谱节点的度数减2；
35.在执行预设次数的所述将最低点对中介度对应的两个选定图谱节点确定为一个归结图谱节点的步骤后，得到两个最终图谱节点，并将所述两个最终图谱节点之间的点对中介度之和确定为所述目标图谱节点的分裂中介度。
36.在第一方面的一种可能的实施方式中，所述采用modularity函数计算分裂的所述不连通子图的划分评估值的步骤，包括：
37.获取分裂的所述不连通子图的分裂子图数量、每个所述不连通子图内部的连线数量以及每个所述不连通子图内部所有图谱节点的连通度之和；
38.基于分裂的所述不连通子图的分裂子图数量、每个所述不连通子图内部的连线数量以及每个所述不连通子图内部所有图谱节点的连通度之和，采用modularity函数计算分裂的所述不连通子图的划分评估值。
39.根据本技术的第二方面，提供一种量子连通图谱的聚团划分装置，所述装置包括：
40.获取模块，用于获取目标量子算法的量子连通图谱，所述量子连通图谱包括多个图谱节点以及两个图谱节点之间的连线，其中，所述图谱节点用于表示所述目标量子算法中的逻辑比特，所述连线用于表示两个所述逻辑比特之间的量子比特逻辑门；
41.计算模块，用于计算所述量子连通图谱中所有连线的连线中介度，并计算所述量子连通图谱中所有图谱节点的节点中介度；
42.划分模块，用于根据所述所有连线的连线中介度和所述所有图谱节点的节点中介度将所述量子连通图谱划分为多个不连通的目标子图谱聚团。
43.根据本技术的第三方面，提供一种计算机终端，包括机器可读存储介质和处理器，所述机器可读存储介质中存储有计算机程序，所述处理器被设置为运行所述计算机程序以执行第一方面或者第一方面中任意一种可能的实施方式所述的量子连通图谱的聚团划分方法。
44.根据本技术的第四方面，提供一种计算机可读存储介质，所述计算机可读存储介质中存储有计算机程序，当所述计算机程序被计算机执行时，实现第一方面或者第一方面中任意一种可能的实施方式所述的量子连通图谱的聚团划分方法。
45.基于上述任一方面，本技术通过计算量子连通图谱中所有连线的连线中介度，并计算量子连通图谱中所有图谱节点的节点中介度，从而根据所有连线的连线中介度和所有图谱节点的节点中介度将量子连通图谱划分为多个不连通的目标子图谱聚团。如此，通过将量子连通图谱划分为多个不连通的目标子图谱聚团，从而可以便于后续单独基于每个不
连通的目标子图谱聚团进行后续的量子算法设计，提高算法运行效果。
附图说明
46.为了更清楚地说明本技术实施例的技术方案，下面将对实施例中所需要使用的附图作简单地介绍，应当理解，以下附图仅示出了本技术的某些实施例，因此不应被看作是对范围的限定，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他相关的附图。
47.图1示出了本技术实施例所提供的量子连通图谱的聚团划分方法的流程示意图；
48.图2示出了图1中所示的步骤s120的子步骤流程示意图；
49.图3示出了图1中所示的步骤s130的子步骤流程示意图；
50.图4示出了本技术实施例所提供的量子连通图谱的聚团划分装置的功能模块示意图；
51.图5示出了本技术实施例所提供的用于实现上述量子连通图谱的聚团划分的计算机终端的组件结构示意框图。
具体实施方式
52.为使本技术实施例的目的、技术方案和优点更加清楚，下面将结合本技术实施例中的附图，对本技术实施例中的技术方案进行清楚、完整地描述，应当理解，本技术中附图仅起到说明和描述的目的，并不用于限定本技术的保护范围。另外，应当理解，示意性的附图并未按实物比例绘制。本技术中使用的流程图示出了根据本技术实施例的一些实施例实现的操作。
53.应该理解，流程图的操作可以不按顺序实现，没有逻辑的上下文关系的步骤可以反转顺序或者同时实施。此外，本领域技术人员在本技术内容的指引下，可以向流程图添加一个或多个其它操作，也可以从流程图中移除一个或多个操作。
54.请参照图1，示出了本技术实施例提供的量子连通图谱的聚团划分方法的交互流程示意图，应当理解，在其它实施例中，本实施例的量子连通图谱的聚团划分方法其中部分步骤的顺序可以根据实际需要相互交换，或者其中的部分步骤也可以省略或删除。该量子连通图谱的聚团划分方法的详细步骤介绍如下。
55.步骤s110，获取目标量子算法的量子连通图谱。
56.本实施例中，量子连通图谱可以包括多个图谱节点以及两个图谱节点之间的连线，图谱节点可以用于表示目标量子算法中的逻辑比特，连线可以用于表示两个逻辑比特之间的量子比特逻辑门。
57.其中，该量子连通图谱可以基于该目标量子算法中的逻辑比特以及任意两个量子比特上施加的量子比特逻辑门的次数获得。其中，量子比特可以是指一种可以同时处于基态|0》、激发态|1》以及叠加态(α|0》+β|1》)的物理体系。在数学上，量子比特可以由希尔伯特空间上的态矢量表示。量子线路是通过同时操纵若干个量子比特实现的。
58.量子线路是量子程序的一种表示形式，可以由一连串初始位于|0》态的量子比特以及后续的若干个量子逻辑门组成，由测量操作作为结尾(不一定每个比特都需要被测量)。通常，每个量子程序可以最终被分解为只由基本量子逻辑门序列构成的量子程序。此
外，量子比特逻辑门可以是指一些可逆的幺正变换，可以用于操纵若干个量子比特，让这些量子比特向目标态演化，演化最终态即为量子计算的结果。
59.步骤s120，计算量子连通图谱中所有连线的连线中介度，并计算量子连通图谱中所有图谱节点的节点中介度。
60.本实施例中，连线的连线中介度可以衡量一条连线属于聚团间连接的可能性大小的指标。经本技术发明人研究发现，通常量子连通图谱中出现聚团现象是指量子连通图谱内若干个子图谱内图谱节点之间互相连接比子图谱之间节点连接的连线数目的更多。如果两个子图谱之间被较少的聚团间连线连接，那么所有从一个聚团内节点到另一个聚团内节点的路径必须通过这些比聚团内部数目更少的连线。因为连线的数目更少了，可选择路径变少，所以路径途径这些连线的次数比聚团内部节点之间的路径途径聚团内部的连线要多，这个次数就与连线中介度有关。
61.步骤s130，根据所有连线的连线中介度和所有图谱节点的节点中介度将量子连通图谱划分为多个不连通的目标子图谱聚团。
62.本实施例中，通过将量子连通图谱划分为多个不连通的目标子图谱聚团，后续可以针对每个不连通的目标子图谱聚团单独进行处理，例如对每个不连通的目标子图谱聚团进行相应的连通度优化、交叉连线优化等。
63.基于上述步骤，本实施例通过计算量子连通图谱中所有连线的连线中介度，并计算量子连通图谱中所有图谱节点的节点中介度，从而根据所有连线的连线中介度和所有图谱节点的节点中介度将量子连通图谱划分为多个不连通的目标子图谱聚团。如此，通过将量子连通图谱划分为多个不连通的目标子图谱聚团，从而可以便于后续单独基于每个不连通的目标子图谱聚团进行后续的量子算法设计，提高算法运行效果。
64.在一种可能的实施方式中，针对步骤s120，在计算量子连通图谱中所有连线的连线中介度的实施方式中，请结合参阅图2，可以通过以下示例性的子步骤来实现，详细描述如下。
65.子步骤s121，计算每两个图谱节点在量子连通图谱中的最短连通路径。
66.例如，针对每个图谱节点，可以初始化赋予该图谱节点与其它图谱节点在量子连通图谱中的第一距离ds为0、第一节点权重ws为1。
67.在此基础上，对于每一个与该图谱节点相邻的其它第一图谱节点，可以赋予每个第一图谱节点与该图谱节点之间的第二距离为第一距离加1、第二节点权重为第一节点权重，并将第一图谱节点到该图谱节点之间的连线构成的路径标记为该图谱节点与该第一图谱节点间的最短路径。如，对于每一个与该图谱节点s相邻的其它第一图谱节点i，第二距离di＝ds+1，第二节点权重wi＝ws＝1，把所有图谱节点s》其它第一图谱节点i标记为这两个图谱节点间的最短连通路径。
68.进一步地，对于每一个与第一图谱节点相邻的第二图谱节点，赋予第二图谱节点的第三距离为第二距离加1、第三节点权重为第二节点权重，并将第二图谱节点到第一图谱节点、第一图谱节点到该图谱节点之间的连线构成的路径标记为该图谱节点与该第二图谱节点间的最短路径。如，对于每一个与第一图谱节点i相邻的第二图谱节点j，如果第二图谱节点j没有被赋予第三距离，就赋予第三距离dj＝di+1和第三节点权重wj＝wi，把s》......》i》j标记为从s到j的一条最短连通路径。
69.子步骤s122，基于最短连通路径计算每两个图谱节点之间的连线的连线中介度。
70.例如，首先获取最短连通路径中根节点s关联的所有叶节点t，并计算所有连接叶节点t和叶节t点的邻接节点之间的连线的第一连线评分。其中，第一连线评分为邻接节点的节点权重与叶节点t的节点权重之商。
71.接着，从距离根节点s最远的叶节点t开始遍历，分别计算每相邻的两个叶节点t之间的连线的第二连线评分，直到到达根节点s时，获得所有连线的第二连线评分。例如，对于相邻的叶节点i和叶节点j，叶节点i比叶节点j距离根节点s更近，对连接叶节点i和叶节点j的连线的第二连线评分
72.由此，可以将第一连线评分和所有第二连线评分进行求和，获得每个图谱节点与其它图谱节点在量子连通图谱中的连线中介度。
73.在一种可能的实施方式中，仍旧针对步骤s120，在计算量子连通图谱中所有图谱节点的节点中介度的实施方式中，仍旧参阅图2，可以通过以下示例性的子步骤来实现，详细描述如下。
74.子步骤s123，计算穿过每个图谱节点的最短连通路径的总数量。
75.本实施例中，关于穿过每个图谱节点的最短连通路径，可以参照子步骤s111中针对每两个图谱节点在量子连通图谱中的最短连通路径进行确定，在此不再赘述。
76.子步骤s124，基于穿过每个图谱节点的最短连通路径的总数量，获得每个图谱节点的节点中介度。
77.本实施例中，每个图谱节点的节点中介度可以等于穿过每个图谱节点的最短连通路径的总数量，也可以等于穿过每个图谱节点的最短连通路径的总数量与预设系数的加权值，在此不作具体限定。
78.其中，每个图谱节点的节点中介度，可以通过以下计算公式得到：
[0079][0080]
其中，γ(v)是以v为端点的所有连线，n这部分子图里所有图谱节点的个数，cb(v)，cb(e)分别表示节点中介度和连线中介度，所述节点中介度定义了什么时候执行点分裂操作的问题，因为在把图谱节点v的邻接点分成n1，n2两部分后，从n1到n2的最短路径总数必小于图谱节点v的节点中介度，故只有在后续图谱节点的节点中介度大于连线中介度时，才可能考虑执行点分裂操作。
[0081]
如此，通过计算每个图谱节点的节点中介度，可以解决在何时执行点分裂操作以及如何执行点分裂操作的问题，如果能够定位若干个高中介度的连线，则这些连线是聚团之间的连接，通过去除这些连线，即可将量子连通图谱划分为若干个不连通的聚团，进而完成聚团划分。
[0082]
在一种可能的实施方式中，对于步骤s130，请结合参阅图3，可以通过以下示例性的子步骤来实现，详细描述如下。
[0083]
子步骤s131，获取所有图谱节点中节点中介度大于所有连线的连线中介度中最大连线中介度的目标图谱节点。
[0084]
子步骤s132，计算目标图谱节点的点对中介度，并根据点对中介度计算目标图谱
节点的分裂中介度。
[0085]
例如，在一种可能的示例中，子步骤s132可以通过以下示例性的实施方式实现。
[0086]
(1)计算经过目标图谱节点和目标图谱节点的每个邻接图谱节点的连线的最短路径总数，作为目标图谱节点的点对中介度。
[0087]
本实施例中，点对中介度是一个局部的指标，对一个目标图谱节点v，其任意邻接图谱节点{u，w}的点对中介度是所有经过连线{u，v}和{w，v}的最短路径总数。
[0088]
(2)将最低点对中介度对应的两个选定图谱节点确定为一个归结图谱节点。
[0089]
本实施例中，归结图谱节点的点对中介度可以为两个选定图谱节点的点对中介度的相加值。
[0090]
(3)对于目标图谱节点的所有邻接图谱节点构成的子图，通过归结图谱节点和辅助图谱节点分别取代所有邻接图谱节点分别与归结图谱节点之间的连线连接，并将辅助图谱节点与两个选定图谱节点之间的点对中介度的相加值作为辅助图谱节点到归结图谱节点的点对中介度。
[0091]
(4)重复执行预设次数的将最低点对中介度对应的两个选定图谱节点确定为一个归结图谱节点的步骤。
[0092]
本实施例中，预设次数为目标图谱节点的度数减2。
[0093]
(5)在执行预设次数的将最低点对中介度对应的两个选定图谱节点确定为一个归结图谱节点的步骤后，得到两个最终图谱节点，并将两个最终图谱节点之间的点对中介度之和确定为目标图谱节点的分裂中介度。
[0094]
例如，在得到点对中介度后，通过选择最低点对中介度的两个选定图谱节点{u，w}，然后把u，w归结为一个归结图谱节点uw，归结图谱节点uw的点对中介度为两个选定图谱节点{u，w}的点对中介度相加。
[0095]
对于目标图谱节点v所有邻接图谱节点构成的子图，可以用{uw，x}取代这些邻接图谱节点分别与归结图谱节点之间的连接连接，并且所有辅助图谱节点x与u，w之间的点对中介度相加，得到辅助图谱节点x到归结图谱节点uw的点对中介度。
[0096]
然后，重复将最低点对中介度对应的两个选定图谱节点确定为一个归结图谱节点k-2次，k为目标图谱节点的度数。
[0097]
如此，最终可以得到两个最终图谱节点，这两个最终图谱节点之间的点对中介度之和可以确定为目标图谱节点的分裂中介度，这两个最终图谱节点包含的节点就是节点分裂为两部分后，邻接图谱节点如何分别与两个最终图谱节点连接。
[0098]
子步骤s133，如果目标图谱节点的分裂中介度大于最大连线中介度，则对目标图谱节点执行点分裂操作，否则对目标图谱节点执行去除连线操作。
[0099]
本实施例中，只有当目标图谱节点的分裂中介度大于最大连线中介度时，才会对目标图谱节点执行点分裂操作，否则对目标图谱节点执行去除连线操作。
[0100]
子步骤s134，在执行点分裂操作或者去除连线操作后，检测量子连通图谱是否分裂为不连通子图。
[0101]
例如，在执行点分裂操作的过程中，可以将一个图谱节点v分裂成两部分v1，v2。原本v的邻接图谱节点可以以某种方式分别与v1，v2相连，分裂高中介度的点，就可以将量子连通图谱划分成若干个不连通的聚团。
[0102]
子步骤s135，如果检测到量子连通图谱分裂为不连通子图，则采用modularity函数计算分裂的不连通子图的划分评估值。
[0103]
聚团是指一个量子连通图谱中有若干个子图，其内部的连通度通常要高于这些子图之间的连通度，由于在前述的步骤执行时，在进行点分裂操作或者去除连线操作的过程中，每一步都可能需要去除一条连线，或者可能需要分裂一个图谱节点，从而将量子连通图谱逐步划分成更小的部分，这是一个层级过程。例如，先将一个大的量子连通图谱分成两个，再在两个更小的子图里划分，最终得到所有聚团只有一个图谱节点的一组划分。在此基础上，为了保证后续的算法运行效果，最终还需要通过一个modularity函数评估划分到哪个层级是较优的。通常来说，modularity函数一般先增后减，有若干个峰值，在最高的峰值处，就是划分的最佳位置。如果modularity函数没有这种行为，或者峰值过低，则可认为不存在聚团结构。
[0104]
示例性地，本实施例中可以获取分裂的不连通子图的分裂子图数量、每个不连通子图内部的连线数量以及每个不连通子图内部所有图谱节点的连通度之和。
[0105]
在此基础上，基于分裂的不连通子图的分裂子图数量、每个不连通子图内部的连线数量以及每个不连通子图内部所有图谱节点的连通度之和，采用modularity函数计算分裂的不连通子图的划分评估值。
[0106]
例如，在划分聚团的时候，需要指定一个标准，在没有标准的情况下，整个量子连通图谱可以是一个聚团的，每一个图谱节点自身也可能是一个聚团的，因此需要定义一个指标来衡量划分的好坏程度，发明人经过研究认为聚团之间的连接要弱于聚团内部的连接，所以定义modularity函数q如下：
[0107][0108]
其中，a
ij
是算法本真的联通矩阵，p
ij
的意义是，假设当前直到所有节点的联通度ki，则对于一个完全随机的图节点i和j之间存在连接的概率为而p
ij
＝2mp
ij
是存在连线的期望值。基于此，modularity函数q还可以归结如下：
[0109][0110]
其中，nc是聚团的数目，lc是聚团内部的总连线数，dc是聚团内部所有节点的联通度之和。如果modularity函数存在峰值，在峰值处通常可以理解为划分选择较佳的节点。
[0111]
子步骤s136，根据划分评估值重新计算所有连线的连线中介度，返回执行计算量子连通图谱中所有图谱节点的节点中介度的步骤，直到获得完全不连通的目标子图谱聚团，以将量子连通图谱划分为多个不连通的目标子图谱聚团。
[0112]
本实施例中，在获得划分评估值后，可以通过划分选择较佳的节点之后划分形成新的聚团，然后重新计算所有连线的连线中介度或，继续上述步骤，直到获得完全不连通的目标子图谱聚团，以将量子连通图谱划分为多个不连通的目标子图谱聚团。
[0113]
基于同一发明构思，请参阅图4，示出了本技术实施例提供的量子连通图谱的聚团划分装置110的功能模块示意图，本实施例可以根据上述的方法实施例对量子连通图谱的
聚团划分装置110进行功能模块的划分。例如，可以对应各个功能划分各个功能模块，也可以将两个或两个以上的功能集成在一个处理模块中。上述集成的模块既可以采用硬件的形式实现，也可以采用软件功能模块的形式实现。需要说明的是，本技术实施例中对模块的划分是示意性的，仅仅为一种逻辑功能划分，实际实现时可以有另外的划分方式。比如，在采用对应各个功能划分各个功能模块的情况下，图4示出的量子连通图谱的聚团划分装置110只是一种装置示意图。其中，量子连通图谱的聚团划分装置110可以包括获取模块111、计算模块112以及划分模块113，下面分别对该量子连通图谱的聚团划分装置110的各个功能模块的功能进行详细阐述。
[0114]
获取模块111，用于获取目标量子算法的量子连通图谱，量子连通图谱包括多个图谱节点以及两个图谱节点之间的连线，其中，图谱节点用于表示目标量子算法中的逻辑比特，连线用于表示两个逻辑比特之间的量子比特逻辑门。可以理解，该获取模块111可以用于执行上述步骤s110，关于该获取模块111的详细实现方式可以参照上述对步骤s110有关的内容。
[0115]
计算模块112，用于计算量子连通图谱中所有连线的连线中介度，并计算量子连通图谱中所有图谱节点的节点中介度。可以理解，该计算模块112可以用于执行上述步骤s120，关于该计算模块112的详细实现方式可以参照上述对步骤s120有关的内容。
[0116]
划分模块113，用于根据所有连线的连线中介度和所有图谱节点的节点中介度将量子连通图谱划分为多个不连通的目标子图谱聚团。可以理解，该划分模块113可以用于执行上述步骤s130，关于该划分模块113的详细实现方式可以参照上述对步骤s130有关的内容。
[0117]
在一种可能的实施方式中，计算模块112具体用于：
[0118]
计算每两个图谱节点在量子连通图谱中的最短连通路径；
[0119]
基于最短连通路径计算每两个图谱节点之间的连线的连线中介度。
[0120]
在一种可能的实施方式中，计算模块112具体用于：
[0121]
针对每个图谱节点，初始化赋予该图谱节点与其它图谱节点在量子连通图谱中的第一距离为0、第一节点权重为1；
[0122]
对于每一个与该图谱节点相邻的其它第一图谱节点，赋予每个第一图谱节点与该图谱节点之间的第二距离为第一距离加1、第二节点权重为第一节点权重，并将第一图谱节点到该图谱节点之间的连线构成的路径标记为该图谱节点与该第一图谱节点间的最短路径；
[0123]
对于每一个与第一图谱节点相邻的第二图谱节点，赋予第二图谱节点的第三距离为第二距离加1、第三节点权重为第二节点权重，并将第二图谱节点到第一图谱节点、第一图谱节点到该图谱节点之间的连线构成的路径标记为该图谱节点与该第二图谱节点间的最短路径。
[0124]
在一种可能的实施方式中，计算模块112具体用于：
[0125]
获取最短连通路径中根节点关联的所有叶节点，并计算所有连接叶节点和叶节点的邻接节点之间的连线的第一连线评分；
[0126]
从距离根节点最远的叶节点开始遍历，分别计算每相邻的两个叶节点之间的连线的第二连线评分，直到到达根节点时，获得所有连线的第二连线评分；
[0127]
将第一连线评分和所有第二连线评分进行求和，获得每两个图谱节点之间的连线的连线中介度。
[0128]
在一种可能的实施方式中，计算模块112具体用于：
[0129]
计算穿过每个图谱节点的最短连通路径的总数量；
[0130]
基于穿过每个图谱节点的最短连通路径的总数量，获得每个图谱节点的节点中介度。
[0131]
在一种可能的实施方式中，划分模块113具体用于：
[0132]
获取所有图谱节点中节点中介度大于所有连线的连线中介度中最大连线中介度的目标图谱节点；
[0133]
计算目标图谱节点的点对中介度，并根据点对中介度计算目标图谱节点的分裂中介度；
[0134]
如果目标图谱节点的分裂中介度大于最大连线中介度，则对目标图谱节点执行点分裂操作，否则对目标图谱节点执行去除连线操作；
[0135]
在执行点分裂操作或者去除连线操作后，检测量子连通图谱是否分裂为不连通子图；
[0136]
如果检测到量子连通图谱分裂为不连通子图，则采用modularity函数计算分裂的不连通子图的划分评估值；
[0137]
根据划分评估值重新计算所有连线的连线中介度，返回执行计算量子连通图谱中所有图谱节点的节点中介度的步骤，直到获得完全不连通的目标子图谱聚团，以将量子连通图谱划分为多个不连通的目标子图谱聚团。
[0138]
在一种可能的实施方式中，划分模块113具体用于：
[0139]
计算经过目标图谱节点和目标图谱节点的每个邻接图谱节点的连线的最短路径总数，作为目标图谱节点的点对中介度；
[0140]
将最低点对中介度对应的两个选定图谱节点确定为一个归结图谱节点，归结图谱节点的点对中介度为两个选定图谱节点的点对中介度的相加值；
[0141]
对于目标图谱节点的所有邻接图谱节点构成的子图，通过归结图谱节点和辅助图谱节点分别取代所有邻接图谱节点分别与归结图谱节点之间的连线连接，并将辅助图谱节点与两个选定图谱节点之间的点对中介度的相加值作为辅助图谱节点到归结图谱节点的点对中介度；
[0142]
重复执行预设次数的将最低点对中介度对应的两个选定图谱节点确定为一个归结图谱节点的步骤，其中，预设次数为目标图谱节点的度数减2；
[0143]
在执行预设次数的将最低点对中介度对应的两个选定图谱节点确定为一个归结图谱节点的步骤后，得到两个最终图谱节点，并将两个最终图谱节点之间的点对中介度之和确定为目标图谱节点的分裂中介度。
[0144]
在一种可能的实施方式中，划分模块113具体用于：
[0145]
获取分裂的不连通子图的分裂子图数量、每个不连通子图内部的连线数量以及每个不连通子图内部所有图谱节点的连通度之和；
[0146]
基于分裂的不连通子图的分裂子图数量、每个不连通子图内部的连线数量以及每个不连通子图内部所有图谱节点的连通度之和，采用modularity函数计算分裂的不连通子
图的划分评估值。
[0147]
基于同一发明构思，请参阅图5，示出了本技术实施例提供的用于执行上述量子连通图谱的聚团划分方法的计算机终端100的结构示意框图，该计算机终端100可以包括量子连通图谱的聚团划分装置110、机器可读存储介质120和处理器130。
[0148]
本实施例中，机器可读存储介质120与处理器130均位于计算机终端100中且二者分离设置。然而，应当理解的是，机器可读存储介质120也可以是独立于计算机终端100之外，且可以由处理器130通过总线接口来访问。可替换地，机器可读存储介质120也可以集成到处理器130中，例如，可以是高速缓存和/或通用寄存器。
[0149]
量子连通图谱的聚团划分装置110可以包括存储在机器可读存储介质120的软件功能模块(例如图4中所示的获取模块111、计算模块112以及划分模块113)，当处理器130执行量子连通图谱的聚团划分装置110中的软件功能模块时，以实现前述方法实施例提供的量子连通图谱的聚团划分方法。
[0150]
由于本技术实施例提供的计算机终端100是上述计算机终端100执行的量子连通图谱的聚团划分方法实施例的另一种实现形式，且计算机终端100可用于执行上述方法实施例提供的量子连通图谱的聚团划分方法，因此其所能获得的技术效果可参考上述方法实施例，在此不再赘述。
[0151]
以上所描述的实施例仅仅是本技术的一部分实施例，而不是全部的实施例。通常在附图中描述和示出的本技术实施例的组件可以以各种不同的配置来布置和设计。因此，在附图中提供的本技术的实施例的详细描述并非旨在限制本技术的保护范围，而仅仅是表示本技术的选定实施例。因此，本技术的保护范围应以权利要求的保护范围为准。此外，基于本技术的实施例，本领域技术人员在没有做出创造性劳动的前提下可获得的所有其它实施例，都应属于本技术保护的范围。

技术特征：
1.一种量子连通图谱的聚团划分方法，其特征在于，所述方法包括：获取目标量子算法的量子连通图谱，所述量子连通图谱包括多个图谱节点以及两个图谱节点之间的连线，其中，所述图谱节点用于表示所述目标量子算法中的逻辑比特，所述连线用于表示两个所述逻辑比特之间的量子比特逻辑门；计算所述量子连通图谱中所有连线的连线中介度，并计算所述量子连通图谱中所有图谱节点的节点中介度；根据所述所有连线的连线中介度和所述所有图谱节点的节点中介度将所述量子连通图谱划分为多个不连通的目标子图谱聚团。2.根据权利要求1所述的量子连通图谱的聚团划分方法，其特征在于，所述计算所述量子连通图谱中所有连线的连线中介度的步骤，包括：计算每两个图谱节点在所述量子连通图谱中的最短连通路径；基于所述最短连通路径计算每两个图谱节点之间的连线的连线中介度。3.根据权利要求2所述的量子连通图谱的聚团划分方法，其特征在于，所述计算每两个图谱节点在所述量子连通图谱中的最短连通路径的步骤，包括：针对每个图谱节点，初始化赋予该图谱节点与其它图谱节点在所述量子连通图谱中的第一距离为0、第一节点权重为1；对于每一个与该图谱节点相邻的其它第一图谱节点，赋予每个第一图谱节点与该图谱节点之间的第二距离为所述第一距离加1、第二节点权重为所述第一节点权重，并将所述第一图谱节点到该图谱节点之间的连线构成的路径标记为该图谱节点与该第一图谱节点间的最短路径；对于每一个与所述第一图谱节点相邻的第二图谱节点，赋予所述第二图谱节点的第三距离为所述第二距离加1、第三节点权重为所述第二节点权重，并将所述第二图谱节点到所述第一图谱节点、所述第一图谱节点到该图谱节点之间的连线构成的路径标记为该图谱节点与该第二图谱节点间的最短路径。4.根据权利要求2所述的量子连通图谱的聚团划分方法，其特征在于，所述基于所述最短连通路径计算每两个图谱节点之间的连线的连线中介度的步骤，包括：获取所述最短连通路径中根节点关联的所有叶节点，并计算所有连接所述叶节点和所述叶节点的邻接节点之间的连线的第一连线评分；从距离所述根节点最远的叶节点开始遍历，分别计算每相邻的两个叶节点之间的连线的第二连线评分，直到到达根节点时，获得所有连线的第二连线评分；将所述第一连线评分和所有第二连线评分进行求和，获得每两个图谱节点之间的连线的连线中介度。5.根据权利要求1所述的量子连通图谱的聚团划分方法，其特征在于，所述计算所述量子连通图谱中所有图谱节点的节点中介度的步骤，包括：计算穿过每个图谱节点的最短连通路径的总数量；基于所述穿过每个图谱节点的最短连通路径的总数量，获得每个所述图谱节点的节点中介度。6.根据权利要求1所述的量子连通图谱的聚团划分方法，其特征在于，所述根据所述所有连线的连线中介度和所述所有图谱节点的节点中介度将所述量子连通图谱划分为多个
不连通的目标子图谱聚团的步骤，包括：获取所述所有图谱节点中节点中介度大于所述所有连线的连线中介度中最大连线中介度的目标图谱节点；计算所述目标图谱节点的点对中介度，并根据所述点对中介度计算所述目标图谱节点的分裂中介度；如果所述目标图谱节点的分裂中介度大于所述最大连线中介度，则对所述目标图谱节点执行点分裂操作，否则对所述目标图谱节点执行去除连线操作；在执行所述点分裂操作或者所述去除连线操作后，检测所述量子连通图谱是否分裂为不连通子图；如果检测到所述量子连通图谱分裂为不连通子图，则采用modularity函数计算分裂的所述不连通子图的划分评估值；根据所述划分评估值重新计算所述所有连线的连线中介度，返回执行计算所述量子连通图谱中所有图谱节点的节点中介度的步骤，直到获得完全不连通的目标子图谱聚团，以将所述量子连通图谱划分为多个不连通的目标子图谱聚团。7.根据权利要求6所述的量子连通图谱的聚团划分方法，其特征在于，所述计算所述目标图谱节点的点对中介度，并根据所述点对中介度计算所述目标图谱节点的分裂中介度的步骤，包括：计算经过所述目标图谱节点和所述目标图谱节点的每个邻接图谱节点的连线的最短路径总数，作为所述目标图谱节点的点对中介度；将最低点对中介度对应的两个选定图谱节点确定为一个归结图谱节点，所述归结图谱节点的点对中介度为所述两个选定图谱节点的点对中介度的相加值；对于所述目标图谱节点的所有邻接图谱节点构成的子图，通过所述归结图谱节点和辅助图谱节点分别取代所述所有邻接图谱节点分别与所述归结图谱节点之间的连线连接，并将所述辅助图谱节点与所述两个选定图谱节点之间的点对中介度的相加值作为所述作为辅助图谱节点到所述归结图谱节点的点对中介度；重复执行预设次数的所述将最低点对中介度对应的两个选定图谱节点确定为一个归结图谱节点的步骤，其中，所述预设次数为所述目标图谱节点的度数减2；在执行预设次数的所述将最低点对中介度对应的两个选定图谱节点确定为一个归结图谱节点的步骤后，得到两个最终图谱节点，并将所述两个最终图谱节点之间的点对中介度之和确定为所述目标图谱节点的分裂中介度。8.根据权利要求6所述的量子连通图谱的聚团划分方法，其特征在于，所述采用modularity函数计算分裂的所述不连通子图的划分评估值的步骤，包括：获取分裂的所述不连通子图的分裂子图数量、每个所述不连通子图内部的连线数量以及每个所述不连通子图内部所有图谱节点的连通度之和；基于分裂的所述不连通子图的分裂子图数量、每个所述不连通子图内部的连线数量以及每个所述不连通子图内部所有图谱节点的连通度之和，采用modularity函数计算分裂的所述不连通子图的划分评估值。9.一种量子连通图谱的聚团划分装置，其特征在于，所述装置包括：获取模块，用于获取目标量子算法的量子连通图谱，所述量子连通图谱包括多个图谱
节点以及两个图谱节点之间的连线，其中，所述图谱节点用于表示所述目标量子算法中的逻辑比特，所述连线用于表示两个所述逻辑比特之间的量子比特逻辑门；计算模块，用于计算所述量子连通图谱中所有连线的连线中介度，并计算所述量子连通图谱中所有图谱节点的节点中介度；划分模块，用于根据所述所有连线的连线中介度和所述所有图谱节点的节点中介度将所述量子连通图谱划分为多个不连通的目标子图谱聚团。10.一种计算机终端，其特征在于，包括机器可读存储介质和处理器，所述机器可读存储介质中存储有计算机程序，所述处理器被设置为运行所述计算机程序以执行权利要求1-8中任意一项中所述的量子连通图谱的聚团划分方法。11.一种计算机可读存储介质，其特征在于，所述计算机可读存储介质中存储有计算机程序，当所述计算机程序被计算机执行时，实现权利要求1-8中任意一项中所述的量子连通图谱的聚团划分方法。

技术总结
本申请实施例提供一种量子连通图谱的聚团划分方法、装置、终端及存储介质，通过计算量子连通图谱中所有连线的连线中介度，并计算量子连通图谱中所有图谱节点的节点中介度，从而根据所有连线的连线中介度和所有图谱节点的节点中介度将量子连通图谱划分为多个不连通的目标子图谱聚团。如此，通过将量子连通图谱划分为多个不连通的目标子图谱聚团，从而可以便于后续单独基于每个不连通的目标子图谱聚团进行后续的量子算法设计，提高算法运行效果。果。果。


技术研发人员：孔维成
受保护的技术使用者：合肥本源量子计算科技有限责任公司
技术研发日：2020.11.09
技术公布日：2022/5/25