Solving Max-3SAT Using QUBO Approximation
Sebastian Zielinski, Jonas Nüßlein, Michael Kölle, Thomas Gabor, Claudia Linnhoff-Popien and 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 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×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)×(n+m)−dimensional QUBO representations of MAX-3SAT instances, is ineffective.
2024 IEEE International Conference on Quantum Computing and Engineering (QCE), Vol. 01, pp. 681-691 (2024)
Cite This Work
Switch between citation styles and copy the format you need.
Citation
Sebastian Zielinski, Jonas Nüßlein, Michael Kölle, Thomas Gabor, Claudia Linnhoff-Popien, and Sebastian Feld. “Solving Max-3SAT Using QUBO Approximation.” 2024 IEEE International Conference on Quantum Computing and Engineering (QCE), 01 , pp. 681-691 , 2024. https://doi.org/10.1109/QCE60285.2024.00085