Hybrid Quantum Branch-and-Bound Method for Quadratic Unconstrained Binary Optimization
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_ | 1866912585654206464 |
|---|---|
| author | Peng, Zedong de Roux, Daniel Neira, David E. Bernal |
| author_facet | Peng, Zedong de Roux, Daniel Neira, David E. Bernal |
| contents | Quantum algorithms have shown promise in solving Quadratic Unconstrained Binary Optimization (QUBO) problems, benefiting from their connection to the transverse field Ising model. Various Ising solvers, both classical and quantum, have emerged to tackle such problems efficiently but lack global optimality guarantees and often suffer from hardware limitations such as limited qubit availability. In this work, we propose a hybrid branch-and-bound (B&B) framework that integrates Ising solvers as heuristics within a classical B&B algorithm. Unlike prior theoretical studies, our work presents a practical implementation, available as open-source on GitHub. We explore when and where to apply Ising solvers in the search tree and introduce a custom branching rule optimized QUBO embedding. Our method is evaluated on hundreds of QUBO instances from QUBOLib.jl using Gurobi and the D-Wave quantum annealer. Our results show up to 11% less solution time and 17% fewer nodes compared to default Gurobi, an off-the-shelf commercial optimization solver. These findings demonstrate the value of hybrid quantum-classical strategies for enhancing exact optimization. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_11040 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Hybrid Quantum Branch-and-Bound Method for Quadratic Unconstrained Binary Optimization Peng, Zedong de Roux, Daniel Neira, David E. Bernal Optimization and Control Quantum algorithms have shown promise in solving Quadratic Unconstrained Binary Optimization (QUBO) problems, benefiting from their connection to the transverse field Ising model. Various Ising solvers, both classical and quantum, have emerged to tackle such problems efficiently but lack global optimality guarantees and often suffer from hardware limitations such as limited qubit availability. In this work, we propose a hybrid branch-and-bound (B&B) framework that integrates Ising solvers as heuristics within a classical B&B algorithm. Unlike prior theoretical studies, our work presents a practical implementation, available as open-source on GitHub. We explore when and where to apply Ising solvers in the search tree and introduce a custom branching rule optimized QUBO embedding. Our method is evaluated on hundreds of QUBO instances from QUBOLib.jl using Gurobi and the D-Wave quantum annealer. Our results show up to 11% less solution time and 17% fewer nodes compared to default Gurobi, an off-the-shelf commercial optimization solver. These findings demonstrate the value of hybrid quantum-classical strategies for enhancing exact optimization. |
| title | Hybrid Quantum Branch-and-Bound Method for Quadratic Unconstrained Binary Optimization |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2509.11040 |