Quantum cooperative search algorithm for 3-SAT

Sheng-Tzong Cheng, Ming Hung Tao

Research output: Contribution to journalArticle

4 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 1

Fingerprint

Search Algorithm
Quantum Algorithms
Heuristic Search
Mathematical Analysis
Local Search Algorithm
Local Search
Evolutionary Algorithms
Assignment
Configuration
Experimental Results
Evolutionary algorithms
Experiment

All Science Journal Classification (ASJC) codes

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

Cite this

@article{f20a7843945f4012a87b92bac67eaf4f,
title = "Quantum cooperative search algorithm for 3-SAT",
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.",
author = "Sheng-Tzong Cheng and Tao, {Ming Hung}",
year = "2007",
month = "2",
day = "1",
doi = "10.1016/j.jcss.2006.09.003",
language = "English",
volume = "73",
pages = "123--136",
journal = "Journal of Computer and System Sciences",
issn = "0022-0000",
publisher = "Academic Press Inc.",
number = "1",

}

Quantum cooperative search algorithm for 3-SAT. / Cheng, Sheng-Tzong; Tao, Ming Hung.

In: Journal of Computer and System Sciences, Vol. 73, No. 1, 01.02.2007, p. 123-136.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Quantum cooperative search algorithm for 3-SAT

AU - Cheng, Sheng-Tzong

AU - Tao, Ming Hung

PY - 2007/2/1

Y1 - 2007/2/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=33751008049&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33751008049&partnerID=8YFLogxK

U2 - 10.1016/j.jcss.2006.09.003

DO - 10.1016/j.jcss.2006.09.003

M3 - Article

AN - SCOPUS:33751008049

VL - 73

SP - 123

EP - 136

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

SN - 0022-0000

IS - 1

ER -