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

Jonas Nüßlein; Sebastian Zielinski; Thomas Gabor; Claudia Linnhoff-Popien; Sebastian Feld

doi:10.1007/978-3-031-36030-5_3

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

Jonas Nüßlein^*, Sebastian Zielinski, Thomas Gabor, Claudia Linnhoff-Popien, Sebastian Feld

^*Corresponding author for this work

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

5 Downloads (Pure)

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.

Original language	English
Title of host publication	Computational Science – ICCS 2023 - 23rd International Conference, Proceedings
Editors	Jiří Mikyška, Clélia de Mulatier, Valeria V. Krzhizhanovskaya, Peter M. A. Sloot, Maciej Paszynski, Jack J. Dongarra
Publisher	Springer
Pages	34-47
Number of pages	14
ISBN (Print)	9783031360299
DOIs	https://doi.org/10.1007/978-3-031-36030-5_3
Publication status	Published - 2023
Event	23rd International Conference on Computational Science, ICCS 2023 - Prague, Czech Republic Duration: 3 Jul 2023 → 5 Jul 2023

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	14077 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	23rd International Conference on Computational Science, ICCS 2023
Country/Territory	Czech Republic
City	Prague
Period	3/07/23 → 5/07/23

Bibliographical note

Green Open Access added to TU Delft Institutional Repository ‘You share, we take care!’ – Taverne project https://www.openaccess.nl/en/you-share-we-take-care
Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

Keywords

3-SAT
quantum annealing
QUBO
satisfiability

Access to Document

10.1007/978-3-031-36030-5_3

978-3-031-36030-5_3Final published version, 315 KB

Cite this

Nüßlein, J., Zielinski, S., Gabor, T., Linnhoff-Popien, C., & Feld, S. (2023). Solving (Max) 3-SAT via Quadratic Unconstrained Binary Optimization. In J. Mikyška, C. de Mulatier, V. V. Krzhizhanovskaya, P. M. A. Sloot, M. Paszynski, & J. J. Dongarra (Eds.), Computational Science – ICCS 2023 - 23rd International Conference, Proceedings (pp. 34-47). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14077 LNCS). Springer. https://doi.org/10.1007/978-3-031-36030-5_3

Nüßlein, Jonas ; Zielinski, Sebastian ; Gabor, Thomas et al. / Solving (Max) 3-SAT via Quadratic Unconstrained Binary Optimization. Computational Science – ICCS 2023 - 23rd International Conference, Proceedings. editor / Jiří Mikyška ; Clélia de Mulatier ; Valeria V. Krzhizhanovskaya ; Peter M. A. Sloot ; Maciej Paszynski ; Jack J. Dongarra. Springer, 2023. pp. 34-47 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{5070c0c136cd4156a606fd45168dd554,

title = "Solving (Max) 3-SAT via Quadratic Unconstrained Binary Optimization",

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.",

keywords = "3-SAT, quantum annealing, QUBO, satisfiability",

author = "Jonas N{\"u}{\ss}lein and Sebastian Zielinski and Thomas Gabor and Claudia Linnhoff-Popien and Sebastian Feld",

note = "Green Open Access added to TU Delft Institutional Repository {\textquoteleft}You share, we take care!{\textquoteright} – Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public. ; 23rd International Conference on Computational Science, ICCS 2023 ; Conference date: 03-07-2023 Through 05-07-2023",

year = "2023",

doi = "10.1007/978-3-031-36030-5_3",

language = "English",

isbn = "9783031360299",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "34--47",

editor = "Ji{\v r}{\'i} Miky{\v s}ka and {de Mulatier}, Cl{\'e}lia and Krzhizhanovskaya, {Valeria V.} and Sloot, {Peter M. A.} and Maciej Paszynski and Dongarra, {Jack J.}",

booktitle = "Computational Science – ICCS 2023 - 23rd International Conference, Proceedings",

}

Nüßlein, J, Zielinski, S, Gabor, T, Linnhoff-Popien, C & Feld, S 2023, Solving (Max) 3-SAT via Quadratic Unconstrained Binary Optimization. in J Mikyška, C de Mulatier, VV Krzhizhanovskaya, PMA Sloot, M Paszynski & JJ Dongarra (eds), Computational Science – ICCS 2023 - 23rd International Conference, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 14077 LNCS, Springer, pp. 34-47, 23rd International Conference on Computational Science, ICCS 2023, Prague, Czech Republic, 3/07/23. https://doi.org/10.1007/978-3-031-36030-5_3

Solving (Max) 3-SAT via Quadratic Unconstrained Binary Optimization. / Nüßlein, Jonas; Zielinski, Sebastian; Gabor, Thomas et al.
Computational Science – ICCS 2023 - 23rd International Conference, Proceedings. ed. / Jiří Mikyška; Clélia de Mulatier; Valeria V. Krzhizhanovskaya; Peter M. A. Sloot; Maciej Paszynski; Jack J. Dongarra. Springer, 2023. p. 34-47 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14077 LNCS).

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

TY - GEN

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

AU - Nüßlein, Jonas

AU - Zielinski, Sebastian

AU - Gabor, Thomas

AU - Linnhoff-Popien, Claudia

AU - Feld, Sebastian

N1 - Green Open Access added to TU Delft Institutional Repository ‘You share, we take care!’ – Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

PY - 2023

Y1 - 2023

N2 - 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.

AB - 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.

KW - 3-SAT

KW - quantum annealing

KW - QUBO

KW - satisfiability

UR - http://www.scopus.com/inward/record.url?scp=85185530266&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-36030-5_3

DO - 10.1007/978-3-031-36030-5_3

M3 - Conference contribution

AN - SCOPUS:85185530266

SN - 9783031360299

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 34

EP - 47

BT - Computational Science – ICCS 2023 - 23rd International Conference, Proceedings

A2 - Mikyška, Jiří

A2 - de Mulatier, Clélia

A2 - Krzhizhanovskaya, Valeria V.

A2 - Sloot, Peter M. A.

A2 - Paszynski, Maciej

A2 - Dongarra, Jack J.

PB - Springer

T2 - 23rd International Conference on Computational Science, ICCS 2023

Y2 - 3 July 2023 through 5 July 2023

ER -

Nüßlein J, Zielinski S, Gabor T, Linnhoff-Popien C, Feld S. Solving (Max) 3-SAT via Quadratic Unconstrained Binary Optimization. In Mikyška J, de Mulatier C, Krzhizhanovskaya VV, Sloot PMA, Paszynski M, Dongarra JJ, editors, Computational Science – ICCS 2023 - 23rd International Conference, Proceedings. Springer. 2023. p. 34-47. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-36030-5_3