Quantum Variational Approaches to the Maximum Independent Set Problem at Utility Scale
Kalyan Dasgupta, Sumanta Mukherjee, Dhriti Verma, Surya Shravan Kumar Sajja, Abhishek Singh, Dzung Phan, Jayant Kalagnanam · 2026
Read Quantum Variational Approaches to the Maximum Independent Set Problem at Utility Scale by Kalyan Dasgupta, Sumanta Mukherjee, Dhriti Verma, Surya Shravan Kumar Sajja, Abhishek Singh, Dzung Phan, Jayant Kalagnanam (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-2606-28866.txt.
Introduction
Dasgupta, Mukherjee, Verma, Sajja, Singh, Phan and Kalagnanam test variational quantum algorithms on the Maximum Independent Set problem, choosing the largest set of graph nodes with no edges between them. They ran two algorithms, VQE and QAOA, on benchmark graphs with 64, 99 and 180 vertices, under two classical optimisers and several circuit depths. A preprocessing pipeline reordered each graph using spectral information and thinned connections to cut circuit depth while keeping solution quality.
Classical post-processing, guided by run history, then repaired candidate answers and recovered the exact optimum on every instance. One variant sampled many distinct optima per run on the smaller graphs. The 180-node case needed a new trick: extra qubits prepared a superposition over classically found near-optimal answers, letting the search improve several seeds at once and find the exact optimum. On real IBM hardware, VQE kept about half its simulator performance. QAOA found no valid sets.
Catalog record
| CREATOR | Kalyan Dasgupta, Sumanta Mukherjee, Dhriti Verma, Surya Shravan Kumar Sajja, Abhishek Singh, Dzung Phan, Jayant Kalagnanam |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 128 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.28866