Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Quantum Hybrid Algorithm for Solving SAT Problem

Charles Varmantchaonala Moudina, Jean Louis Ebongue Kedieng Fendji, J.-P. Tchapet Njafa, Marcellin Atemkeng

Published Jan 1, 2022• 1 citation
Publisher
DOI
10.2139/ssrn.4216868

Related papers

Quantum hybrid algorithm for solving SAT problem

Charles Varmantchaonala Moudina, Jean Louis Ebongue Kedieng Fendji, J.-P. Tchapet Njafa +1 more

Engineering Applications of Artificial Intelligence•Mar 2, 2023•7 citations

Distributed quantum-classical hybrid algorithm for solving K-SAT problem

Huaijing Huang, Daowen Qiu, Le Luo +1 more

Recently, Dunjko et al.(PRL, 2018) proposed an algorithm for accelerating the solution of 3-satisfiability problems using a small-scale quantum computer. In this paper, we design a distributed quantum-classical hybrid algorithm for solving K-satisfiability problems. Under resource-constrained conditions, our algorithm achieves a significant acceleration in the core term of the exponential time complexity. The proposed algorithm is a generalization of the algorithm by Dunjko et al. Compared with their algorithm, our algorithm requires a smaller number of qubits. More importantly, the proposed algorithm does not rely on any quantum communication.

quant-pharXiv:2604.14057•Apr 16, 2026•0 citations

A quantum algorithm for solving the 3-SAT problem

Lily Chen

The method in this paper is wrong.

arXiv:1210.4321•Oct 16, 2012•0 citations

A Quantum Inspired Particle Swarm Algorithm for Solving the Maximum Satisfiability Problem

Abdesslem Layeb

Abstract. In this paper we investigate the use of quantum particle swarm optimization (QPSO) principles to resolve the satisfiability problem. We describe QPSOSAT, a new iterative approach for solving the well known Maximum Satisfiability problem (MAX-SAT). This latter has been shown to be NP-hard if the number of variables per clause is greater than 3. The basic idea is to harness the optimization capabilities of QPSO algorithm to achieve good quality solutions for Max Sat problem. To enhance the efficiency of the QPSO algorithm, a local search has been used. The obtained results are very promising and show the feasibility and effectiveness of the proposed hybrid approach.

International Journal of Combinatorial Optimization Problems and Informatics.•Feb 5, 2010•6 citations

Three “quantum” algorithms to solve 3-SAT

Alberto Leporati, Sara Felloni

Theoretical Computer Science•Dec 1, 2006•17 citations

Quantum Solution for the 3-SAT Problem Based on IBM Q

Ying Zhang, Yuxiang Bian, Qiang Fan +1 more

Lecture notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering•Jan 1, 2020•3 citations
Recently, Dunjko et al.(PRL, 2018) proposed an algorithm for accelerating the solution of 3-satisfiability problems using a small-scale quantum computer. In this paper, we design a distributed quantum-classical hybrid algorithm for solving K-satisfiability problems. Under resource-constrained conditions, our algorithm achieves a significant acceleration in the core term of the exponential time complexity. The proposed algorithm is a generalization of the algorithm by Dunjko et al. Compared with their algorithm, our algorithm requires a smaller number of qubits. More importantly, the proposed algorithm does not rely on any quantum communication.
Abstract. In this paper we investigate the use of quantum particle swarm optimization (QPSO) principles to resolve the satisfiability problem. We describe QPSOSAT, a new iterative approach for solving the well known Maximum Satisfiability problem (MAX-SAT). This latter has been shown to be NP-hard if the number of variables per clause is greater than 3. The basic idea is to harness the optimization capabilities of QPSO algorithm to achieve good quality solutions for Max Sat problem. To enhance the efficiency of the QPSO algorithm, a local search has been used. The obtained results are very promising and show the feasibility and effectiveness of the proposed hybrid approach.