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 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 present Quantum-Enhanced Greedy with QAOA (QEGQ), a hybrid quantum-classical algorithm for Set Cover that preserves the classical Hn≤lnn+O(1) approximation ratio while offering conditional sub-exponential speedups. QEGQ replaces the classical greedy selection with fixed-point amplitude amplification, achieving O(m/Mt) oracle calls per step under the Heavy-Hitters condition (Mt≥mα). 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 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 paper presents a comprehensive theoretical framework that unifies various hybrid quantumclassical optimization approaches for combinatorial problems. Building upon recent advances in Quantum Approximate Optimization Algorithm (QAOA) and quantum-enhanced heuristics, we establish a mathematical foundation that connects amplitude amplification, counterdiabatic annealing, and classical relaxation techniques. We derive general convergence criteria and performance bounds for hybrid algorithms, demonstrating how quantum subroutines can be systematically integrated with classical optimization methods. The framework encompasses both unconstrained and constraint-preserving formulations, providing theoretical guarantees for problem classes including graph optimization, scheduling, and resource allocation. We analyze the trade-offs between quantum circuit depth, classical preprocessing overhead, and solution quality, establishing conditions under which exponential or polynomial speedups can be achieved. Our theoretical analysis reveals fundamental limitations and opportunities in hybrid algorithm design, offering guidelines for selecting appropriate quantum-classical decompositions based on problem structure. This work contributes to the growing understanding of quantum advantage in optimization and provides a roadmap for developing provably efficient hybrid algorithms across diverse application domains.
Abstract The maximum clique problem(MCP) is to find the largest complete subgraph in an undirected graph, that is, the subgraph in which there are edges between every two different vertices. It is an NP-Hard problem with wide applications, including bioinformatics, social networks, data mining, and other fields. This paper proposes an improved algorithm that dynamically tracks the maximum clique size by encoding prior constraints on the vertex count—derived from Turán's theorem and complete graph properties—into global variables through quantum circuit pre-detection. The algorithm further synergizes with Grover's search to optimize the solution space. Our auxiliary-qubit encoding scheme dynamically tracks clique sizes during quantum search, eliminating iterative measurements, achieving MCP solution with $O\left ( \sqrt{2^{n } } \right ) $ Grover iterations and $O\left ( 1 \right ) $ measurements. This represents an n-fold improvement over state-of-the-art Grover-based methods, which require O(n2n) iterations and O(n) measurements for n-vertex graphs. We validate algorithmic correctness through simulations on IBM's Qiskit platform and benchmark qubit/gate efficiency against existing Grover-based MCP solvers.
Abstract The maximum clique problem (MCP) is to find the largest complete subgraph in an undirected graph, that is, the subgraph in which there are edges between every two different vertices. It is an NP-Hard problem with wide applications, including bioinformatics, social networks, data mining, and other fields. This paper proposes an enhanced quantum solution method that introduces a pre-detection phase based on a hybrid heuristic algorithm and a vertex pruning strategy, encoding the prior constraints on clique size into quantum registers as global information. It encodes the prior constraints on clique size into quantum registers as global information. In contrast, state-of-the-art Grover-based methods for n-vertex graphs require O ( n 2 n ) iterations and O ( n ) measurements. By leveraging a global information encoding mechanism, the proposed method compresses the number of iterations to O ( 2 n ) and only needs a constant number of measurements to identify all maximum cliques. We validate algorithmic correctness through simulations on IBM’s Qiskit platform and benchmark qubit/gate efficiency against existing Grover-based MCP solvers.
Large-scale combinatorial and continuous optimisation problems remain intractable for classical algorithms as problem dimensionality scales. Quantum computing offers advantages through parallelism, amplitude amplification, and tunnelling, but practical realisation on near-term noisy intermediate-scale quantum (NISQ) devices demands careful algorithm design balancing advantage against noise resilience and circuit depth constraints. This paper presents the Quantum Optimisation Algorithm Suite (QOAS), a systematic framework across four algorithmic paradigms: Adaptive QAOA with dynamic depth scheduling; Variational Quantum Eigensolver (VQE) for QUBO problems; hybrid Quantum Annealing (QA); and Grover-enhanced Branch and Bound (GBB) for constrained integer programming. QOAS is benchmarked on five problem classes (MaxCut, TSP, Portfolio, Drug-Target, Feature Selection) across n = 12-84 qubits on IBM Quantum Eagle (127-qubit) and Falcon (27-qubit). Adaptive QAOA achieves approximation ratio 0.924 (SD = 0.018) for MaxCut at n = 48 -- outperforming standard QAOA (0.848) and Goemans-Williamson (0.878) at equivalent wall-clock time. GBB achieves 28.4x speedup over classical branch-and-bound for the n = 24 drug-target problem. QOAS provides systematic methodology for algorithm selection, circuit depth optimisation, and noise mitigation for NISQ workloads.