Quantum-inspired graph shrinking improves constrained optimisation on near-term hardware.

Research presents a hybrid classical-quantum framework utilising graph shrinking to simplify combinatorial optimisation problems, such as the multidimensional knapsack problem, maximum independent set, and quadratic assignment problem. This method preserves problem structure, improves solution feasibility, reduces repair complexity and enhances optimisation on limited hardware.

The pursuit of solutions to complex combinatorial optimisation problems (COPs), such as logistics, finance, and machine learning tasks, increasingly explores the potential of quantum computing. However, current quantum hardware presents limitations in circuit depth, qubit availability, and susceptibility to noise, hindering the practical application of these algorithms. Researchers are therefore developing methods to reduce the complexity of these problems before they are processed by quantum computers, allowing them to be tackled with existing technology. Monit Sharma from Singapore Management University, and Hoong Chuin Lau from both Singapore Management University and the Institute of High Performance Computing, A*STAR, detail one such approach in their article, “Adaptive Graph Shrinking for Quantum Optimization of Constrained Combinatorial Problems”. Their work introduces a hybrid classical-quantum framework utilising graph shrinking, a technique to reduce the number of variables and constraints within a QUBO (Quadratic Unconstrained Binary Optimisation) formulation, while maintaining essential problem structure.

Recent advancements in quantum computing offer a potential route to solving classically intractable combinatorial optimisation problems, yet current quantum hardware presents significant limitations regarding algorithm scalability and performance. This study details a hybrid classical-quantum framework designed to address these limitations and enhance the applicability of quantum computation to challenging optimisation tasks. The methodology centres on a novel approach to problem reduction, coupled with a robust verification and repair pipeline, ultimately demonstrating a scalable pathway for utilising near-term quantum computers.

The core innovation of this framework lies in its ability to intelligently reduce the size of Quadratic Unconstrained Binary Optimisation (QUBO) formulations—mathematical models used to represent optimisation problems where the goal is to find the best assignment of binary variables—without sacrificing critical problem characteristics. Researchers achieve this through constraint-aware shrinking, a process that prevents the merging of variables likely to violate problem-specific feasibility constraints. This careful approach ensures that the reduced problem remains representative of the original, allowing for meaningful solutions to be obtained from quantum computation. Furthermore, the framework incorporates a verification-and-repair pipeline that corrects any infeasible solutions generated post-optimisation, enhancing the reliability and accuracy of the results.

The methodology leverages three core innovations to achieve efficient problem reduction and solution refinement. Firstly, constraint-aware shrinking proactively prevents the merging of variables that would likely introduce infeasibility, maintaining solution validity throughout the process. Secondly, a robust verification-and-repair pipeline systematically corrects any infeasible solutions generated after quantum optimisation, ensuring the practicality of the obtained results. Finally, adaptive strategies dynamically recalculate correlations and regulate the graph shrinking process itself, optimising the balance between problem reduction and solution accuracy. Researchers applied this approach to three established benchmark problems: the Multidimensional Knapsack Problem (MDKP), the Maximum Independent Set (MIS), and the Quadratic Assignment Problem (QAP).

Analysis of experimental results reveals a significant improvement in solution feasibility, alongside a reduction in the complexity of the repair process and enhanced optimisation quality on instances constrained by hardware limitations. The framework consistently generates feasible solutions for problems that previously yielded infeasible results.

The study’s results underscore the importance of hybrid classical-quantum approaches for tackling complex optimisation problems. By combining the strengths of both classical and quantum computation, researchers can overcome the limitations of each individual approach and achieve superior performance.

These findings demonstrate that the proposed framework effectively addresses the challenges of applying quantum computation to complex optimisation problems. The ability to intelligently reduce problem size, coupled with a robust verification and repair pipeline, enables researchers to obtain meaningful solutions even with limited quantum resources. The observed scaling behaviour provides valuable insights into the limitations of current quantum hardware and guides the development of more efficient algorithms and architectures.

These findings demonstrate a scalable pathway for applying near-term quantum computers to classically challenging constrained optimisation problems. The observed scaling behaviour—where increased qubit counts correlate with increased circuit depth and gate counts—confirms the expected increase in computational complexity as problem size grows. This understanding is crucial for developing effective strategies for mitigating the limitations of current quantum hardware.

The data reveals a clear relationship between problem complexity and resource allocation in quantum computations. Experiments utilised a broad spectrum of qubit counts, ranging from 11 to 122, with an average of 50-60 qubits commonly employed. This variation indicates investigations into problems of differing scales and inherent difficulty, providing valuable insights into the scalability of the framework. Correspondingly, circuit depth extended from 42 to 137, averaging around 60-70, and demonstrated a tendency to increase alongside qubit count, as more complex problems logically demand more extensive computational pathways. Gate count, ranging from 386 to 1704 with an average of 700-800, and the number of trainable parameters, spanning 276 to 1382 with an average of 600-700, also correlated with qubit count and depth, reflecting the increasing complexity of the optimisation landscape. This correlation highlights the importance of carefully managing computational resources and optimising algorithm parameters to achieve efficient performance. Researchers observed that the adaptive strategies effectively balanced these competing demands, ensuring that the framework remained scalable and efficient.

Future research will focus on extending the framework to handle even larger and more complex problems, exploring alternative problem reduction techniques, and investigating the potential of incorporating machine learning algorithms to further optimise the solution process. Researchers also plan to investigate the performance of the framework on different quantum hardware platforms and explore the potential of developing specialised quantum architectures tailored to the specific requirements of the proposed algorithm. This ongoing research will contribute to the advancement of quantum computation and its application to real-world problems.