Influence of Different 3SAT-to-QUBO Transformations on the Solution Quality of Quantum Annealing

A Benchmark Study

Conference paper (2023)

Authors

Sebastian Zielinski Ludwig Maximilians University
Thomas Gabor Ludwig Maximilians University
Jonas Nüßlein Ludwig Maximilians University
Claudia Linnhoff-Popien Ludwig Maximilians University
Jonas Stein Ludwig Maximilians University
S. Feld Quantum Circuit Architectures and Technology - EEMCS
Research Group
Quantum Circuit Architectures and Technology (EEMCS) (TU Delft)
Copyright: © 2023 Sebastian Zielinski, Thomas Gabor, Jonas Nüßlein, Claudia Linnhoff-Popien, Jonas Stein, S. Feld
DOI: https://doi.org/10.1145/3583133.3596330
Satisfiability Quantum annealing Ising 3sat Qubo
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.

Faculty

Electrical Engineering, Mathematics and Computer Science

Department

Quantum & Computer Engineering

Research Group

Quantum Circuit Architectures and Technology

Abstract

To solve 3sat instances on quantum annealers they need to be transformed to an instance of Quadratic Unconstrained Binary Optimization (QUBO). When there are multiple transformations available, the question arises whether different transformations lead to differences in the obtained solution quality. Thus, in this paper we conduct an empirical benchmark study, in which we compare four structurally different QUBO transformations for the 3sat problem with regards to the solution quality on D-Wave’s Advantage_system4.1. We show that the choice of QUBO transformation can significantly impact the number of correct solutions the quantum annealer returns. Furthermore, we show that the size of a QUBO instance (i.e., the dimension of the QUBO matrix) is not a sufficient predictor for solution quality, as larger QUBO instances may produce better results than smaller QUBO instances for the same problem. We also empirically show that the number of different quadratic values of a QUBO instance, combined with their range, can significantly impact the solution quality.