Formulation of the Maximum Independent Set Problem on QDeep Hybrid Solver: Benchmarking Quantum Solutions on Real-World Graphs

The Maximum Independent Set (MIS) problem is a fundamental NP-hard problem with widely known applications in network science, scheduling, bioinformatics, and combinatorial optimization. Recent advances in hybrid quantum–classical computing have introduced new opportunities for solving large-scale discrete optimization problems through Quadratic Unconstrained Binary Optimization (QUBO) formulations. In this work, we investigate the performance of the QDeep QonQuester Cloud platform, a secure hybrid quantum–classical optimization system, for solving MIS instances of varying scales and graph densities. We encode MIS as a QUBO problem and evaluate QDeep’s black-box solver selection mechanism, which automatically chooses between quantum, heuristic, and classical backends based on input structure. Our work highlights the strengths and limitations of hybrid QUBO-based solvers for combinatorial graph problems and provides insights for applying quantum-ready optimization tools to MIS and related NP-hard problems. The results indicate that hybrid approaches – such as QDeep – offer a practical pathway toward using quantum computing concepts for real-world optimization tasks before full-scale quantum hardware becomes widely available.