Quantum cooperative search algorithm for 3-SAT

Sheng Tzong Cheng, Ming Hung Tao

研究成果: Article同行評審

7 引文 斯高帕斯(Scopus)


Grover's search algorithm, one of the most popular quantum algorithms, provides a good solution to solve NP complexity problems, but requires a large number of quantum bits (qubits) for its functionality. In this paper, a novel algorithm called quantum cooperative search is proposed to make Grover's search algorithm work on 3-SAT problems with a small number of qubits. The proposed algorithm replaces some qubits with classical bits and finds assignments to these classical bits using the traditional 3-SAT algorithms including evolutionary algorithms and heuristic local search algorithms. In addition, the optimal configuration of the proposed algorithm is suggested by mathematical analysis. The experimental results show that the quantum cooperative search algorithm composed by Grover's search and heuristic local search performs better than other pure traditional 3-SAT algorithms in most cases. The mathematical analysis of the appropriate number of qubits is also verified by the experiments.

頁(從 - 到)123-136
期刊Journal of Computer and System Sciences
出版狀態Published - 2007 2月

All Science Journal Classification (ASJC) codes

  • 理論電腦科學
  • 電腦網路與通信
  • 計算機理論與數學
  • 應用數學


深入研究「Quantum cooperative search algorithm for 3-SAT」主題。共同形成了獨特的指紋。