Solving Max-3SAT Using QUBO Approximation

Sebastian Zielinski, Jonas Nüßlein, Michael Kölle, Thomas Gabor, Claudia Linnhoff-Popien, Sebastian Feld

In the current "NISQ" (Noisy Intermediate-Scale Quantum) era, quantum computers are like early radio sets—full of static and prone to drifting off-station. When we try to solve complex logic problems on these devices, the hardware's inherent noise often mangles the "perfect" mathematical models we give it.

A new paper from researchers at LMU Munich and Delft University of Technology suggests a counter-intuitive solution: If the hardware is going to approximate your answer anyway, you might as well give it a simpler, approximate version of the problem.

TL;DR

Researchers found that using "approximate" mathematical models to solve MAX-3SAT problems on quantum annealers actually yields better results than using exact models. By eliminating auxiliary variables and shrinking the problem size, their "FullApprox" method reduces noise interference and allows current quantum hardware to tackle 50% larger problems.

What Problem Does This Paper Address?

To solve a logic problem like MAX-3SAT (finding the variable assignment that satisfies the maximum number of logical clauses) on a quantum annealer like D-Wave, you must translate it into a QUBO (Quadratic Unconstrained Binary Optimization) matrix.

The "standard" way to do this translation is exact. However, to represent a 3-variable clause (like $x \lor y \lor \neg z$) as a quadratic equation, you usually need to add an "auxiliary variable" for every single clause. If you have $n$ variables and $m$ clauses, your quantum "map" becomes $(n+m) \times (n+m)$.

On modern hardware, these extra variables are a liability. They require more physical qubits and more complex connections, which invites more noise. The authors ask: Can we create a smaller $(n \times n)$ approximation that fits better on the chip, even if it's mathematically "imperfect"?

Methods

The authors propose a systematic way to create QUBO Approximations:

  1. The Mathematical Barrier: They first prove (Theorem 1) that it is mathematically impossible to perfectly represent a 3-variable SAT clause using only a $3 \times 3$ matrix without auxiliary variables. An approximation is mandatory.
  2. Systematic Search: Instead of guessing, they used a "Pattern QUBO" search to find $3 \times 3$ matrices that correctly identify 6 out of the 7 possible satisfying assignments for a clause.
  3. FullApprox: By using these $3 \times 3$ building blocks, they created a "FullApprox" model that uses zero auxiliary variables. This results in a QUBO matrix of size $n \times n$, significantly smaller than the state-of-the-art exact models.
  4. Comparison: They compared this against "Naive Pruning"—simply taking an exact model and deleting the smallest values to save space—to show that systematic design beats random simplification.

Datasets

The team evaluated their approach using:

  • Small Scale: 100 random 3SAT formulas (500 clauses, 145 variables) generated via the Balanced SAT method. These were small enough to be embedded onto the D-Wave Advantage_System6.4 quantum annealer.
  • Large Scale: 100 larger formulas (10,000 clauses, 2,780 variables) to test how the approximation scales using classical "Tabu Search" solvers.

Key Insights and Ideas

  • Noise as Involuntary Approximation: The authors argue that because current quantum computers lack error correction, every calculation is already an approximation. By providing a simpler input, you improve the "signal-to-noise" ratio.
  • Auxiliary Variables are Expensive: In quantum annealing, every extra variable increases the complexity of the "embedding" (how the problem is mapped to physical qubits). Reducing the variable count from $(n+m)$ to $n$ is a massive win for hardware efficiency.
  • Naive Pruning Fails: You can't just delete parts of a perfect model to make it smaller. Doing so causes an immediate, sharp drop in solution quality. The approximation must be built into the logic of the transformation itself.

Key Results

  • Better Solutions: On the D-Wave hardware, the FullApprox method consistently found assignments that satisfied more clauses than the exact methods (Chancellor and Nüßlein transformations).
  • Qubit Efficiency: FullApprox required roughly 50% fewer physical qubits (avg. 2,385) compared to exact methods (avg. ~4,760).
  • Increased Capacity: Because the models were smaller, the researchers could fit problems with 50% more clauses (750 vs 500) onto the same D-Wave chip.
  • Classical Scaling: Even on classical solvers, the approximation held up, satisfying approximately 98% of all clauses in massive 10,000-clause problems.

Limitations and Future Work

The primary limitation is inherent in the name: it is an approximation. There is no mathematical guarantee that the "best" solution found by the approximate QUBO is the absolute "best" solution for the original 3SAT problem.

The authors suggest future research should explore:

  1. Why specific exact models (like Chancellor’s) degrade so much faster than others when pruned.
  2. Whether this "systematic approximation" strategy can be applied to other NP-hard problems like the Traveling Salesperson Problem or Job Shop Scheduling.

Paper Citation: Zielinski, S., et al. (2024). Solving Max-3SAT Using QUBO Approximation. arXiv:2409.15891v1 [quant-ph].

Summary updated

Abstract

As contemporary quantum computers do not possess error correction, any calculation performed by these devices can be considered an involuntary approximation. To solve a problem on a quantum annealer, it has to be expressed as an instance of Quadratic Unconstrained Binary Optimization (QUBO). In this work, we thus study whether systematically approximating QUBO representations of the MAX-3SAT problem can improve the solution quality when solved on contemporary quantum hardware, compared to using exact, non-approximated QUBO representations. For a MAX-3SAT instance consisting of a 3SAT formula with n variables and m clauses, we propose a method of systematically creating approximate QUBO representations of dimension (n x n), which is significantly smaller than the QUBO matrices of any exact, non-approximated MAX-3SAT QUBO transformation. In an empirical evaluation, we demonstrate that using our QUBO approximations for solving MAX-3SAT problems on D-Wave's quantum annealer Advantage_System6.4 can yield better results than using state-of-the-art exact QUBO transformations. Furthermore, we demonstrate that using naive QUBO approximation methods, based on removing values from exact (n+m)x(n+m)-dimensional QUBO representations of MAX-3SAT instances is ineffective.
BibTeX
@inproceedings{zielinski2024solving,
  author = {Sebastian Zielinski and Jonas Nüßlein and Michael Kölle and Thomas Gabor and Claudia Linnhoff-Popien and Sebastian Feld},
  title = {{Solving Max-3SAT Using QUBO Approximation}},
  booktitle = {QCE},
  year = {2024},
  doi = {10.1109/qce60285.2024.00085},
}

Loading related content...

Figure