Adaptive Graph Shrinking for Quantum Optimization of Constrained Combinatorial Problems

Monit Sharma, Hoong Chuin LauarXiv 2025 · DOI · arXiv

TL;DR

Researchers have developed a hybrid classical-quantum framework that uses adaptive graph shrinking to compress large, constrained optimization problems into smaller versions that fit on today’s limited quantum hardware. By making the shrinking process "constraint-aware" and adding a smart "repair" step, the team successfully solved complex problems like the Knapsack and Quadratic Assignment problems with significantly fewer qubits while maintaining high solution quality.

What Problem Does This Paper Address?

Quantum algorithms like the Quantum Approximate Optimization Algorithm (QAOA) and Variational Quantum Eigensolver (VQE) are promising tools for solving NP-hard combinatorial problems. However, we are currently in the "NISQ" (Noisy Intermediate-Scale Quantum) era, where hardware is limited by low qubit counts and high noise.

When we translate a real-world constrained problem (like scheduling or logistics) into a format a quantum computer understands—specifically QUBO (Quadratic Unconstrained Binary Optimization)—the number of required variables often explodes. For example, handling inequality constraints usually requires adding many "slack variables," quickly exceeding the 50–100 qubits available on modern processors. This paper tackles the "scalability gap": how do we solve large, constrained problems on small, noisy quantum devices without losing the problem's essential structure?

Methods

The authors propose a multi-stage hybrid pipeline:

  1. QUBO to Max-Cut Transformation: They first convert the constrained problem into a weighted Max-Cut graph. This allows them to treat optimization as a graph partitioning problem.
  2. SDP-Guided Correlation: They use a classical technique called Semi-Definite Programming (SDP) relaxation to calculate how strongly different variables are correlated. If two variables are highly correlated, they likely "belong together" in the final solution.
  3. Constraint-Aware Merging (Proactive): This is the "secret sauce." Unlike standard graph shrinking, their algorithm penalizes merging nodes that would obviously violate constraints (e.g., merging two items in a Knapsack problem that together exceed the weight limit).
  4. Spectral Stopping Criterion: Instead of shrinking the graph to a random size, they use the eigenvalues of the graph Laplacian (spectral energy) to determine the optimal point to stop shrinking, ensuring the "structural essence" of the problem is preserved.
  5. Quantum Optimization: The shrunken, hardware-compatible problem is solved using a quantum simulator (VQE).
  6. Verification and Repair (Reactive): Since shrinking is a heuristic, the reconstructed solution might be slightly infeasible. They apply a lightweight, problem-specific greedy repair to restore feasibility.

Datasets

The framework was evaluated on three classic NP-hard benchmark families:

  • Multidimensional Knapsack Problem (MDKP): Selecting items to maximize profit without exceeding multiple resource capacities.
  • Maximum Independent Set (MIS): Finding the largest set of vertices in a graph where no two are connected.
  • Quadratic Assignment Problem (QAP): Assigning facilities to locations to minimize transport costs (notoriously difficult even for classical solvers). The authors used standard benchmark instances from libraries like QAPLIB and other classically "hard" datasets.

Key Insights and Ideas

  • Constraints as Weights: By scaling penalty terms correctly in the QUBO, the SDP solver "sees" the constraints. This ensures that the correlations used for shrinking aren't just based on the objective function, but also on the rules of the game.
  • Adaptive vs. Static: The paper shows that "Adaptive Shrinking"—where the algorithm decides how much to compress based on the specific instance—outperforms "Fixed Shrinking" (e.g., always reducing by 50%).
  • The "Aha" Moment: The researchers found that VQE performance improves significantly when constraints are embedded directly into the shrinking logic. It’s not just about making the problem smaller; it’s about making the smaller problem easier for the quantum solver to navigate.

Key Results

  • Feasibility: The constraint-aware approach consistently produced feasible solutions across all test cases, whereas "blind" shrinking often led to unrepairable violations.
  • Solution Quality: On MDKP instances, the "Adaptive GS" (Graph Shrinking) method achieved optimality gaps as low as 0.21%, significantly outperforming direct VQE on the full problem (which often failed to find a solution or hit "infinite" gaps).
  • Resource Efficiency: The method successfully reduced problems requiring over 120 qubits down to 40–80 qubits, making them runnable on near-term hardware.
  • Comparison: While classical CPLEX is still faster and more accurate for these specific instances, the hybrid framework proved that quantum solvers can be made "competitive" and scalable for constrained problems that were previously out of reach.

Limitations and Future Work

  • Classical Overhead: Calculating SDP correlations and recalculating them during the shrinking process adds classical computational cost. For very large graphs, this preprocessing could become a bottleneck.
  • Heuristic Nature: The approach does not provide a formal guarantee of optimality; it is a "best-effort" heuristic designed for practical scalability.
  • Hardware Noise: Most results were obtained via simulators (Qiskit AerSimulator). The authors acknowledge that testing on real, noisy quantum hardware is the next critical step to see how error mitigation strategies interact with the shrunken graphs.
  • Future Directions: They suggest using Graph Neural Networks (GNNs) to learn better merging strategies and exploring more complex "reconstruction pipelines" to reduce information loss during the un-shrinking phase.

Summary updated

Abstract

A range of quantum algorithms, especially those leveraging variational parameterization and circuit-based optimization, are being studied as alternatives for solving classically intractable combinatorial optimization problems (COPs). However, their applicability is limited by hardware constraints, including shallow circuit depth, limited qubit counts, and noise. To mitigate these issues, we propose a hybrid classical--quantum framework based on graph shrinking to reduce the number of variables and constraints in QUBO formulations of COPs, while preserving problem structure. Our approach introduces three key ideas: (i) constraint-aware shrinking that prevents merges that will likely violate problem-specific feasibility constraints, (ii) a verification-and-repair pipeline to correct infeasible solutions post-optimization, and (iii) adaptive strategies for recalculating correlations and controlling the graph shrinking process. We apply our approach to three standard benchmark problems: Multidimensional Knapsack (MDKP), Maximum Independent Set (MIS), and the Quadratic Assignment Problem (QAP). Empirical results show that our approach improves solution feasibility, reduces repair complexity, and enhances quantum optimization quality on hardware-limited instances. These findings demonstrate a scalable pathway for applying near-term quantum algorithms to classically challenging constrained optimization problems.
BibTeX
@misc{sharma2025adaptive,
  author = {Monit Sharma and Hoong Chuin Lau},
  title = {{Adaptive Graph Shrinking for Quantum Optimization of Constrained Combinatorial Problems}},
  year = {2025},
  eprint = {2506.14250},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2506.14250},
  howpublished = {arXiv},
}
Figure