Quantum-Enhanced Greedy with QAOA (QEGQ): A Hybrid Algorithm for Set Cover with Sub-exponential Expected Runtime
Yalla Jnan Devi Satya Prasad · 2025
We present Quantum-Enhanced Greedy with QAOA (QEGQ), a hybrid quantum-classical algorithm for Set Cover that preserves the classical \(H_n\le\ln n+O(1)\) approximation ratio while offering conditional sub-exponential speedups. QEGQ replaces the classical greedy selection with fixed-point amplitude amplification, achieving \(O(\sqrt{m/M_t})\) oracle calls per step under the Heavy-Hitters condition (\(M_t\ge m^{\alpha}\)). We integrate QAOA-based batch refinement, demonstrated to yield up to 12% quality improvements in structured instances, and quantum-accelerated SDP/LP subroutines for fractional cover tightening. We provide detailed quantum circuit constructions (QROM, reversible population count), rigorous runtime and resource analyses including real-device gate counts and wall-clock estimates, and noise-resilience strategies with hybrid fallbacks. Empirical validation on sensor placement, document summarization, and synthetic families confirms robust Heavy-Hitters behavior (α ≥ 0.28) and quantifies performance degradation in adversarial instances. Our results establish practical guidelines for NISQ implementation, identify critical hardware targets for quantum advantage, and open pathways for broader quantum-enhanced approximation algorithms.