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 · 2025
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.