A quantum-classical hybrid branch & bound algorithm
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917237870297088 |
|---|---|
| author | Czégel, András Sipos, Dávid -Tóth, Boglárka G. |
| author_facet | Czégel, András Sipos, Dávid -Tóth, Boglárka G. |
| contents | We propose a complete quantum-classical hybrid branch-and-bound algorithm (QCBB) to solve binary linear programs with equality constraints. That includes bound calculation, convergence metrics and optimality guarantee to the quantum optimization based algorithm, which makes our method directly comparable to classical methods. Key aspects of the proposed algorithm are (i) encapsulation of the quantum optimization method, (ii) utilization of noisy samples for problem reduction, (iii) classical approximation based bound calculation, (iv) branch and bound traits like gap-based stopping criterion and monotonic increase in solution quality, (v) integrated composition of many different solutions that can be improved individually. We show numerical results on set partitioning problem instances and provide many details about the characteristics of the different steps of the algorithm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_19501 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A quantum-classical hybrid branch & bound algorithm Czégel, András Sipos, Dávid -Tóth, Boglárka G. Quantum Physics We propose a complete quantum-classical hybrid branch-and-bound algorithm (QCBB) to solve binary linear programs with equality constraints. That includes bound calculation, convergence metrics and optimality guarantee to the quantum optimization based algorithm, which makes our method directly comparable to classical methods. Key aspects of the proposed algorithm are (i) encapsulation of the quantum optimization method, (ii) utilization of noisy samples for problem reduction, (iii) classical approximation based bound calculation, (iv) branch and bound traits like gap-based stopping criterion and monotonic increase in solution quality, (v) integrated composition of many different solutions that can be improved individually. We show numerical results on set partitioning problem instances and provide many details about the characteristics of the different steps of the algorithm. |
| title | A quantum-classical hybrid branch & bound algorithm |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2511.19501 |