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

CREATORKalyan Dasgupta, Sumanta Mukherjee, Dhriti Verma, Surya Shravan Kumar Sajja, Abhishek Singh, Dzung Phan, Jayant Kalagnanam
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE128 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.28866

Browse the full library · About the Tower of Babel