Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming

Friedrich Wagner, Jonas Nüßlein, Frauke LiersACM Trans. Quantum Comput 2025 · DOI

TL;DR

This paper introduces a novel hybrid quantum-classical algorithm for solving the Max-Cut problem, a fundamental optimization challenge. By leveraging linear programming to "shrink" large problems into smaller ones, it makes them tractable for current noisy quantum hardware, while also developing a method for better parameter estimation for quantum algorithms.

What Problem Does This Paper Address?

Combinatorial optimization problems, like Max-Cut, are notoriously difficult for classical computers to solve optimally. While quantum computing promises a potential speedup, current quantum hardware is limited in size and prone to noise. This means that even if quantum algorithms can theoretically solve these problems faster, they can only handle relatively small instances. The challenge, therefore, is to bridge this gap: how can we harness the power of quantum computation for larger, more complex optimization problems given the limitations of today's quantum hardware? This paper tackles this by integrating classical optimization techniques with quantum algorithms to overcome these limitations.

Methods

The core of the proposed method is a hybrid approach that combines classical integer programming (IP) techniques with quantum approximate optimization algorithm (QAOA). Here's a breakdown:

  • Problem Shrinking via Linear Programming (LP) Relaxation: The authors use a well-established technique called "shrinking" from classical IP. They first solve a linear programming relaxation of the Max-Cut problem. The solution to this relaxation provides "correlations" between vertices, indicating whether they are likely to be in the same or different partitions in an optimal cut. These correlations are then used to identify pairs of vertices that can be merged into a single "super-vertex." This process effectively reduces the size of the problem. The key innovation here is using LP relaxations to guide this shrinking process, aiming to preserve optimality.
  • QAOA for the Shrunk Problem: The significantly smaller, shrunk problem is then fed into QAOA, a quantum algorithm designed to find approximate solutions.
  • Parameter Estimation for QAOA: A significant contribution is the development of a method to derive good parameters for QAOA, specifically for weighted Max-Cut. This is crucial because QAOA's performance heavily depends on these parameters, and finding them classically can be computationally expensive. The authors derive an analytical formula for the expectation value of depth-1 QAOA and use it to propose a parameter estimate that works well even for arbitrary instances, reducing the need for costly classical parameter optimization.
  • Reconstruction: After solving the shrunk problem with QAOA, the solution is "unshrunk" to obtain a feasible solution for the original, larger problem.

Datasets

The paper evaluates its approach on several types of instances:

  • Small, Artificial Instances: These are small (4 vertices) graphs designed to test the assumptions behind the QAOA parameter estimation. They include ring, star, complete graphs, and rings with chords, with weights drawn from uniform or normal distributions.
  • "2x3gns" Instances: These are derived from shrinking a 2x3 grid graph.
  • Large Instances: These include a 10x10 toroidal grid graph ("t2g10_5555") and a fully connected graph K100 ("ising2.5-100_5555") with 100 vertices. These are chosen to test the scalability of the method and are significantly larger than what current quantum hardware can handle directly.
  • Erdős-Rényi Random Graphs: These are used to compare the LP-based shrinking with other methods, with varying densities to explore different problem regimes.

Key Insights and Ideas

  • LP-guided shrinking is powerful: Using the solution of a linear programming relaxation to guide the vertex merging process is more effective than random shrinking. It preserves more of the problem's structure and leads to better solutions.
  • QAOA parameter estimation is crucial and achievable: Finding good QAOA parameters is a bottleneck. The authors' analytical approach provides a practical way to estimate these parameters, making QAOA more accessible for near-term hardware.
  • Hybrid approaches are the way forward: The paper strongly advocates for combining classical and quantum strengths. Classical methods handle the heavy lifting of problem reduction and relaxation, while quantum computers tackle the core optimization of the reduced problem.
  • Depth-1 QAOA has limitations: While the proposed parameter estimation works well for depth-1 QAOA, the results suggest that deeper QAOA circuits are likely needed for true quantum advantage, highlighting the ongoing need for hardware improvements.

Key Results

  • The hybrid algorithm successfully reduces the size of Max-Cut instances, making them solvable on current quantum hardware (up to 10 qubits used in experiments).
  • For small instances, the LP-based shrinking combined with QAOA achieved approximation ratios comparable to or better than solving the shrunk problem optimally with classical IP, especially when using the derived parameter estimate.
  • The QAOA parameter estimate (Eq. 16) showed good performance across various instances, with a maximum deviation of at most 13% from the optimal expectation value even on instances that didn't meet the assumptions for provable optimality.
  • For larger instances (100 vertices), the method demonstrated a significant increase in approximation ratio when shrinking the problem size, indicating its potential for tackling larger problems.
  • The LP-based shrinking consistently outperformed a recursive QAOA (RQAOA) approach, especially on sparse instances, achieving approximation ratios above 99.7% in some cases.

Limitations and Future Work

  • Noise in Quantum Hardware: The experiments were significantly impacted by noise, especially for larger qubit counts. This limits the depth of QAOA circuits that can be meaningfully executed.
  • Depth-1 QAOA Limitations: The paper acknowledges that depth-1 QAOA often falls short of returning optimal solutions, and deeper circuits are desirable for better performance.
  • Instance Size Limitations: While the method reduces problem size, the experiments were still constrained by the available quantum hardware (at most 10 qubits used).
  • Future Work: The authors suggest several avenues:
  • Incorporating quantum hardware characteristics (like graph topology preferences) into the shrinking process.
  • Exploring other methods for deriving correlations.
  • Testing the algorithm on a wider range of instances to better understand its performance.
  • Replacing depth-1 QAOA with higher-depth QAOA, warm-start QAOA, or other quantum algorithms like quantum annealing.

Summary updated

BibTeX
@article{wagner2025enhancing,
  author = {Friedrich Wagner and Jonas Nüßlein and Frauke Liers},
  title = {{Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming}},
  journal = {ACM Trans. Quantum Comput.},
  year = {2025},
  doi = {10.1145/3711935},
}
Figure