Solving Max-3SAT Using QUBO Approximation

Zielinski, Sebastian ; Nüßlein, Jonas ; Kölle, Michael; Gabor, Thomas ; Linnhoff-Popien, Claudia und Feld, Sebastian (2024): Solving Max-3SAT Using QUBO Approximation. QCE 2024: IEEE International Conference on Quantum Computing and Engineering, Montréal, QC, Canada, 15. - 20. September 2024. Culhane, Candace; Byrd, Greg; Muller, Hausi; Alexev, Yuri und Sheldon, Sarah (Hrsg.): In: Proceedings Volume I of III IEEE Quantum Week 2024, Bd. 1 Los Alamitos: IEEE. S. 681-691

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

• Dokumententyp: Konferenzbeitrag (Paper)
• Keywords: Computers ; Performance evaluation ; Annealing ; Systematics ; Qubit ; Quantum annealing ; Hardware ; Error correction; Approximation methods ; Optimization ; Quadratic Unconstrained Binary Optimization ; Combinatorial Optimization ; Max-3SAT ; Approximation
• Fakultät: Mathematik, Informatik und Statistik > Informatik
• Themengebiete: 000 Informatik, Informationswissenschaft, allgemeine Werke > 004 Informatik
• ISBN: 979-8-3315-4137-8
• Ort: Los Alamitos
• Sprache: Englisch