A Parallel Quantum Algorithm for the Satisfiability Problem |
| |
| Authors: | LIU Wen-Zhang ZHANG Jing-Fu LONG Gui-Lu |
| |
| Institution: | 1. Key Laboratory for Atomic and Molecular NanoSciences and
Department of Physics, Tsinghua University, Beijing 100084, China
;2. Tsinghua National Laboratory for Information Science and
Technology, Beijing 100084, China |
| |
| Abstract: | 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. |
| |
| Keywords: | satisfiability problem quantum search algorithm long algorithm |
| 本文献已被 维普 等数据库收录！ |
| 点击此处可从《理论物理通讯》浏览原始摘要信息 |
| 点击此处可从《理论物理通讯》下载免费的PDF全文 |
|
