{"id":"arxiv/2601.21923","url":"https://arxiv.org/abs/2601.21923","tags":["quant-ph"],"score":0,"title":"A scalable quantum-enhanced greedy algorithm for maximum independent set problems","domain":"quant-ph","source":"arxiv","authors":["Elisabeth Wybo","Jami Rönkkö","Olli Hirviniemi","Jernej Rudi Finžgar","Martin Leib"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-01-29","reactions":{}}