Quantum Algorithm for Maximum Satisfiability
Authors:
- 1 May 2022
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 27-34
Abstract
Satisfiability (SAT) problem in engineering and computer science is to find the set of assignment values of input variables for the given Boolean function that evaluate this function to TRUE or prove that such satisfying values do not exist. For POS SAT Problem, we propose a novel quantum algorithm for the maximum satisfiability (MAX-SAT) which returns the maximum number of OR terms that are satisfied for the SAT-unsatisfiable function, providing us with the information how far the given Boolean function is from the SAT satisfaction. We use Grovers algorithm with a new block called quantum counter in the oracle circuit.Keywords
This publication has 22 references indexed in Scilit:
- Hybrid of genetic algorithm and local search to solve MAX-SAT problem using nVidia CUDA frameworkGenetic Programming and Evolvable Machines, 2009
- Quantum cooperative search algorithm for 3-SATJournal of Computer and System Sciences, 2007
- GASAT: A Genetic Local Search Algorithm for the Satisfiability ProblemEvolutionary Computation, 2006
- Maximum satisfiability: How good are tabu search and plateau moves in the worst-case?European Journal of Operational Research, 2005
- Exploiting Unit Propagation to Compute Lower Bounds in Branch and Bound Max-SAT SolversLecture Notes in Computer Science, 2005
- Improved quantum cost for n -bit Toffoli gatesElectronics Letters, 2003
- Elementary gates for quantum computationPhysical Review A, 1995
- The Minimum Satisfiability ProblemSIAM Journal on Discrete Mathematics, 1994
- Efficient local search for very large-scale satisfiability problemsACM SIGART Bulletin, 1992
- Reversible logic and quantum computersPhysical Review A, 1985