A Copositive Framework for Analysis of Hybrid Ising-Classical Algorithms

Robin Brown, David E. Bernal Neira, Davide Venturelli, Marco Pavone

TL;DR

This paper introduces a theoretically grounded framework for hybrid quantum-classical optimization by reformulating mixed-binary quadratic programs (MBQP) into convex copositive programs. By employing a hybrid cutting-plane algorithm, the authors prove that the classical portion of the process is guaranteed to be polynomial-time, effectively "packaging" the NP-hard complexity of the problem into a single subroutine handled by an Ising solver.

What Problem Does This Paper Address?

Solving Mixed-Binary Quadratic Programs (MBQP)—problems involving both continuous and discrete variables with quadratic objectives—is notoriously difficult (NP-hard). Recent years have seen the rise of "Ising solvers," such as quantum annealers and the Quantum Approximate Optimization Algorithm (QAOA), which are designed to find the ground states of spin Hamiltonians.

However, two major challenges persist:

  1. Inefficient Mapping: Directly transcribing complex problems into an Ising format often requires many auxiliary variables and results in "ill-conditioned" landscapes that are hard to navigate.
  2. Lack of Theoretical Rigor: While many hybrid classical-quantum algorithms exist (like those based on ADMM or Benders Decomposition), they often lack global convergence guarantees or a clear analytical characterization of how the classical and quantum parts interact.

The authors seek a framework where the classical computer does what it does best (efficiently narrowing down the search space) while the quantum computer handles the specific "hard" bottleneck.

Methods

The authors propose a three-step approach:

  1. Copositive Reformulation: They leverage "Burer’s reformulation," which lifts the non-convex MBQP into a higher-dimensional but convex space called the cone of completely positive matrices.
  2. Proving Strong Duality: A key theoretical contribution of this paper is proving strong duality for this reformulation. This ensures that solving the dual "copositive program" gives the exact same answer as the original problem, with no "relaxation gap."
  3. Hybrid Cutting-Plane Algorithm: To solve the copositive program, they use a standard convex optimization tool: the cutting-plane method (e.g., the Ellipsoid method).
  4. The Classical Part: Generates test points and manages the search space. This is proven to run in polynomial time.
  5. The Quantum Part (The Oracle): The "hard" step in a cutting-plane algorithm is the "separation oracle"—checking if a test point is feasible. In this framework, checking feasibility is equivalent to checking if a matrix is "copositive." The authors show this check can be formulated as a Quadratic Unconstrained Binary Optimization (QUBO) problem, which is the native language of Ising solvers.

Datasets

The authors evaluated their framework using the Maximum Clique Problem, a classic NP-hard graph theory problem.

  • Data: Randomly generated Erdős-Rényi graphs.
  • Scale: Graphs with 10 to 270 vertices.
  • Variations: Three different edge densities ($p = 0.25, 0.5, 0.75$) to test how graph "clutteredness" affects performance.
  • Solvers: They compared a deterministic classical solver (Gurobi) against a stochastic Ising-inspired solver (Simulated Annealing via the neal package).

Key Insights and Ideas

  • Complexity Shifting: The framework successfully "offloads" the exponential complexity of NP-hard problems onto the Ising solver. The classical overhead remains polynomial, meaning as quantum hardware improves, the entire hybrid system scales predictably.
  • Resilience to Heuristics: Unlike some hybrid methods that require the quantum computer to be perfect, the cutting-plane method is resilient. As long as the Ising solver finds any "certificate of non-copositivity" (a negative value), the algorithm can make progress, even if it isn't the absolute global minimum.
  • Packaging the "Hardness": By using copositive programming, the authors "package" all the discrete, non-convex messiness of the original problem into a single, well-defined matrix constraint.

Key Results

  • Empirical Validation of Complexity: Experiments confirmed that the time spent on classical operations (updating the search space) grew modestly, while the time spent on the copositivity checks (the Ising subroutine) scaled exponentially with the number of vertices.
  • Speedup over Deterministic Solvers: For the subproblems (the copositivity checks), Simulated Annealing found solutions orders of magnitude faster than the state-of-the-art deterministic solver (Gurobi).
  • Competitive Performance: For larger graph instances, the hybrid copositive approach actually began to outperform a standard direct Mixed-Integer Linear Programming (MILP) formulation solved entirely by Gurobi.

Limitations and Future Work

  • Discretization Errors: To run the copositivity check on current Ising solvers, the authors had to discretize continuous variables into bits. This introduces an approximation. The authors suggest that future "continuous-variable" Ising machines could solve this more natively.
  • Oracle Failure: If the Ising solver fails to find a certificate when one actually exists (due to its heuristic nature), the algorithm might incorrectly assume a point is feasible. Developing strategies to handle these "false positives" is a key area for future research.
  • Parameter Tuning: The performance of the Ising solver is sensitive to "penalty weights." While the framework mitigates this compared to direct transcription, it remains a factor in the subroutine's efficiency.

Summary updated

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. By leveraging an existing completely positive reformulation of MBQPs, as well as a new strong-duality result, we show the exactness of the dual problem over the cone of copositive matrices, thus 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.
BibTeX
@article{brown2022copositive,
  author = {Robin Brown and David E. Bernal Neira and Davide Venturelli and Marco Pavone},
  title = {{A Copositive Framework for Analysis of Hybrid Ising-Classical Algorithms}},
  journal = {SIAM J. Optim.},
  year = {2022},
}
Figure