Solving (Max) 3-SAT via Quadratic Unconstrained Binary Optimization

2023/02/07 by Nüßlein, Jonas, Zielinski, Sebastian, Gabor, Thomas +2 · 1 citation
#Emerging Technologies (cs.ET) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph)

paper · doi:10.48550/arxiv.2302.03536

Abstract

We introduce a novel approach to translate arbitrary 3-SAT instances to Quadratic Unconstrained Binary Optimization (QUBO) as they are used by quantum annealing (QA) or the quantum approximate optimization algorithm (QAOA). Our approach requires fewer couplings and fewer physical qubits than the current state-of-the-art, which results in higher solution quality. We verified the practical applicability of the approach by testing it on a D-Wave quantum annealer.

Cited by

• Evidence of scaling advantage on an NP-Complete problem with enhanced quantum solvers

Related

• Solving Max-3SAT Using QUBO Approximation
• Transformation-Dependent Performance-Enhancement of Digital Annealer for 3-SAT
• Solving Quadratic Unconstrained Binary Optimization with divide-and-conquer and quantum algorithms
• Efficient Digital Quadratic Unconstrained Binary Optimization Solvers for SAT Problems
• Solving SAT and MaxSAT with a Quantum Annealer: Foundations, Encodings, and Preliminary Results