A Parallel Quantum Algorithm for the Satisfiability Problem

作     者：LIU Wen-Zhang ZHANG Jing-Fu LONG Gui-Lu 

作者机构：Key Laboratory for Atomic and Molecular NanoSciences and Department of Physics Tsinghua University Beijing 100084 China Tsinghua National Laboratory for Information Science and Technology Beijing 100084 China 

出 版 物：《Communications in Theoretical Physics》 (理论物理通讯（英文版）)

年 卷 期：2008年第49卷第3期

页      面：629-630页

核心收录：

学科分类：0809[工学-电子科学与技术（可授工学、理学学位）] 07[理学] 070205[理学-凝聚态物理] 08[工学] 0702[理学-物理学] 

基　　金：supported by 973 Program under Grant No.2006CB921106 National Natural Science Foundation of China under Grant No.60635040 the Key Grant Project of the Ministry of Education under Grant No.306020 

主　　题：satisfiability problem quantum search algorithm long algorithm 

摘      要：In this paper we present a classical parallel quantum algorithm for the satisfiability problem. We have exploited the classical parallelism of quantum algorithms developed in [G.L. Long and L. Xiao, Phys. Rev. A 69 （2004） 052303], so that additional acceleration can be gained by using classical parallelism. The quantum algorithm first estimates the number of solutions using the quantum counting algorithm, and then by using the quantum searching algorithm, the explicit solutions are found.