Physics Division, National Center for Theoretical Sciences, National Taiwan University, Taipei, 10617, Taiwan.
Department of Computer Science and Information Engineering, National Kaohsiung University of Science and Technology, Kaohsiung, 807618, Taiwan.
Sci Rep. 2023 Mar 14;13(1):4205. doi: 10.1038/s41598-023-30600-4.
A dominating set of a graph [Formula: see text] is a subset U of its vertices V, such that any vertex of G is either in U, or has a neighbor in U. The dominating-set problem is to find a minimum dominating set in G. Dominating sets are of critical importance for various types of networks/graphs, and find therefore potential applications in many fields. Particularly, in the area of communication, dominating sets are prominently used in the efficient organization of large-scale wireless ad hoc and sensor networks. However, the dominating set problem is also a hard optimization problem and thus currently is not efficiently solvable on classical computers. Here, we propose a biomolecular and a quantum algorithm for this problem, where the quantum algorithm provides a quadratic speedup over any classical algorithm. We show that the dominating set problem can be solved in [Formula: see text] queries by our proposed quantum algorithm, where n is the number of vertices in G. We also demonstrate that our quantum algorithm is the best known procedure to date for this problem. We confirm the correctness of our algorithm by executing it on IBM Quantum's qasm simulator and the Brooklyn superconducting quantum device. And lastly, we show that molecular solutions obtained from solving the dominating set problem are represented in terms of a unit vector in a finite-dimensional Hilbert space.
图 [公式：见正文] 的支配集是其顶点 V 的子集 U，使得 G 的任何顶点要么在 U 中，要么有一个邻居在 U 中。支配集问题是在 G 中找到一个最小的支配集。支配集对于各种类型的网络/图至关重要，因此在许多领域都有潜在的应用。特别是在通信领域，支配集在大规模无线自组织和传感器网络的有效组织中得到了广泛应用。然而，支配集问题也是一个困难的优化问题，因此目前在经典计算机上无法有效地解决。在这里，我们提出了一种针对该问题的生物分子和量子算法，其中量子算法提供了相对于任何经典算法的二次加速。我们表明，我们的量子算法可以在 [公式：见正文] 查询中解决支配集问题，其中 n 是 G 中顶点的数量。我们还证明了我们的量子算法是迄今为止针对该问题的最佳已知程序。我们通过在 IBM Quantum 的 qasm 模拟器和布鲁克林超导量子设备上执行该算法来确认算法的正确性。最后，我们表明，从解决支配集问题中获得的分子解决方案表示为有限维希尔伯特空间中的单位向量。
