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...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.展开更多
We present a rigorous proof that quantum circuit algorithm can be transformed into quantum adiabatic algorithm with the exact same time complexity. This means that from a quantum circuit algorithm of L gates we can co...We present a rigorous proof that quantum circuit algorithm can be transformed into quantum adiabatic algorithm with the exact same time complexity. This means that from a quantum circuit algorithm of L gates we can construct a quantum adiabatic algorithm with time complexity of O（L）. Additionally, our construction shows that one may exponentially speed up some quantum adiabatic algorithms by properly choosing an evolution path.展开更多
基金supported in part by the U.S.Department of Energy(Grant No.DE-SC0012567)the European Research Council(Grant No.742104)+3 种基金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.
基金Supported by the The National Key Research and Development Program of China under Grant Nos 2017YFA0303302 and 2018YFA030562the National Natural Science Foundation of China under Grant Nos 11334001 and 11429402
文摘We present a rigorous proof that quantum circuit algorithm can be transformed into quantum adiabatic algorithm with the exact same time complexity. This means that from a quantum circuit algorithm of L gates we can construct a quantum adiabatic algorithm with time complexity of O（L）. Additionally, our construction shows that one may exponentially speed up some quantum adiabatic algorithms by properly choosing an evolution path.
