Abstract:
Mixed-integer linear programs are widely used to model optimization problems involving both discrete and continuous variables, but remain computationally challenging due to the combinatorial complexity. To exploit the potential advantages of quantum computing in tackling the combinatorial optimization part, recent efforts have explored hybrid quantum-classical Benders decomposition frameworks, which delegate the discrete master problem to quantum solvers like annealers while solving the continuous subproblem classically. However, these approaches typically rely on penalty-based formulations that are heuristic in nature, offer no guarantee of recovering the exact master optimum, require delicate penalty tuning, and introduce slack-register overhead that inflates circuit size and distorts the problem’s native structure. In this work, we propose a Grover Adaptive Search based Benders Decomposition (GAS-BD) algorithm that circumvents penalty terms by directly encoding Benders cuts into a novel quantum oracle. The designed oracle-based quantum solver searches for constraint-satisfying master solutions by leveraging Grover’s potential quadratic speedup, while the subproblem loop is handled by a classical solver. Simulation results shows that GAS-BD matches the convergence of classical Benders and exhibits greater stability than penalty-based hybrid baselines, while remaining executable on current NISQ hardware. These results demonstrate a practical and penalty-free path for embedding exact Benders logic into Grover-style quantum search.