Influence of Different 3SAT-to-QUBO Transformations on the Solution Quality of Quantum Annealing
A Benchmark Study
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 (TU Delft - Quantum Circuit Architectures and Technology)
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
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.