Enhancing Optimization with Quantum Annealers: A Focus on Max 3 SAT

The Max-SAT problem is an optimization problem that involves finding the maximum number of satisfiable clauses in a Boolean formula by assigning truth values to its variables. With the rise of quantum computing, Quantum Annealing offers a promising approach for solving Max-SAT instances. In this study, we evaluate various methods that convert random 3-SAT instances into Quadratic Unconstrained Binary Optimization (QUBO) problems. We highlight the superior performance of two novel methods compared to existing solutions using D-Wave's quantum annealer.