Using an Evolutionary Algorithm to Create (MAX)-3SAT QUBOs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914796782223360 |
|---|---|
| author | Zielinski, Sebastian Zorn, Maximilian Gabor, Thomas Feld, Sebastian Linnhoff-Popien, Claudia |
| author_facet | Zielinski, Sebastian Zorn, Maximilian Gabor, Thomas Feld, Sebastian Linnhoff-Popien, Claudia |
| contents | A common way of solving satisfiability instances with quantum methods is to transform these instances into instances of QUBO, which in itself is a potentially difficult and expensive task. State-of-the-art transformations from MAX-3SAT to QUBO currently work by mapping clauses of a 3SAT formula associated with the MAX-3SAT instance to an instance of QUBO and combining the resulting QUBOs into a single QUBO instance representing the whole MAX-3SAT instance. As creating these transformations is currently done manually or via exhaustive search methods and, therefore, algorithmically inefficient, we see potential for including search-based optimization. In this paper, we propose two methods of using evolutionary algorithms to automatically create QUBO representations of MAX-3SAT problems. We evaluate our created QUBOs on 500 and 1000-clause 3SAT formulae and find competitive performance to state-of-the-art baselines when using both classical and quantum annealing solvers. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_09272 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Using an Evolutionary Algorithm to Create (MAX)-3SAT QUBOs Zielinski, Sebastian Zorn, Maximilian Gabor, Thomas Feld, Sebastian Linnhoff-Popien, Claudia Quantum Physics Emerging Technologies A common way of solving satisfiability instances with quantum methods is to transform these instances into instances of QUBO, which in itself is a potentially difficult and expensive task. State-of-the-art transformations from MAX-3SAT to QUBO currently work by mapping clauses of a 3SAT formula associated with the MAX-3SAT instance to an instance of QUBO and combining the resulting QUBOs into a single QUBO instance representing the whole MAX-3SAT instance. As creating these transformations is currently done manually or via exhaustive search methods and, therefore, algorithmically inefficient, we see potential for including search-based optimization. In this paper, we propose two methods of using evolutionary algorithms to automatically create QUBO representations of MAX-3SAT problems. We evaluate our created QUBOs on 500 and 1000-clause 3SAT formulae and find competitive performance to state-of-the-art baselines when using both classical and quantum annealing solvers. |
| title | Using an Evolutionary Algorithm to Create (MAX)-3SAT QUBOs |
| topic | Quantum Physics Emerging Technologies |
| url | https://arxiv.org/abs/2405.09272 |