• Home
  • Aktuelles
  • Technologie
  • Forschung
  • Lehre
  • Wirtschaft
  • Jobs
  • Home
  • Aktuelles
  • Technologie
  • Forschung
  • Lehre
  • Wirtschaft
  • Jobs
Kontakt
  • Deutsch
  • English

  • Home
  • Aktuelles
  • Technologie
  • Forschung
  • Lehre
  • Wirtschaft
  • Jobs
Kontakt
  • Deutsch
  • English

Pattern QUBOs: Algorithmic Construction of 3SAT-to-QUBO Transformations

Pattern QUBOs: Algorithmic Construction of 3SAT-to-QUBO Transformations

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

Abstract

One way of solving 3sat instances on a quantum computer is to transform the 3sat instances into instances of Quadratic Unconstrained Binary Optimizations (QUBOs), which can be used as an input for the QAOA algorithm on quantum gate systems or as an input for quantum annealers. This mapping is performed by a 3sat-to-QUBO transformation. Recently, it has been shown that the choice of the 3sat-to-QUBO transformation can significantly impact the solution quality of quantum annealing. It has been shown that the solution quality can vary up to an order of magnitude difference in the number of correct solutions received, depending solely on the 3sat-to-QUBO transformation. An open question is: what causes these differences in the solution quality when solving 3sat-instances with different 3sat-to-QUBO transformations? To be able to conduct meaningful studies that assess the reasons for the differences in the performance, a larger number of different 3sat-to-QUBO transformations would be needed. However, currently, there are only a few known 3sat-to-QUBO transformations, and all of them were created manually by experts, who used time and clever reasoning to create these transformations. In this paper, we will solve this problem by proposing an algorithmic method that is able to create thousands of new and different 3sat-to-QUBO transformations, and thus enables researchers to systematically study the reasons for the significant difference in the performance of different 3sat-to-QUBO transformations. Our algorithmic method is an exhaustive search procedure that exploits properties of 4×4
dimensional pattern QUBOs, a concept which has been used implicitly in the creation of 3sat-to-QUBO transformations before, but was never described explicitly. We will thus also formally and explicitly introduce the concept of pattern QUBOs in this paper.

In progress


QAR-Lab – Quantum Applications and Research Laboratory
Ludwig-Maximilians-Universität München
Oettingenstr. 67
80538 München
Telefon: +49 89 2180-9153
E-Mail: qar-lab@mobile.ifi.lmu.de

© Copyright 2025

Allgemein

Team
Kontakt
Impressum

Social Media

Twitter Linkedin Github

Sprache

  • Deutsch
  • English
Cookie-Zustimmung verwalten
Wir verwenden Cookies, um unsere Website und unseren Service zu optimieren.
Funktional Immer aktiv
Die technische Speicherung oder der Zugang ist unbedingt erforderlich für den rechtmäßigen Zweck, die Nutzung eines bestimmten Dienstes zu ermöglichen, der vom Teilnehmer oder Nutzer ausdrücklich gewünscht wird, oder für den alleinigen Zweck, die Übertragung einer Nachricht über ein elektronisches Kommunikationsnetz durchzuführen.
Vorlieben
Die technische Speicherung oder der Zugriff ist für den rechtmäßigen Zweck der Speicherung von Präferenzen erforderlich, die nicht vom Abonnenten oder Benutzer angefordert wurden.
Statistiken
Die technische Speicherung oder der Zugriff, der ausschließlich zu statistischen Zwecken erfolgt. Die technische Speicherung oder der Zugriff, der ausschließlich zu anonymen statistischen Zwecken verwendet wird. Ohne eine Vorladung, die freiwillige Zustimmung deines Internetdienstanbieters oder zusätzliche Aufzeichnungen von Dritten können die zu diesem Zweck gespeicherten oder abgerufenen Informationen allein in der Regel nicht dazu verwendet werden, dich zu identifizieren.
Marketing
Die technische Speicherung oder der Zugriff ist erforderlich, um Nutzerprofile zu erstellen, um Werbung zu versenden oder um den Nutzer auf einer Website oder über mehrere Websites hinweg zu ähnlichen Marketingzwecken zu verfolgen.
Optionen verwalten Dienste verwalten Verwalten von {vendor_count}-Lieferanten Lese mehr über diese Zwecke
Einstellungen anzeigen
{title} {title} {title}