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

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

Abstract

To solve 3SAT instances on quantum annealers, they must first be transformed into Quadratic Unconstrained Binary Optimization (QUBO) form. This study benchmarks four structurally distinct 3SAT-to-QUBO transformations on D-Wave's Advantage_system4.1. We demonstrate that the choice of transformation significantly impacts solution quality. Crucially, we find that the size of a QUBO instance is not a reliable predictor of success; instead, the range and variety of quadratic values—the "precision" of the mapping—are the primary drivers of performance.

Introduction

The 3SAT problem is a fundamental NP-complete problem in logic. Solving it on modern quantum annealers requires a translation step into the QUBO framework. While researchers traditionally prioritize "compact" mappings that use the minimum number of qubits to reduce noise, the impact of the mathematical structure of these mappings on solution quality has remained under-explored. This paper investigates how different transformation strategies affect the probability of finding correct solutions on real-world hardware.

Methodology

The study compares four transformations: Choi’s Transformation, Chancellor’s Transformation (with two parameterizations, J1 and J5), and Nuesslein’s Transformation.

A single QUBO matrix representing the constraints of a logic clause.

Nuesslein’s approach is particularly notable for its use of "pattern QUBOs," which are pre-defined matrices based on the arrangement of literals within a clause.

Examples of pattern QUBOs used in the Nuesslein transformation for different clause configurations (a-d).

The benchmark consisted of 1,000 hard 3SAT instances with $n=11$ variables and $m=46$ clauses, positioned near the computational "phase transition" to ensure difficulty. All instances were verified as satisfiable classically before quantum execution.

The Precision Bottleneck

A key finding of this research is that "size is a deceptive metric." While the Choi transformation uses significantly more qubits than the compact Chancellor variants, it outperformed ChancellorJ5. The limiting factor is the analog precision of the quantum hardware.

When a transformation produces a wide range of unique numerical values, D-Wave's auto-scaling mechanism must "squash" these values to fit the hardware's physical range (typically $[-1, 1]$). This reduction in resolution makes it difficult for the annealer to distinguish the true ground state from thermal noise. Transformations with fewer unique quadratic values and tighter ranges—like ChancellorJ1—maintain higher effective precision and thus yield better results.

Experimental Results

The performance differences between transformations were stark, spanning an order of magnitude in success rates.

Transformation Instances Solved (%) Correct Solutions (%)
ChancellorJ1 91.0% ~8.71%
Nuesslein 79.4% ~5.58%
Choi 69.5% ~2.46%
ChancellorJ5 58.0% ~0.48%

ChancellorJ1 emerged as the most effective, while ChancellorJ5—despite having the same qubit footprint—performed the worst due to its higher magnitude internal weights which exacerbated the precision bottleneck.

Conclusion

This study highlights that optimizing for qubit count alone is insufficient for maximizing performance on current quantum annealers. Future work should focus on developing "precision-aware" transformations that balance compact representation with numerical simplicity. Understanding these hardware-specific constraints is vital for scaling quantum solutions to larger, more complex NP-hard problems.

Summary updated

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.
BibTeX
@inproceedings{zielinski2023influence,
  author = {Sebastian Zielinski and Jonas Nüßlein and Jonas Stein and Thomas Gabor and Claudia Linnhoff‐Popien and Sebastian Feld},
  title = {{Influence of Different 3SAT-to-QUBO Transformations on the Solution Quality of Quantum Annealing: A Benchmark Study}},
  booktitle = {GECCO Companion},
  year = {2023},
  doi = {10.1145/3583133.3596330},
}
Figure