Recent years have seen significant advances in quantum/quantum-inspired technologies capable of approximately searching for the ground state of Ising spin Hamiltonians. The promise of leveraging such technologies to accelerate the solution of difficult optimization problems has spurred an increased interest in exploring methods to integrate Ising problems as part of their solution process, with existing approaches ranging from direct transcription to hybrid quantum-classical approaches rooted in existing optimization algorithms. Due to the heuristic and black-box nature of the underlying Ising solvers, many such approaches have limited optimality guarantees. While some hybrid algorithms may converge to global optima, their underlying classical algorithms typically rely on exhaustive search, making it unclear if such algorithmic scaffolds are primed to take advantage of speed-ups that the Ising solver may offer. In this paper, we propose a framework for solving mixed-binary quadratic programs (MBQP) to global optimality using black-box and heuristic Ising solvers. We show the exactness of a convex copositive reformulation of MBQPs, which we propose to solve via a hybrid quantum-classical cutting-plane algorithm. The classical portion of this hybrid framework is guaranteed to be polynomial time, suggesting that when applied to NP-hard problems, the complexity of the solution is shifted onto the subroutine handled by the Ising solver.

翻译：近些年来,在量子/量子激励技术方面取得了显著进步,这些技术能够大致探索Ising Hamiltonians的地面状态。利用这些技术加速解决困难的优化问题的承诺促使人们越来越有兴趣探索将Ising问题整合为解决方案进程的一部分的方法,现有方法包括直接转录和基于现有优化算法的混合量子古典方法。由于基础的Ising 解算器的杂交和黑箱性质,许多这类方法都具有有限的最佳性保证。虽然一些混合算法可能聚集到全球opima,但其基本古典算法通常依赖于彻底的搜索,使得人们不清楚这些算法辅助器是否准备利用Ising Solorlor可能提供的加速进程。在本文中,我们提出了一个框架,以解决混合二元二次二次二次二次二次二次量子工程方案(MBQP),而使用黑箱和超度Isrining解算器实现全球最佳性。我们展示了MBQPs的精确性共性重重组,我们提议通过混合的量子级定式处理方式解决混合式断式方案的复杂度框架。