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

Elisabeth Wybo, Jami Rönkkö, Olli Hirviniemi, Jernej Rudi Finžgar, Martin Leib · 2026

Read A scalable quantum-enhanced greedy algorithm for maximum independent set problems by Elisabeth Wybo, Jami Rönkkö, Olli Hirviniemi, Jernej Rudi Finžgar, Martin Leib (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-21923.txt.

Introduction

Elisabeth Wybo and co-authors mix quantum and classical methods to solve a classic graph problem. The maximum independent set problem asks for the largest set of vertices with no edges between them. It appears in scheduling, coding, and network design, and it is hard to solve exactly at scale.

Their 2026 preprint studies a hybrid algorithm for regular graphs. It combines the Quantum Approximate Optimization Algorithm, using angles computed in advance, with a minimal-degree classical greedy method. The quantum part guides the search while the classical part finishes the job cheaply. Honest tests of such hybrids matter because they show where today's small quantum processors can genuinely help rather than merely participate.

Catalog record

CREATORElisabeth Wybo, Jami Rönkkö, Olli Hirviniemi, Jernej Rudi Finžgar, Martin Leib
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE49 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-21923

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A scalable quantum-enhanced greedy algorithm for maximum independent set problems Elisabeth Wybo, Jami Rönkkö, Olli Hirviniemi, Jernej Rudi Finžgar, Martin Leib Abstract 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 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 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. I Introduction Quantum computers promise new approaches for solving hard optimization problems Abbas et al. 2024 . In the current Noisy Intermediate-Scale Quantum (NISQ) era Preskill 2018 , hybrid quantum-classical algorithms have emerged as leading candidates to achieve quantum utility under realistic hardware constraints. A prominent example is the Quantum Approximate Optimization Algorithm (QAOA) Farhi et al. 2014 ; Blekos et al. 2024 which is a variational algorithm for solving combinatorial optimization problems that has been the subject of extensive theoretical, numerical and experimental investigation Farhi et al. 2014 ; Brandao et al. 2018 ; Wang et al. 2018 ; Basso et al. 2021 ; Farhi et al. 2020a ; Farhi et al. 2020b ; Farhi et al. 2022 ; Zhou et al. 2018 ; Pagano and et al. 2020 ; Harrigan et al. 2021 ; Ebadi et al. 2022 ; Byun et al. 2022 ; Kim et al. 2022 ; Farhi et al. 2025 . However, recent theoretical and numerical results provide a mixed outlook on the performance of QAOA. On the one hand, there is evidence that QAOA can outperform the worst-case bound of the best known classical approximation algorithm Goemans and Williamson 1995 for solving the MaxCut problem when the QAOA circuit depth p is sufficiently large but independent of the problem size Brandao et al. 2018 ; Crooks 2018 ; Wurtz and Lykov 2021 ; Farhi et al. 2025 . On the other hand, there are also rigorous indications that constant-depth QAOA has limitations Farhi et al. 2020a ; Farhi et al. 2020b ; Chou et al. 2021 ; Barak and Marwaha 2021 ; Anshu and Metger 2022 ; Chen et al. 2023 . For instance it provably cannot solve the Maximum Independent Set (MIS) problem to (near) optimality due to its locality Farhi et al. 2020a ; Farhi et al. 2020b . This implies that unbounded depth is a necessary, but not sufficient, condition for reaching (near) optimal solutions. However, scaling QAOA to larger problem sizes in practice remains challenging because current NISQ devices can only support shallow circuits before noise dominates Franca and Garcia-Patron 2020 ; Wang et al. 2021 ; De Palma et al. 2022 ; González-García et al. 2022 . A natural response to these limitations is to reconsider the role of the quantum algorithm itself. Rather than viewing QAOA as a standalone optimizer that must fully solve the problem, one can instead use it as a subroutine that enhances classical heuristics Brady and Hadfield 2024 ; Dupont and Sundar 2024 ; Dupont et al. 2023 ; Finžgar et al. 2024 . In this work, we adopt this perspective and study a quantum-enhanced greedy algorithm for the MIS problem Brady and Hadfield 2024 . Greedy algorithms are attractive because of their simplicity and scalability Frieze 1990 ; Frieze and Łuczak 1992 ; Boppana and Håldórsson 1992 ; Håldórsson 1997 ; Wormald 1995 . However, their decisions are based on limited information available at each step and can therefore miss important but intricate structure in the problem. The central idea of the hybrid approach is to improve these decisions using expectation values from QAOA. Specifically, at each iteration, a shallow QAOA circuit is executed on a residual problem graph to estimate expectation values of local observables, which are then used to guide the next greedy step Brady and Hadfield 2024 ; Finžgar et al. 2024 . In this way, the quantum processor provides structured guidance derived from an entangled quantum state, while the classical algorithm retains control over the iterative reduction of the problem. The central contribution of this work is an efficient and scalable version of the quantum-enhanced greedy algorithm that eliminates the need for variational parameter optimization thus retaining an overall linear-time complexity. Optimizing variational QAOA angles is widely recognized as a major bottleneck particularly as system size increases, due to highly non-convex energy landscapes and the onset of barren plateaus Wang et al. 2021 ; Cerezo et al. 2021 ; Larocca et al. 2025 . We bypass this challenge entirely by employing fixed-angle QAOA circuits with parameters derived from regular tree models (Bethe lattice like structures), which are well suited to problems on large d -regular graphs that resemble trees locally Streif and Leib 2020 ; Wurtz and Love 2020 ; Basso et al. 2021 ; Wybo and Leib 2025 . This enables a plug-and-play use of QAOA without instance-specific tuning. Crucially, for fixed QAOA depth p and fixed degree d , each greedy update requires the evaluation of a constant number of local expectation values and a constant amount of classical post-processing. As a result, the total run time of the quantum-enhanced greedy algorithm scales as O(N) with N the number of nodes of the problem graph. To benchmark the method beyond current hardware capabilities, we compute the required QAOA expectation values using tensor-network contractions, allowing us to study the shallow-depth regime ( p\leq 4 ) and elucidate the exponential cost in p induced by light-cone growth. In numerical simulations on random 3 -regular graphs, the quantum-enhanced greedy algorithm consistently outperforms the classical greedy baseline. We observe the same behavior experimentally by implementing the algorithm at depths p=2,3 on the IQM Garnet quantum processor Abdurakhimov et al. 2024 . Finally, we compare the hybrid approach to the linear-time prioritized search algorithm of Marino et al. Marino and Kirkpatrick 2020 and find improved performance up to N\approx 5000 nodes for p=4 . This is significant because Marino’s algorithm is a recent linear-time prioritized search algorithm specifically tailored to random regular graphs, yet our approach already outperforms it using only shallow circuits to estimate local expectation values. By using QAOA expectation values to guide a classical greedy search, our approach partially mitigates current hardware limitations that preclude the much deeper circuits required by a standalone quantum algorithm. Therefore, our results suggest that classical optimization can benefit substantially from incorporating quantum components even in the near term. The present work illustrates

Read the complete text