Branch-and-bound digitized counterdiabatic quantum optimization
Preprint
Abstract
Branch-and-bound algorithms effectively solve combinatorial optimization problems, relying on the relaxation of the objective function to obtain tight lower bounds. While this is straightforward for convex objective functions, higher-order formulations pose challenges due to their inherent non-convexity. In this work, we propose branch-and-bound digitized counterdiabatic quantum optimization (BB-DCQO), a quantum algorithm that addresses the relaxation difficulties in higher-order unconstrained binary optimization (HUBO) problems. By employing bias fields as approximate solutions to the relaxed problem, we iteratively enhance the quality of the results compared to the bare bias-field digitized counterdiabatic quantum optimization (BF-DCQO) algorithm. We refer to this enhanced method as BBB-DCQO. In order to benchmark it against simulated annealing (SA), we apply it on sparse HUBO instances with up to $156$ qubits using tensor network simulations. To explore regimes that are less tractable for classical simulations, we experimentally apply BBB-DCQO to denser problems using up to 100 qubits on IBM quantum hardware. We compare our results with SA and a greedy-tuned quantum annealing baseline. In both simulations and experiments, BBB-DCQO consistently achieved higher-quality solutions with significantly reduced computational overhead, showcasing the effectiveness of integrating counterdiabatic quantum methods into branch-and-bound to address hard non-convex optimization tasks.
Keywords
All Related Versions
This publication has 32 references indexed in Scilit:
- Bias-field digitized counterdiabatic quantum algorithm for higher-order binary optimizationCommunications Physics, 2025
- Short-depth QAOA circuits and quantum annealing on higher-order ising modelsnpj Quantum Information, 2024
- Quantum Annealing vs. QAOA: 127 Qubit Higher-Order Ising Problems on NISQ Computers2023
- Recent Theoretical Advances in Non-Convex Optimization2022
- Resource-efficient quantum algorithm for protein foldingnpj Quantum Information, 2021
- Non-convex mixed-integer nonlinear programming: A surveySurveys in Operations Research and Management Science, 2012
- Global optimization in the 21st century: Advances and challengesComputers & Chemical Engineering, 2005
- Adiabatic Population Transfer with Control FieldsThe Journal of Physical Chemistry A, 2003
- A user's guide to tabu searchAnnals of Operations Research, 1993
- The sphericalp-spin interaction spin glass model: the staticsZeitschrift für Physik B Condensed Matter, 1992