Quantum Algorithm for Approximating Maximum Independent Sets  

作　　者：Hongye Yu Frank Wilczek Biao Wu 余泓烨;Frank Wilczek;吴飙(Department of Physics and Astronomy,Stony Brook University,Stony Brook,NY 11794,USA;Center for Theoretical Physics,Massachusetts Institute of Technology,Cambridge,Massachusetts 02139,USA;D.Lee Institute,Shanghai Jiao Tong University,Shanghai 200240,China;Wilczek Quantum Center,School of Physics and Astronomy,Shanghai Jiao Tong University,Shanghai 200240,China;Department of Physics,Stockholm University,Stockholm SE-10691,Sweden;Department of Physics and Origins Project,Arizona State University,Tempe AZ 25287,USA;International Center for Quantum Materials,School of Physics,Peking University,Beijing 100871,China;Collaborative Innovation Center of Quantum Matter,Beijing 100871,China)

机构地区：[1]Department of Physics and Astronomy,Stony Brook University,Stony Brook,NY 11794,USA [2]Center for Theoretical Physics,Massachusetts Institute of Technology,Cambridge,Massachusetts 02139,USA [3]D.Lee Institute,Shanghai Jiao Tong University,Shanghai 200240,China [4]Wilczek Quantum Center,School of Physics and Astronomy,Shanghai Jiao Tong University,Shanghai 200240,China [5]Department of Physics,Stockholm University,Stockholm SE-10691,Sweden [6]Department of Physics and Origins Project,Arizona State University,Tempe AZ 25287,USA [7]International Center for Quantum Materials,School of Physics,Peking University,Beijing 100871,China [8]Collaborative Innovation Center of Quantum Matter,Beijing 100871,China

出　　处：《Chinese Physics Letters》2021年第3期17-21,共5页中国物理快报（英文版）

基　　金：supported in part by the U.S.Department of Energy(Grant No.DE-SC0012567);the European Research Council(Grant No.742104);the Swedish Research Council(Grant No.335–2014-7424);supported by the National Key R&D Program of China(Grant Nos.2017YFA0303302 and 2018YFA0305602);the National Natural Science Foundation of China(Grant No.11921005);Shanghai Municipal Science and Technology Major Project(Grant No.2019SHZDZX01)。

摘　　要：We present a quantum algorithm for approximating maximum independent sets of a graph based on quantum non-Abelian adiabatic mixing in the sub-Hilbert space of degenerate ground states,which generates quantum annealing in a secondary Hamiltonian.For both sparse and dense random graphs G,numerical simulation suggests that our algorithm on average finds an independent set of size close to the maximum size α(G) in low polynomial time.The best classical algorithms,by contrast,produce independent sets of size about half of α(G)in polynomial time.

关 键 词：QUANTUM POLYNOMIAL INDEPENDENT 

分 类 号：O157.5[理学—数学]