Search papers, labs, and topics across Lattice.
This paper investigates Hybrid Quantum Neighborhood Selection (HQNS) as a resource-efficient method for tackling large-scale combinatorial optimization problems, specifically focusing on the Maximum Diversity Subset Selection Problem (MDSSP). By decomposing dense Quadratic Unconstrained Binary Optimization (QUBO) instances into manageable quantum subproblems, HQNS significantly reduces resource consumption while maintaining high solution quality. The results demonstrate that HQNS achieves a mean diversity score retention of 99.9908% compared to a parallel Simulated Annealing baseline, while drastically cutting wall-clock time, CPU utilization, and memory usage, thus paving the way for practical hybrid quantum optimization applications.
HQNS retains nearly all solution quality while slashing resource consumption, making hybrid quantum optimization feasible for large-scale problems.
Large-scale combinatorial optimization remains demanding for classical heuristics, particularly when dense Quadratic Unconstrained Binary Optimization (QUBO) formulations induce large memory footprints, high CPU utilization, and long execution times. While near-term quantum processors cannot yet deliver unconditional quantum advantage, hybrid architectures can provide practical value by reducing the resource burden. This paper presents a resource-efficiency study of Hybrid Quantum Neighborhood Selection (HQNS), a framework that decomposes large dense QUBO instances into bounded-width quantum subproblems via stochastic frontier selection. We evaluate HQNS on the Maximum Diversity Subset Selection Problem (MDSSP), focusing on the trade-off between solution quality retention and resource consumption. Benchmarks up to N=1000 candidates show that HQNS preserves 99.9908% of the mean diversity score of an 11-restart parallel Simulated Annealing baseline, while reducing wall-clock time by 94.91%, peak CPU utilization by 64.68%, and peak memory usage by 88.61%. The QPU execution time remains bounded within a 6-7 second envelope across scales, indicating that the quantum component is decoupled from the global QUBO dimension when the frontier size is fixed. These results suggest that HQNS provides a resource-aware pathway for deploying hybrid quantum optimization in practical large-scale settings, serving as an efficient architecture for incorporating near-term quantum processors into classical optimization pipelines.
