Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2511.19501 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _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 |