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

Conference paper (2023)

Authors

Jonas Nüßlein Ludwig Maximilians University
Sebastian Zielinski Ludwig Maximilians University
Thomas Gabor Ludwig Maximilians University
Claudia Linnhoff-Popien Ludwig Maximilians University
S. Feld Quantum Circuit Architectures and Technology, QCD/Feld Group
Research Group
Quantum Circuit Architectures and Technology
More Info
expand_more

Published Date

2023

Language

English

Reuse Rights

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.

Research Group

Quantum Circuit Architectures and Technology

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.

Files

978-3-031-36030-5_3.pdf
(pdf | 0.445 Mb)
- Embargo expired in 10-02-2025
Unknown license