Abstract
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. While it is widely acknowledged that quantum computers should augment classical computers, rather than replace them entirely, comparatively little attention has been directed toward deriving analytical characterizations of their interactions. In this paper, we present a formal analysis of hybrid algorithms in the context of solving mixed-binary quadratic programs (MBQP) via Ising solvers. We show the exactness of a convex copositive reformulation of MBQPs, allowing the resulting reformulation to inherit the straightforward analysis of convex optimization. We propose to solve this reformulation with a hybrid quantum-classical cutting-plane algorithm. Using existing complexity results for convex cutting-plane algorithms, we deduce that the classical portion of this hybrid framework is guaranteed to be polynomial time. This suggests that when applied to NP-hard problems, the complexity of the solution is shifted onto the subroutine handled by the Ising solver.
Introduction
Quantum and quantum-inspired "Ising solvers"—such as D-Wave’s quantum annealers or Coherent Ising Machines—are specialized hardware designed to find the ground states of Ising spin Hamiltonians. This capability maps directly to solving Quadratic Unconstrained Binary Optimization (QUBO) problems. However, most industrial and scientific optimization challenges are not pure QUBOs; they are Mixed-Binary Quadratic Programs (MBQPs) that incorporate both continuous and discrete variables subject to complex linear and quadratic constraints.
Historically, the standard approach to utilizing Ising solvers for MBQPs has been "direct transcription," which involves forcing the entire problem into an Ising model. This often results in ill-conditioning, requiring a prohibitive number of qubits or extreme precision to maintain feasibility. Furthermore, these methods often lack rigorous analytical guarantees regarding the interaction between classical and quantum components. This paper introduces a convex framework that formally partitions the computational workload, providing a clear analytical boundary between classical optimization and quantum search.
Theoretical Framework: Copositive Reformulation
The core of the proposed method is the reformulation of non-convex MBQPs into a convex completely positive program. While this transformation results in a convex problem, the complexity is preserved within the constraints, which involve the cone of copositive matrices. Working with this cone is known to be NP-hard.
A significant theoretical contribution of this work is the proof of strong duality for this specific reformulation. This ensures that solving the dual (copositive) problem yields the exact solution to the original MBQP without a relaxation gap. By moving the problem into the realm of copositive programming, the authors can leverage the structured logic of convex optimization while isolating the inherent NP-hardness of the original discrete problem.
The Hybrid Cutting-Plane Algorithm
To solve the copositive reformulation, the authors implement a hybrid quantum-classical cutting-plane algorithm. The algorithm proceeds as follows:
- Classical Scaffold: A classical cutting-plane method iteratively refines the search space. It proposes candidate solutions and generates "cuts" to eliminate regions that do not contain the optimum.
- Ising Separation Oracle: The computational bottleneck of the cutting-plane method is the "separation oracle," which must determine if a candidate matrix is copositive. The authors transform this feasibility check into a QUBO problem.
- Quantum Offloading: The QUBO is sent to an Ising solver. If the solver finds a negative value, it provides a "certificate of non-copositivity." This certificate is returned to the classical computer to generate a new linear cut.
By applying existing complexity results for convex cutting-plane algorithms, the authors demonstrate that the classical portion of this framework—updating the search space and generating test points—is guaranteed to scale polynomially with problem size. Consequently, the exponential complexity associated with NP-hard problems is shifted entirely onto the Ising solver's subroutine.
Empirical Evaluation
The framework was evaluated using the Maximum Clique Problem, a foundational NP-hard graph theory problem. The researchers generated 25 random Erdős-Rényi graph instances across various sizes (10 to 270 vertices) and edge densities ($p \in \{0.25, 0.5, 0.75\}$).
The hybrid approach, utilizing Simulated Annealing (via the neal package) as a proxy for an Ising solver, was benchmarked against Gurobi, a state-of-the-art classical industrial solver. The results indicated several key performance trends:
- Scaling and Performance: While Gurobi remains faster for small-scale instances due to the overhead of the hybrid framework, the copositive cutting-plane algorithm begins to outperform Gurobi as the number of vertices ($N$) increases.
- Oracle Efficiency: The Ising solver often identified certificates of infeasibility significantly faster than Gurobi’s exact methods could prove optimality. In many instances, the solver reached the required confidence level before Gurobi completed its initial pre-processing steps.
- Resilience: The framework proved resilient to heuristic errors. Even if the Ising solver fails to find the absolute ground state, any negative value found serves as a valid certificate, allowing the classical algorithm to continue making progress.
Discussion and Limitations
While the framework provides a rigorous path forward for hybrid optimization, certain challenges remain. The current implementation requires the discretization of continuous variables into bits to be compatible with Ising solvers, which introduces approximation errors. If discretization is too coarse, the optimal solution may be missed; if too fine, the qubit requirements may exceed hardware capacity.
Additionally, if an Ising solver fails to find a certificate when one exists, the classical algorithm might prematurely terminate. Future work may involve utilizing "multiple reads" or hybridizing with classical checks to improve robustness. The authors also suggest that emerging hardware, such as Coherent Continuous-Variable Machines (CCVM), could eventually solve these feasibility checks natively, eliminating the need for discretization and further streamlining the hybrid pipeline.
Summary updated