2024/09/24 by Sebastian Zielinski, Zielinski, Sebastian, Jonas Nüßlein +9
Computer Science · Engineering · #Constraint Satisfaction and Optimization #FOS: Physical sciences #Manufacturing Process and Optimization #Quantum Physics (quant-ph) #Space Satellite Systems and Control
paper · pdf · doi:10.48550/arxiv.2409.15891
openalex publication_date 2024/09/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 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)x(n+m)-dimensional QUBO representations of MAX-3SAT instances is ineffective.