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.
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.
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