Quantum Branch-and-Bound with QAOA-Enhanced Upper Bounds for the Maximum Clique Problem: A Hybrid Framework for Conditional Exponential Speedup
Yalla Jnan Devi Satya Prasad · 2025
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) 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.