Influence of Different 3SAT-to-QUBO Transformations on the Solution Quality of Quantum Annealing: A Benchmark Study

Zielinski, Sebastian ; Nüßlein, Jonas ; Stein, Jonas ; Gabor, Thomas und Linnhoff-Popien, Claudia (2023): Influence of Different 3SAT-to-QUBO Transformations on the Solution Quality of Quantum Annealing: A Benchmark Study. GECCO '23 Companion: Companion Conference on Genetic and Evolutionary Computation, Lisbon Portugal, July 15 - 19, 2023. Silva, Sara und Paquete, Luís (Hrsg.): In: Proceedings of the Companion Conference on Genetic and Evolutionary Computation, New York, NY, United States: Association for Computing Machinery. S. 2263-2271

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.

• Dokumententyp: Konferenzbeitrag (Paper)
• Fakultät: Mathematik, Informatik und Statistik > Informatik
• Themengebiete: 000 Informatik, Informationswissenschaft, allgemeine Werke > 004 Informatik
• ISBN: 979-8-4007-0120-7
• Ort: New York, NY, United States
• Sprache: Englisch