Solving (Max) 3-SAT via Quadratic Unconstrained Binary Optimization
Jonas Nüßlein (Ludwig Maximilians University)
Sebastian Zielinski (Ludwig Maximilians University)
Thomas Gabor (Ludwig Maximilians University)
Claudia Linnhoff-Popien (Ludwig Maximilians University)
S. Feld (TU Delft - Quantum Circuit Architectures and Technology, TU Delft - QCD/Feld Group)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
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.