Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2409.15891 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916408757059584 |
|---|---|
| author | Zielinski, Sebastian Nüßlein, Jonas Kölle, Michael Gabor, Thomas Linnhoff-Popien, Claudia Feld, Sebastian |
| author_facet | Zielinski, Sebastian Nüßlein, Jonas Kölle, Michael Gabor, Thomas Linnhoff-Popien, Claudia Feld, Sebastian |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_15891 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Solving Max-3SAT Using QUBO Approximation Zielinski, Sebastian Nüßlein, Jonas Kölle, Michael Gabor, Thomas Linnhoff-Popien, Claudia Feld, Sebastian Quantum Physics 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. |
| title | Solving Max-3SAT Using QUBO Approximation |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2409.15891 |