Hybrid classical-quantum branch-and-bound algorithm for solving integer linear problems
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917669404409856 |
|---|---|
| author | Sanavio, Claudio Tignone, Edoardo Ercolessi, Elisa |
| author_facet | Sanavio, Claudio Tignone, Edoardo Ercolessi, Elisa |
| contents | Quantum annealers are suited to solve several logistic optimization problems expressed in the QUBO formulation. However, the solutions proposed by the quantum annealers are generally not optimal, as thermal noise and other disturbing effects arise when the number of qubits involved in the calculation is too large. In order to deal with this issue, we propose the use of the classical branch-and-bound algorithm, that divides the problem into sub-problems which are described by a lower number of qubits. We analyze the performance of this method on two problems, the knapsack problem and the traveling salesman problem. Our results show the advantages of this method, that balances the number of steps that the algorithm has to make with the amount of error in the solution found by the quantum hardware that the user is willing to risk. All the results are actual runs on the quantum annealer D-Wave Advantage. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_09700 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Hybrid classical-quantum branch-and-bound algorithm for solving integer linear problems Sanavio, Claudio Tignone, Edoardo Ercolessi, Elisa Quantum Physics Quantum annealers are suited to solve several logistic optimization problems expressed in the QUBO formulation. However, the solutions proposed by the quantum annealers are generally not optimal, as thermal noise and other disturbing effects arise when the number of qubits involved in the calculation is too large. In order to deal with this issue, we propose the use of the classical branch-and-bound algorithm, that divides the problem into sub-problems which are described by a lower number of qubits. We analyze the performance of this method on two problems, the knapsack problem and the traveling salesman problem. Our results show the advantages of this method, that balances the number of steps that the algorithm has to make with the amount of error in the solution found by the quantum hardware that the user is willing to risk. All the results are actual runs on the quantum annealer D-Wave Advantage. |
| title | Hybrid classical-quantum branch-and-bound algorithm for solving integer linear problems |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2311.09700 |