Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Hybrid Quantum-Classical Steiner Tree Optimization: A Novel Framework Combining Amplitude Amplification, QAOA, and SDP Relaxations

Yalla Jnan Devi Satya Prasad, Sahil Ram Chatrati, Shaik Fathima Masthan

Published Oct 6, 2025• 1 citation
Publisher

Abstract

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.

DOI
10.36227/techrxiv.175977614.47893700/v1

Related papers

Theoretical Foundations of Hybrid Quantum-Classical Optimization, unified Framework for Combinatorial Problems

Jeffrey Quinn Cordova, Punith Khandelwal

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.

•Oct 31, 2025•0 citations

Quantum-Enhanced Greedy with QAOA (QEGQ): A Hybrid Algorithm for Set Cover with Sub-exponential Expected Runtime

Yalla Jnan Devi Satya Prasad

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.

•Oct 6, 2025•0 citations

A scalable quantum-enhanced greedy algorithm for maximum independent set problems

Elisabeth Wybo, Jami Rönkkö, Olli Hirviniemi +2 more

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.

quant-pharXiv:2601.21923•Jan 30, 2026•0 citations

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

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.

•Oct 6, 2025•0 citations

A NISQ-Aware Hybrid Quantum-Classical Framework for Scalable Combinatorial Optimization

Haolong Ding, Mohan Wu, Yin Xu +1 more

Scalable combinatorial optimization under resource-constrained quantum hardware remains a fundamental challenge in the Noisy Intermediate-Scale Quantum (NISQ) era, due to the mismatch between exponentially growing solution spaces and limited quantum computational capacity. In this work, we propose a NISQ-aware hybrid quantum-classical optimization framework that reformulates large-scale combinatorial optimization as a resource-bounded distribution evolution process. Instead of directly optimizing individual solutions, the proposed framework operates on a probabilistic representation of the solution space, enabling efficient exploration under hardware constraints. Specifically, large problem instances are decomposed into qubit-compatible subproblems via clustering-based decomposition, ensuring resource-bounded optimization. Within each subproblem, a quantum genetic algorithm evolves the solution distribution, while periodically embedded amplitude amplification acts as a controlled quantum enhancement mechanism that accelerates convergence without increasing circuit depth. A classical refinement stage ensures global solution consistency. Extensive experiments on benchmark and synthetic datasets demonstrate that the proposed framework consistently outperforms classical and quantum-inspired baselines, with performance gains that become more pronounced as problem scale increases. This scale-dependent behavior indicates that scalability is achieved through structured decomposition rather than increased quantum complexity. Noise simulations further confirm robustness under realistic NISQ conditions, and ablation studies validate that both quantum evolutionary search and amplitude amplification contribute significantly to performance improvements.

quant-pharXiv:2606.00541•Jun 2, 2026•0 citations

Quantum-Assisted Hybrid Optimization for Graph-Based Combinatorial Optimization

Srinivasarao Thota, N Shilpa, Nasr Al Din Ide

Graph-based combinatorial optimization problems are computationally challenging for classical optimization techniques due to their NP-hard nature. This paper proposes a novel Quantum-Assisted Hybrid Optimization Algorithm (QAHOA) that integrates the Quantum Approximate Optimization Algorithm (QAOA), spectral graph theory, and classical optimization strategies for graph-based combinatorial optimization. The developed framework uses spectral initialization via the graph Laplacian Fiedler vector to provide structurally informed starting variational parameters, aiming to stabilize the parameter search space and improve convergence trajectories under noisy conditions. The mathematical framework, alongside a convergence analysis to first-order stationary points, is provided to establish theoretical baseline properties. Evaluated on synthetic Erdős–Rényi random graph instances, the current study serves as a preliminary, small-to-medium-scale proof-of-concept. Controlled evaluations demonstrate that the proposed QAHOA achieves marginal yet stable and statistically significant improvements in mean cut values and approximation ratios over classical Greedy heuristics, Simulated Annealing, the standard QAOA, and Warm-Start QAOA. Formal paired hypothesis testing mathematically verifies the stability of the framework, while preliminary 4-qubit hardware executions demonstrate baseline architectural compatibility under physical NISQ noise channels.

IEEE Access•Jan 1, 2026•0 citations
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.
We present Quantum-Enhanced Greedy with QAOA (QEGQ), a hybrid quantum-classical algorithm for Set Cover that preserves the classical Hn≤ln⁡n+O(1)H_n\le\ln n+O(1)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)O(\sqrt{m/M_t})O(m/Mt​​) oracle calls per step under the Heavy-Hitters condition (Mt≥mαM_t\ge m^{\alpha}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 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-ppp 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=4p=4p=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.
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.
Scalable combinatorial optimization under resource-constrained quantum hardware remains a fundamental challenge in the Noisy Intermediate-Scale Quantum (NISQ) era, due to the mismatch between exponentially growing solution spaces and limited quantum computational capacity. In this work, we propose a NISQ-aware hybrid quantum-classical optimization framework that reformulates large-scale combinatorial optimization as a resource-bounded distribution evolution process. Instead of directly optimizing individual solutions, the proposed framework operates on a probabilistic representation of the solution space, enabling efficient exploration under hardware constraints. Specifically, large problem instances are decomposed into qubit-compatible subproblems via clustering-based decomposition, ensuring resource-bounded optimization. Within each subproblem, a quantum genetic algorithm evolves the solution distribution, while periodically embedded amplitude amplification acts as a controlled quantum enhancement mechanism that accelerates convergence without increasing circuit depth. A classical refinement stage ensures global solution consistency. Extensive experiments on benchmark and synthetic datasets demonstrate that the proposed framework consistently outperforms classical and quantum-inspired baselines, with performance gains that become more pronounced as problem scale increases. This scale-dependent behavior indicates that scalability is achieved through structured decomposition rather than increased quantum complexity. Noise simulations further confirm robustness under realistic NISQ conditions, and ablation studies validate that both quantum evolutionary search and amplitude amplification contribute significantly to performance improvements.
Graph-based combinatorial optimization problems are computationally challenging for classical optimization techniques due to their NP-hard nature. This paper proposes a novel Quantum-Assisted Hybrid Optimization Algorithm (QAHOA) that integrates the Quantum Approximate Optimization Algorithm (QAOA), spectral graph theory, and classical optimization strategies for graph-based combinatorial optimization. The developed framework uses spectral initialization via the graph Laplacian Fiedler vector to provide structurally informed starting variational parameters, aiming to stabilize the parameter search space and improve convergence trajectories under noisy conditions. The mathematical framework, alongside a convergence analysis to first-order stationary points, is provided to establish theoretical baseline properties. Evaluated on synthetic Erdős–Rényi random graph instances, the current study serves as a preliminary, small-to-medium-scale proof-of-concept. Controlled evaluations demonstrate that the proposed QAHOA achieves marginal yet stable and statistically significant improvements in mean cut values and approximation ratios over classical Greedy heuristics, Simulated Annealing, the standard QAOA, and Warm-Start QAOA. Formal paired hypothesis testing mathematically verifies the stability of the framework, while preliminary 4-qubit hardware executions demonstrate baseline architectural compatibility under physical NISQ noise channels.