中文题目：无向图最小支配集的量子算法及线路设计

论文题目：Quantum algorithm for minimum dominating set problem with circuit design

录用期刊/会议：Chinese Physics B (中科院大类四区，JCR Q2)

原文DOI：10.1088/1674-1056/ad02e5

原文链接：https://iopscience.iop.org/article/10.1088/1674-1056/ad02e5/meta

作者列表：

1）张皓颖 中国石油大学（北京）人工智能学院 计算机科学与技术 硕21

2）王绍轩 中国石油大学（北京）人工智能学院 计算机科学与技术 硕21

3）刘新建 中国石油大学（北京）人工智能学院 计算机科学与技术 硕21

4）沈颖童 中国石油大学（北京）人工智能学院 计算机科学与技术 硕22

5）王玉坤 中国石油大学（北京）人工智能学院 计算机科学与技术系 教师

文章简介:

本文提出了一种求解无向图最小支配集问题的量子算法，该问题是一个著名的NP完全问题，对于图论和组合优化领域具有重要意义。文章整体通过量子算法获得极小支配集，通过经典后处理获得最小支配集。本文所提出的算法利用Grover搜索算法的特性，通过设计特定的量子门和电路结构来识别非有向图中的最小支配集。由于最小支配集问题的解的数量未知，直接应用原始的Grover搜索算法面临挑战。为了解决这一问题，文章引入了一种交换测试方法来估计所需的迭代次数。这为利用Grover算法求解任意目标解数量未知问题提供了方向。

摘要:

本文主要研究了在无向图中寻找最小支配集的NP完全问题。为了加快搜索过程，提出了一种基于Grover搜索的支配集搜索算法。然而，利用该方法直接解决最小支配集问题面临一个困难，即无法精确获得算法的迭代次数，这使得直接使用原始的Grover的搜索不可能。因此，引入了一种SWAT-TEST方法来确定所需的迭代次数。算法的查询复杂度为O (1.414ⁿ)，空间复杂度为O (n)。为了验证所提出的方法，我们采用qiskit软件包对量子电路进行了模拟，得到了预期的结果。

主要内容:

通过对支配集的性质进行分析，我们将量子比特按照不同的功能分为了7类，并将算法分为支配集探测和极小支配集探测两个部分，设计了如图1所示的量子线路总体框架。

图1 量子线路框架

支配集探测的核心思想是检测图中的每个顶点能否被支配。判断该顶点及其所有邻接点中是否存在支配点。极小支配集探测模块的核心思想是首先判断顶点在成为非支配点后是否仍然能够被支配，然后判断顶点成为非支配点后，其所有邻接点是否能被支配。然后我们将判断的思想映射到量子线路中。

实验结果及分析:

我们对3个顶点2条边的无向图进行了实验，所设计的量子线路如图2所示。其中包括支配集探测、极小支配集探测和反演算子三部分。当运行完此量子线路之后，可以通过测量量子比特的状态来确定极小支配集的组合，然后借助经典算法找到最终的解。

图2 三顶点量子线路

模拟结果如图3所示，横坐标表示量子态，对应到无向图的顶点集合，纵坐标表示该量子态被测量得到的概率。算法执行完毕后，以高概率获得两个极小支配集。通过Grover量子搜索算法获取所有的极小支配集后，利用经典算法在这些集合中进行最小支配集的搜索，最终发现{A}是最小的支配集。

图3 实验结果

结论:

我们提出了一种利用Grover的搜索算法来解决在无向图中寻找最小支配集的问题，该算法相对经典的穷举算法产生了平方级的加速。为了展示整个算法的有效性和效率，我们使用Python和IBM开发的qiskit包进行了模拟。实验展示了算法在具有3个和8个顶点的无向图上的性能，展示了该算法在获得高概率的次要支配集方面的准确性。随后，采用经典的后处理方法将这些次要支配集转化为最小支配集，显著减少了搜索空间，并在短时间内实现了精确解。

通讯作者简介:

王玉坤，女，博士，人工智能学院计算机系助理教授。研究方向为量子计算，量子密码及量子信息基本理论，主要包括：量子机器学习，经典困难问题量子算法加速，量子线路优化与映射，量子密码协议设计及安全性证明，设备不可信量子信息处理等。主持国家自然基金青年基金，密码管理局密码科技国家重点实验室面上项目，校人才启动基金，在国内外著名期刊和会议发表SCI检索的学术论文30余篇。担任多个国际顶级期刊审稿人。