Quantum cooperative search algorithm for 3-SAT

Sheng Tzong Cheng, Ming Hung Tao

Research output: Contribution to journalArticlepeer-review

5 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)123-136
Number of pages14
JournalJournal of Computer and System Sciences
Volume73
Issue number1
DOIs
Publication statusPublished - 2007 Feb

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Quantum cooperative search algorithm for 3-SAT'. Together they form a unique fingerprint.

Cite this