arXiv:2610.27362
Quantum-Classical Hybrid Methods for Optimization: Lessons from Classical Decomposition
David E. Bernal Neira
Abstract
Quantum and physics-inspired solvers provide specialized sampling interfaces for Ising and quadratic unconstrained binary optimization models, but constrained optimization requires broader coordination and certification. This survey uses classical decomposition to analyze how such solvers can be integrated into hybrid quantum-classical algorithms. We distinguish formal decomposition, reformulation and reduction, and computational orchestration. For each interface, we ask what the transformation preserves, which assumptions make the outer method converge, and which certificates the implemented inner routine supplies. The central questions are whether that information meets the classical algorithm's requirements and whether hybridization improves solution quality or total cost enough to justify its coordination overhead. Benders decomposition, column generation, graph reduction, and copositive methods illustrate this distinction by separating heuristic proposals from classical certification. We also distinguish component effects within a fixed wrapper, reduction--solver interactions, and comparisons between complete quantum-enabled and classical systems. The analyzed studies provide conditional component benefits and favorable co-design evidence, but do not establish transferable end-to-end superiority over strong classical comparators. The resulting framework identifies opportunities for constraint programming and operations research in structure-preserving design, safeguarded hybrid algorithms, and controlled benchmarking.
AI Summary
This survey asks how quantum and physics-inspired optimization samplers can be integrated into classical decomposition algorithms without confusing candidate solutions with the certificates required for convergence or optimality. It separates formal decomposition, reformulation and reduction, and computational orchestration, then examines interfaces including Benders masters, column-generation pricing, mixed-binary ADMM, graph reductions, and copositive separation. The central analysis identifies what each transformation preserves, what the outer algorithm assumes, and what the implemented quantum routine actually returns. A sampled Benders master objective is not a certified lower bound; unsuccessful heuristic pricing does not certify that no improving column exists. In copositive separation, a classically verified negative witness supplies a valid cut, whereas failure to sample one does not certify membership. Exact continuous-oracle guarantees are distinguished from finite-grid encodings and heuristic solves. Performance evidence is organized into fixed-wrapper component effects, reduction–solver interactions, and independently optimized system comparisons. The purposive corpus covers 30 studies, with 25 main-table entries, plus 23 software implementations. Reported findings are mixed: in qReduMIS, a classical simulated-annealing variant matches or exceeds the quantum arm on all 39 tested instances, although budgets are not time-matched. Other studies show conditional component benefits or favorable co-design evidence, but the corpus does not establish robust, transferable end-to-end superiority over strong classical comparators. The survey is neither exhaustive nor an experimental reproduction. Its conclusions retain each study’s restrictions, including unmatched resources, incomplete timing, simulation or projected execution costs, limited uncertainty estimates, and opaque proprietary hybrid components.
OpenAI ChatGPT and Codex assisted with literature and software discovery, drafting, structural revision, technical and citation checks, copyediting, and preparation of LaTeX/TikZ source and diagrams.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 34 pages main paper, 91 pages including supplementary material, 7 figures, invited paper after CPAIOR 2024 workshop on quantum computing