Solving Max-3SAT Using QUBO Approximation

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

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 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 \times 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) \times (n+m)$-dimensional QUBO representations of MAX-3SAT instances is ineffective.

Introduction

In the current "Noisy Intermediate-Scale Quantum" (NISQ) era, quantum hardware is inherently susceptible to noise and decoherence. When mapping complex combinatorial problems like MAX-3SAT to these devices, the standard approach involves creating "exact" mathematical models. However, these models often require auxiliary variables that increase the problem's physical footprint on the quantum chip. Researchers from LMU Munich and Delft University of Technology suggest that since the hardware already performs involuntary approximations due to noise, providing a systematically simplified, approximate model can actually lead to superior results.

The Challenge of Exact Transformations

To solve a MAX-3SAT problem on a quantum annealer such as D-Wave, the logical formula must be translated into a Quadratic Unconstrained Binary Optimization (QUBO) matrix. Standard exact transformations for a 3-variable clause (e.g., $x_i \lor x_j \lor \neg x_k$) typically require at least one auxiliary variable to reduce the cubic interaction to a quadratic one.

Exact QUBO representation for the clause $(x_i \lor x_j \lor \neg x_k)$ requiring an auxiliary variable $a_l$.

For a problem with $n$ variables and $m$ clauses, this results in a QUBO matrix of size $(n+m) \times (n+m)$. On modern hardware, these extra variables are a significant liability. They necessitate more physical qubits and more intricate couplers, which in turn increases the impact of hardware noise.

Exact QUBO representation for the clause $(\neg x_i \lor \neg x_j \lor \neg x_k)$ showing the additional variable $a_l$.

Systematic Approximation: The FullApprox Method

The researchers propose a "FullApprox" method that eliminates auxiliary variables entirely, resulting in a QUBO matrix of size $n \times n$.

  1. Mathematical Necessity: The paper proves (Theorem 1) that it is impossible to perfectly represent a 3-variable SAT clause using only a $3 \times 3$ matrix without auxiliary variables. Thus, any $n \times n$ model must be an approximation.
  2. Pattern QUBO Search: Instead of arbitrary simplification, the team used a systematic search to find $3 \times 3$ "building block" matrices. These matrices correctly identify 6 out of the 7 possible satisfying assignments for a clause, minimizing the logical error introduced by the approximation.
  3. Superiority over Naive Pruning: The study compared FullApprox against "Naive Pruning"—the process of taking an exact model and deleting small coefficients. They found that naive pruning leads to a sharp decline in solution quality, whereas systematic approximation maintains high performance.

Experimental Evaluation and Results

The approach was tested on D-Wave's Advantage_System6.4 using 100 random 3SAT formulas. The results were compelling:

  • Improved Solution Quality: The FullApprox method consistently found variable assignments satisfying more clauses than exact methods like the Chancellor or Nüßlein transformations.
  • Hardware Efficiency: FullApprox reduced the physical qubit requirement by approximately 50% (averaging 2,385 qubits vs. 4,760 for exact models).
  • Scaling Capacity: The reduced size allowed the researchers to fit problems with 50% more clauses (up to 750) on the same hardware.
  • Classical Robustness: In large-scale tests (10,000 clauses) using classical Tabu Search solvers, the approximation remained effective, satisfying roughly 98% of all clauses.

Conclusion

The findings highlight a paradigm shift for NISQ-era computing: "perfect" mathematical models are not always optimal for "imperfect" hardware. By reducing the variable count and simplifying the problem graph, systematic approximations like FullApprox improve the signal-to-noise ratio on current quantum annealers. Future work will explore applying this methodology to other NP-hard problems, such as Job Shop Scheduling and the Traveling Salesperson Problem.

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},
}
Figure