Quantum speedup in solving the maximal-clique problem

doi:10.1103/PhysRevA.97.032344

	Quantum speedup in solving the maximal-clique problem
	Chang, Weng-Long 1; Yu, Qi 2,3; Li, Zhaokai 2,3,4; Chen, Jiahui 2,3,5,6; Peng, Xinhua 2,3,4,7; Feng, Mang 7,8,9
刊名	PHYSICAL REVIEW A
	2018-03-29
卷号	97 期号:3
ISSN号	2469-9926
DOI	10.1103/PhysRevA.97.032344
文献子类	Article
英文摘要	The maximal-clique problem, to find the maximally sized clique in a given graph, is classically an NP-complete computational problem, which has potential applications ranging from electrical engineering, computational chemistry, and bioinformatics to social networks. Here we develop a quantum algorithm to solve the maximal-clique problem for any graph G with n vertices with quadratic speedup over its classical counterparts, where the time and spatial complexities are reduced to, respectively, O(root 2(n)) and O(n(2)). With respect to oracle-related quantum algorithms for the NP-complete problems, we identify our algorithm as optimal. To justify the feasibility of the proposed quantum algorithm, we successfully solve a typical clique problem for a graph G with two vertices and one edge by carrying out a nuclear magnetic resonance experiment involving four qubits.
WOS关键词	NUCLEAR-MAGNETIC-RESONANCE ; ALGORITHM ; REALIZATION
WOS研究方向	Optics ; Physics
语种	英语
出版者	AMER PHYSICAL SOC
WOS记录号	WOS:000428647300006
资助机构	National Key Basic Research Program of China(2013CB921800 ; National Key Basic Research Program of China(2013CB921800 ; National Science Fund for Distinguished Young Scholars of China(11425523) ; National Science Fund for Distinguished Young Scholars of China(11425523) ; National Natural Science Foundation of China(11674360 ; National Natural Science Foundation of China(11674360 ; Strategic Priority Research Program (B) of the CAS(XDB01030400 ; Strategic Priority Research Program (B) of the CAS(XDB01030400 ; Key Research Program of Frontier Sciences of the CAS(QYZDY-SSW-SLH004) ; Key Research Program of Frontier Sciences of the CAS(QYZDY-SSW-SLH004) ; 2014CB848700 ; 2014CB848700 ; 11375167 ; 11375167 ; XDB21010100) ; XDB21010100) ; 2017YFA0304503) ; 2017YFA0304503) ; 11227901) ; 11227901) ; National Key Basic Research Program of China(2013CB921800 ; National Key Basic Research Program of China(2013CB921800 ; National Science Fund for Distinguished Young Scholars of China(11425523) ; National Science Fund for Distinguished Young Scholars of China(11425523) ; National Natural Science Foundation of China(11674360 ; National Natural Science Foundation of China(11674360 ; Strategic Priority Research Program (B) of the CAS(XDB01030400 ; Strategic Priority Research Program (B) of the CAS(XDB01030400 ; Key Research Program of Frontier Sciences of the CAS(QYZDY-SSW-SLH004) ; Key Research Program of Frontier Sciences of the CAS(QYZDY-SSW-SLH004) ; 2014CB848700 ; 2014CB848700 ; 11375167 ; 11375167 ; XDB21010100) ; XDB21010100) ; 2017YFA0304503) ; 2017YFA0304503) ; 11227901) ; 11227901) ; National Key Basic Research Program of China(2013CB921800 ; National Key Basic Research Program of China(2013CB921800 ; National Science Fund for Distinguished Young Scholars of China(11425523) ; National Science Fund for Distinguished Young Scholars of China(11425523) ; National Natural Science Foundation of China(11674360 ; National Natural Science Foundation of China(11674360 ; Strategic Priority Research Program (B) of the CAS(XDB01030400 ; Strategic Priority Research Program (B) of the CAS(XDB01030400 ; Key Research Program of Frontier Sciences of the CAS(QYZDY-SSW-SLH004) ; Key Research Program of Frontier Sciences of the CAS(QYZDY-SSW-SLH004) ; 2014CB848700 ; 2014CB848700 ; 11375167 ; 11375167 ; XDB21010100) ; XDB21010100) ; 2017YFA0304503) ; 2017YFA0304503) ; 11227901) ; 11227901) ; National Key Basic Research Program of China(2013CB921800 ; National Key Basic Research Program of China(2013CB921800 ; National Science Fund for Distinguished Young Scholars of China(11425523) ; National Science Fund for Distinguished Young Scholars of China(11425523) ; National Natural Science Foundation of China(11674360 ; National Natural Science Foundation of China(11674360 ; Strategic Priority Research Program (B) of the CAS(XDB01030400 ; Strategic Priority Research Program (B) of the CAS(XDB01030400 ; Key Research Program of Frontier Sciences of the CAS(QYZDY-SSW-SLH004) ; Key Research Program of Frontier Sciences of the CAS(QYZDY-SSW-SLH004) ; 2014CB848700 ; 2014CB848700 ; 11375167 ; 11375167 ; XDB21010100) ; XDB21010100) ; 2017YFA0304503) ; 2017YFA0304503) ; 11227901) ; 11227901)
内容类型	期刊论文
源URL	[http://ir.wipm.ac.cn/handle/112942/12954]
专题	中国科学院武汉物理与数学研究所
通讯作者	Chang, Weng-Long; Peng, Xinhua; Feng, Mang
作者单位	1.Natl Kaohsiung Univ Appl Sci, Dept Comp Sci, Kaohsiung 80778, Taiwan 2.Univ Sci & Technol China, CAS Key Lab Microscale Magnet Resonance, Hefei 230026, Anhui, Peoples R China 3.Univ Sci & Technol China, Dept Modern Phys, Hefei 230026, Anhui, Peoples R China 4.Univ Sci & Technol China, Synerget Innovat Ctr Quantum Informat & Quantum P, Hefei 230026, Anhui, Peoples R China 5.Univ Waterloo, Inst Quantum Comp, Waterloo, ON N2L 3G1, Canada 6.Univ Waterloo, Dept Phys & Astron, Waterloo, ON N2L 3G1, Canada 7.Hunan Normal Univ, Synerget Innovat Ctr Quantum Effects & Applicat, Changsha 410081, Hunan, Peoples R China 8.Chinese Acad Sci, Wuhan Inst Phys & Math, State Key Lab Magnet Resonance & Atom & Mol Phys, Wuhan 430071, Hubei, Peoples R China 9.Zhejiang Normal Univ, Dept Phys, Jinhua 321004, Peoples R China
推荐引用方式 GB/T 7714	Chang, Weng-Long,Yu, Qi,Li, Zhaokai,et al. Quantum speedup in solving the maximal-clique problem[J]. PHYSICAL REVIEW A,2018,97(3).
APA	Chang, Weng-Long,Yu, Qi,Li, Zhaokai,Chen, Jiahui,Peng, Xinhua,&Feng, Mang.(2018).Quantum speedup in solving the maximal-clique problem.PHYSICAL REVIEW A,97(3).
MLA	Chang, Weng-Long,et al."Quantum speedup in solving the maximal-clique problem".PHYSICAL REVIEW A 97.3(2018).