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.
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.
We investigate a hybrid quantum-classical algorithm for solving the Maximum Independent Set (MIS) problem on regular graphs, combining the Quantum Approximate Optimization Algorithm (QAOA) with a minimal degree classical greedy algorithm. The method leverages pre-computed QAOA angles, derived from depth-p QAOA circuits on regular trees, to compute local expectation values and inform sequential greedy decisions that progressively build an independent set. This hybrid approach maintains shallow quantum circuit and avoids instance-specific parameter training, making it well-suited for implementation on current quantum hardware: we have implemented the algorithm on a 20 qubit IQM superconducting device to find independent sets in graphs with thousands of nodes. We perform tensor network simulations to evaluate the performance of the algorithm beyond the reach of current quantum hardware and compare to established classical heuristics. Our results show that even at low depth (p=4), the quantum-enhanced greedy method significantly outperforms purely classical greedy baselines as well as more sophisticated approximation algorithms. The modular structure of the algorithm and relatively low quantum resource requirements make it a compelling candidate for scalable, hybrid optimization in the NISQ era and beyond.
The transition from theoretical quantum computing to practical real-world applications heavily relies onhybrid quantum-classical architectures designed for NoisyIntermediate-Scale Quantum (NISQ) devices. Among these approaches, the Quantum Approximate Optimization Algorithm(QAOA) is a prominent strategy for addressing complex combinatorial optimization challenges, such as the NP-hard MaxCut problem. Instead of performing the entire computationon a quantum processor, QAOA utilizes a quantum circuit toevaluate a parameterized cost function, whereas a classical optimizer refines the parameters iteratively. This study presentsa rigorous empirical evaluation comparing the performanceof QAOA against established classical solvers on small-scaleMax-Cut instances. All experiments were implemented andexecuted using Python (Qiskit Aer) on a state-vector simulator.Using Erdős–Rényi random graphs and regular graphs with4 to 20 nodes, we benchmark QAOA at depths p = 2 andp = 3 against simulated annealing, the Goemans–WilliamsonSDP-based algorithm, and a linear-time greedy heuristic. Ourexperimental results demonstrate that low-depth QAOA implementations exhibit severe performance degradation, prohibitive computational overhead (O(2^n) scaling), and low convergencerates compared to mature classical algorithms. At 20 nodes,QAOA (p = 2) achieves only a 0.467 approximation ratio versus0.856 for Goemans–Williamson, with a 210× runtime slowdownover greedy heuristics
We present QBB-QAOA, a novel hybrid quantumclassical algorithm for the Maximum Clique Problem (MCP) that integrates quantum subroutines within a classical branch-and-bound framework. Our approach combines three key innovations: (1) Groveramplified subtree verification with noise-adaptive depth selection, (2) QAOA-based upper bound estimation using calibrated graph-theoretic relaxations, and (3) dynamic fallback mechanisms with hardwarespecific optimizations. We prove conditional exponential reductions in the effective search exponent for structured graph families, achieving µ ′ = αµ+o(1) < µ where α ∈ [0.6, 0.9] depends on QAOA bound quality and graph clustering structure. Empirical validation demonstrates that 67% of real-world networks exhibit the required clustering properties (Q > 0.3) with QAOA achieving improvement factors α < 0.85. For practical instances with n ∈ [50, 200], we demonstrate wall-clock speedups of 4-10× over classical branch-and-bound on NISQ devices with gate error rates p gate ≤ 5 × 10 −4. Our implementation includes comprehensive error mitigation (ZNE, dynamical decoupling), adaptive threshold-based policies, and cross-platform compatibility (IBM, IonQ, trapped-ion systems). Detailed resource analysis shows quantum subroutine costs of τ g ≈ 15.7 ms per Grover call and τ q ≈ 120 s per QAOA optimization, with break-even conditions achievable for structured instances. The mapping function F : ⟨H ub ⟩ → U q generalizes across graph families with mean absolute error ≤ 0.5 vertices, enabling robust upper bound estimation without per-instance recalibration.
We introduce a novel hybrid quantum-classical algorithm for the Minimum Steiner Tree problem that integrates three key innovations to achieve practical improvements on structured graph families. First, we employ a fast classical preprocessing pipeline, including geometric ranking, connectivity pruning, and a lightweight ML surrogate, to reduce the candidate Steiner vertex set by 60-80% while preserving 95% of optimal solutions. Second, we leverage a custom "Greedy-Mixer" QAOA ansatz tailored to terminal clustering, paired with quantum amplitude amplification, to explore exponentially many subsets with O(2 m/2) oracle complexity. Third, we integrate quantum SDP relaxations to tighten lower bounds, improving threshold selection in amplitude amplification and boosting success rates by 26% over classical bounds. Under structural assumptions (bounded local treewidth), we prove a conditional approximation guarantee α < 1.55 in expected time O(2 θm poly(n)) with θ < 1 2. Extensive experiments on planar, random geometric, and VLSI-like graphs (up to n = 50, m ≤ 20) demonstrate a 4-5× reduction in quantum resources and a 3-8% improvement in approximation ratio versus classical heuristics, with statistically significant advantages (p < 0.01) for gate errors 1%, 200 measurement shots, and mixer depths p ≥ 4. This work establishes a practical pathway toward NISQ-era quantum advantage in combinatorial network design.
This study presents a rigorous empirical evaluation of the Quantum Approximate Optimization Algorithm (QAOA) within a hybrid quantum-classical framework for solving the NP-hard Max-Cut problem. Using Python and Qiskit Aer statevector simulations, we benchmark QAOA (depths p = 2 and p = 3) against established classical algorithms, including simulated annealing, the Goemans–Williamson algorithm, and greedy heuristics, across Erdős–Rényi and regular graphs with 4 to 20 nodes (100 instances per size). Results demonstrate that low-depth QAOA suffers from significant performance degradation, achieving a 0.467 approximation ratio at 20 nodes compared to 0.856 for Goemans–Williamson, alongside a 210× runtime overhead. Convergence analysis further reveals low optimality probabilities and high iteration costs, highlighting limitations of variational optimization in NISQ-era devices. This work provides a reproducible benchmarking framework and contributes to a realistic assessment of near-term quantum advantage.
This study presents a rigorous empirical evaluation of the Quantum Approximate Optimization Algorithm (QAOA) within a hybrid quantum-classical framework for solving the NP-hard Max-Cut problem. Using Python and Qiskit Aer statevector simulations, we benchmark QAOA (depths p = 2 and p = 3) against established classical algorithms, including simulated annealing, the Goemans–Williamson algorithm, and greedy heuristics, across Erdős–Rényi and regular graphs with 4 to 20 nodes (100 instances per size). Results demonstrate that low-depth QAOA suffers from significant performance degradation, achieving a 0.467 approximation ratio at 20 nodes compared to 0.856 for Goemans–Williamson, alongside a 210× runtime overhead. Convergence analysis further reveals low optimality probabilities and high iteration costs, highlighting limitations of variational optimization in NISQ-era devices. This work provides a reproducible benchmarking framework and contributes to a realistic assessment of near-term quantum advantage.