QUBO formulation for the Snake-in-the-box and Coil-in-the-box problems
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929490580471808 |
|---|---|
| author | Fuidio, Federico Canale, Eduardo Sotelo, Rafael |
| author_facet | Fuidio, Federico Canale, Eduardo Sotelo, Rafael |
| contents | This paper present the first QUBO formulations for the Snake-in-the-box (SITB) and Coil-in-the-box (CITB) problems. Both formulations are also capable of solving the NP-Hard problems of Maximum induced path and Maximum induced cylce respectively. In the process we also found a new QUBO formulation for the Maximum Common Induced Sub-graph problem. We proved the correctness of our formulations for the SITB, CITB and Maximum Common Sub-graph problem, and tested the formulations of the SITB and CITB in both classical and quantum solvers, being able to get the best solution for up to 5 dimensions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_04476 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | QUBO formulation for the Snake-in-the-box and Coil-in-the-box problems Fuidio, Federico Canale, Eduardo Sotelo, Rafael Optimization and Control Combinatorics Quantum Physics This paper present the first QUBO formulations for the Snake-in-the-box (SITB) and Coil-in-the-box (CITB) problems. Both formulations are also capable of solving the NP-Hard problems of Maximum induced path and Maximum induced cylce respectively. In the process we also found a new QUBO formulation for the Maximum Common Induced Sub-graph problem. We proved the correctness of our formulations for the SITB, CITB and Maximum Common Sub-graph problem, and tested the formulations of the SITB and CITB in both classical and quantum solvers, being able to get the best solution for up to 5 dimensions. |
| title | QUBO formulation for the Snake-in-the-box and Coil-in-the-box problems |
| topic | Optimization and Control Combinatorics Quantum Physics |
| url | https://arxiv.org/abs/2409.04476 |