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 a...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.414^(n))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.展开更多
为了使“区间”形式加以表述的不确定信息的提取具有侧重性,需提取出对象(属性)集对应的属性(对象)区间集。本文在模糊形式背景中,通过引入2个阈值,将单边区间集与经典半概念结合,提取出属性(对象)集对应的对象(属性)区间集,从而提出区...为了使“区间”形式加以表述的不确定信息的提取具有侧重性,需提取出对象(属性)集对应的属性(对象)区间集。本文在模糊形式背景中,通过引入2个阈值,将单边区间集与经典半概念结合,提取出属性(对象)集对应的对象(属性)区间集,从而提出区间集外延–集合内涵(集合外延–区间集内涵)(interval set extent-set intent(set extent-interval set intent),ISE-SI(SE-ISI))型单边区间集模糊半概念。全体ISE-SI(SE-ISI)型单边区间集模糊半概念构成格,并给出基于格搜寻全体ISE-SI(SE-ISI)型单边区间集模糊半概念的算法。通过与已有成果对比,显示出这2种知识表示形式的多方优势。本文所得结果在知识表示及提取方法上具有适用范围广、实际应用强等优点。展开更多
基金Project supported by the National Natural Science Foundation of China(Grant No.62101600)the Science Foundation of China University of Petroleum,Beijing(Grant No.2462021YJRC008)the State Key Laboratory of Cryptology(Grant No.MMKFKT202109).
文摘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.414^(n))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.
文摘为了使“区间”形式加以表述的不确定信息的提取具有侧重性,需提取出对象(属性)集对应的属性(对象)区间集。本文在模糊形式背景中,通过引入2个阈值,将单边区间集与经典半概念结合,提取出属性(对象)集对应的对象(属性)区间集,从而提出区间集外延–集合内涵(集合外延–区间集内涵)(interval set extent-set intent(set extent-interval set intent),ISE-SI(SE-ISI))型单边区间集模糊半概念。全体ISE-SI(SE-ISI)型单边区间集模糊半概念构成格,并给出基于格搜寻全体ISE-SI(SE-ISI)型单边区间集模糊半概念的算法。通过与已有成果对比,显示出这2种知识表示形式的多方优势。本文所得结果在知识表示及提取方法上具有适用范围广、实际应用强等优点。