Pattern QUBOs: Algorithmic construction of 3SAT-to-QUBO transformations

• Published in: arXiv.org 2023-05
• Main Authors: Zielinski, Sebastian, Nüßlein, Jonas, Stein, Jonas, Gabor, Thomas, Linnhoff-Popien, Claudia, Feld, Sebastian
• Format: Article
• Language: English
• Subjects: Algorithms; Optimization; Qubits (quantum computing); Transformations
• ISSN: 2331-8422
• DOI: 10.48550/arxiv.2305.02659

3SAT instances need to be transformed into instances of Quadratic Unconstrained Binary Optimization (QUBO) to be solved on a quantum annealer. Although it has been shown that the choice of the 3SAT-to-QUBO transformation can impact the solution quality of quantum annealing significantly, currently only a few 3SAT-to-QUBO transformations are known. Additionally, all of the known 3SAT-to-QUBO transformations were created manually (and not procedurally) by an expert using reasoning, which is a rather slow and limiting process. In this paper, we will introduce the name Pattern QUBO for a concept that has been used implicitly in the construction of 3SAT-to-QUBO transformations before. We will provide an in-depth explanation for the idea behind Pattern QUBOs and show its importance by proposing an algorithmic method that uses Pattern QUBOs to create new 3SAT-to-QUBO transformations automatically. As an additional application of Pattern QUBOs and our proposed algorithmic method, we introduce approximate 3SAT-to-QUBO transformations. These transformations sacrifice optimality but use significantly fewer variables (and thus physical qubits on quantum hardware) than non-approximate 3SAT-to-QUBO transformations. We will show that approximate 3SAT-to-QUBO transformations can nevertheless be very effective in some cases.