首页|Quantum algorithm for minimum dominating set problem with circuit design
Quantum algorithm for minimum dominating set problem with circuit design
扫码查看
点击上方二维码区域，可以放大扫码查看
原文链接
NETL
NSTL
万方数据
维普
Using quantum algorithms to solve various problems has attracted widespread attention with the development of quantum computing.Researchers are particularly interested in using the acceleration properties of quantum algorithms to solve NP-complete problems.This paper focuses on the well-known NP-complete problem of finding the minimum dominating set in undirected graphs.To expedite the search process,a quantum algorithm employing Grover's search is proposed.However,a challenge arises from the unknown number of solutions for the minimum dominating set,rendering direct usage of original Grover's search impossible.Thus,a swap test method is introduced to ascertain the number of iterations required.The oracle,diffusion operators,and swap test are designed with achievable quantum gates.The query complexity is O(1.414n)and the space complexity is O(n).To validate the proposed approach,qiskit software package is employed to simulate the quantum circuit,yielding the anticipated results.
quantum algorithmcircuit designminimum dominating set
张皓颖、王绍轩、刘新建、沈颖童、王玉坤
展开 >
Beijing Key Laboratory of Petroleum Data Mining,China University of Petroleum,Beijing 102249,China
State Key Laboratory of Cryptology,P.O.Box 5159,Beijing 100878,China
National Natural Science Foundation of ChinaScience Foundation of China University of Petroleum,BeijingState Key Laboratory of Cryptology
NETL
NSTL
万方数据
维普
