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:
- 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.
- 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:
- 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.
- 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."
- 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).
- The Classical Part: Generates test points and manages the search space. This is proven to run in polynomial time.
- 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
nealpackage).
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