{"id":"arxiv/2606.28866","url":"https://arxiv.org/abs/2606.28866","tags":["quant-ph"],"score":0,"title":"Quantum Variational Approaches to the Maximum Independent Set Problem at Utility Scale","domain":"quant-ph","source":"arxiv","authors":["Kalyan Dasgupta","Sumanta Mukherjee","Dhriti Verma","Surya Shravan Kumar Sajja","Abhishek Singh","Dzung Phan","Jayant Kalagnanam"],"reviews":0,"subject":"quant-ph","summary":"Near-optimal solutions to Maximum Independent Set on dense graphs sit in local optima that greedy correction and maximality extension cannot escape. We encode near-optimal seeds as a uniform quantum superposition on ancilla qubits and evolve them under an excitation-preserving variational ansatz that holds the search inside the feasible Hamming-weight subspace. A preprocessing stage of spectral reordering and distance-based sparsification, together with history-guided post-processing of the sampled bitstrings, takes the method to 200 nodes. The ansatz entangles the seed branches and the bond…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-06-27","reactions":{}}