A Parallel Quantum Algorithm for the Satisfiability Problem |
| |
Authors: | LIU Wen-Zhang ZHANG Jing-Fu LONG Gui-Lu |
| |
Affiliation: | 1. Key Laboratory for Atomic and Molecular NanoSciences andDepartment of Physics, Tsinghua University, Beijing 100084, China;2. Tsinghua National Laboratory for Information Science andTechnology, 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 developedin [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 |
本文献已被 维普 万方数据 等数据库收录! |
| 点击此处可从《理论物理通讯》浏览原始摘要信息 |
|
点击此处可从《理论物理通讯》下载全文 |
|