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

Lecture notes in computer science

A New Quantum Evolutionary Local Search Algorithm for MAX 3-SAT Problem

Abdesslem Layeb, Djamel Eddine Saïdouni

Published Jan 1, 2008• 20 citations
Publisher
DOI
10.1007/978-3-540-87656-4_22

Related papers

Quantum cooperative search algorithm for 3-SAT

Sheng-Tzong Cheng, Ming‐Hung Tao

Journal of Computer and System Sciences•Oct 20, 2006•17 citations

A Hybrid Quantum Genetic Algorithm and Local Search based DPLL for Max 3-SAT Problems

Abdesslem Layeb, Djamel Eddine Saïdouni

Abstract: In this paper, we present a new framework for combining complete and incomplete methods in order to deal with the Max Sat problem. The objective is to find the best assignment for a set of Boolean variables, which gives the maximum of verified clauses in a Boolean formula. Unfortunately, this problem has been shown to be NP-hard (non-deterministic polynomial-time hard) if the number of variables per clause is greater than 3. The proposed approach is based on quantum inspired genetic principles and the well known exact algorithm DPLL. The underlying idea is to harness the optimization capabilities of quantum genetic algorithm to achieve good quality solutions for Max SAT problem. A new local search based on DPLL algorithm has been embodied in the quantum genetic algorithm leading to an efficient hybrid framework which achieves better balance between diversification and intensification search. The obtained results are very encouraging and show the feasibility and effectiveness of the proposed hybrid approach.

Applied Mathematics & Information Sciences•Sep 18, 2013•1 citation

A parallel spatial quantum search algorithm applied to the 3-SAT problem

Miguel A. Hernández Barreto, Gonzalo Abal, Sergio Nesmachnow

•Jan 1, 2011•2 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

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

Using an Evolutionary Algorithm to Create (MAX)-3SAT QUBOs

Sebastian Zielinski, Maximilian Zorn, Thomas Gabor +2 more

A common way of solving satisfiability instances with quantum methods is to transform these instances into instances of QUBO. State-of-the-art transformations from MAX-3SAT to QUBO work by mapping clauses of a 3SAT formula associated with the MAX-3SAT instance to an instance of QUBO and combining the resulting QUBOs into a single QUBO instance representing the whole MAX-3SAT instance. As creating these transformations is currently done manually or via exhaustive search methods and is, therefore, algorithmically inefficient, we see potential for including search-based optimization. In this paper, we propose two methods of using evolutionary algorithms to create QUBO representations of MAX-3SAT problems automatically. We evaluate our created QUBOs on 500 and 1000-clause 3SAT formulae and find competitive performance to state-of-the-art baselines when using both classical and quantum annealing solvers.

arXiv:2405.09272•Genetic and Evolutionary Computation Conference Companion (GECCO Companion)•Jul 14, 2024•1 citation
Abstract: In this paper, we present a new framework for combining complete and incomplete methods in order to deal with the Max Sat problem. The objective is to find the best assignment for a set of Boolean variables, which gives the maximum of verified clauses in a Boolean formula. Unfortunately, this problem has been shown to be NP-hard (non-deterministic polynomial-time hard) if the number of variables per clause is greater than 3. The proposed approach is based on quantum inspired genetic principles and the well known exact algorithm DPLL. The underlying idea is to harness the optimization capabilities of quantum genetic algorithm to achieve good quality solutions for Max SAT problem. A new local search based on DPLL algorithm has been embodied in the quantum genetic algorithm leading to an efficient hybrid framework which achieves better balance between diversification and intensification search. The obtained results are very encouraging and show the feasibility and effectiveness of the proposed hybrid approach.
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.
A common way of solving satisfiability instances with quantum methods is to transform these instances into instances of QUBO. State-of-the-art transformations from MAX-3SAT to QUBO work by mapping clauses of a 3SAT formula associated with the MAX-3SAT instance to an instance of QUBO and combining the resulting QUBOs into a single QUBO instance representing the whole MAX-3SAT instance. As creating these transformations is currently done manually or via exhaustive search methods and is, therefore, algorithmically inefficient, we see potential for including search-based optimization. In this paper, we propose two methods of using evolutionary algorithms to create QUBO representations of MAX-3SAT problems automatically. We evaluate our created QUBOs on 500 and 1000-clause 3SAT formulae and find competitive performance to state-of-the-art baselines when using both classical and quantum annealing solvers.