Hybrid Algorithm of Linear Programming Relaxation and Quantum Annealing
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913574650118144 |
|---|---|
| author | Takabayashi, Taisei Ohzeki, Masayuki |
| author_facet | Takabayashi, Taisei Ohzeki, Masayuki |
| contents | The demand for classical-quantum hybrid algorithms to solve large-scale combinatorial optimization problems using quantum annealing (QA) has increased. One approach involves obtaining an approximate solution using classical algorithms and refining it using QA. In previous studies, such variables were determined using molecular dynamics (MD) as a continuous optimization method. We propose a method that uses the simple continuous relaxation technique called linear programming (LP) relaxation. Our method demonstrated superiority through comparative experiments with the minimum vertex cover problem versus the previous MD-based approach. Furthermore, the hybrid approach of LP relaxation and simulated annealing showed advantages in accuracy and speed compared to solving with simulated annealing alone. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_10765 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Hybrid Algorithm of Linear Programming Relaxation and Quantum Annealing Takabayashi, Taisei Ohzeki, Masayuki Quantum Physics The demand for classical-quantum hybrid algorithms to solve large-scale combinatorial optimization problems using quantum annealing (QA) has increased. One approach involves obtaining an approximate solution using classical algorithms and refining it using QA. In previous studies, such variables were determined using molecular dynamics (MD) as a continuous optimization method. We propose a method that uses the simple continuous relaxation technique called linear programming (LP) relaxation. Our method demonstrated superiority through comparative experiments with the minimum vertex cover problem versus the previous MD-based approach. Furthermore, the hybrid approach of LP relaxation and simulated annealing showed advantages in accuracy and speed compared to solving with simulated annealing alone. |
| title | Hybrid Algorithm of Linear Programming Relaxation and Quantum Annealing |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2308.10765 |