Quantum Variational Approaches to the Maximum Independent Set Problem at Utility Scale
Abstract
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 dimension of the simulated state grows with circuit depth, which places deeper circuits outside the reach of exact matrix product state simulation at the bond dimensions available to us. Larger instances therefore need quantum hardware. Measured on the data register alone, the superposition behaves as a classical mixture over the seeds, so coherence between the branches has to be created and then looked for. We do this with a CRZ phase layer and post-selection on the ancilla qubits, which brings the branches into interference and exposes the cross terms. The idea is to see if interference between near-optimal seeds widens the range of independent sets the circuit returns. Standard VQE with this pipeline recovers the certified optimum for instances up to 125 nodes, and these run on ibm_marrakesh with parameters transferred from noiseless simulation. The ancilla construction is introduced for the sizes past that point. On a 180-node hard instance the superposition recovers the certified MIS. Five 200-node instances are solved to the certified optimum, and on the 400-node brock400-1 benchmark the method reaches size 25 against a certified optimum of 27. These are the largest hard general-graph instances we know of where a gate-based variational algorithm optimises the full circuit directly.
Related
- Benchmarking Ansatze for Pauli Correlation Encoding in the Maximum Independent Set Problem
- Scalable quantum-enhanced greedy algorithm for the maximum independent set problems on random regular graphs
- Quantum Variational Approaches to Plasma Equilibrium: Cost Function Design for the Grad-Shafranov Equation
- Designing Quantum Solutions to the Closest String Problem with the Non-Variational QWOA
- Exact cost of the Euclidean Maximum Traveling Salesman Problem in one dimension
BibTeX
@misc{dasgupta2026quantum,
title = {{Quantum Variational Approaches to the Maximum Independent Set Problem at Utility Scale}},
author = {Kalyan Dasgupta and Sumanta Mukherjee and Dhriti Verma and Surya Shravan Kumar Sajja and Abhishek Singh and Dzung Phan and Jayant Kalagnanam},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2606.28866},
eprint = {2606.28866},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.28866},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Quantum Variational Approaches to the Maximum Independent Set Problem at Utility Scale
AU - Kalyan Dasgupta
AU - Sumanta Mukherjee
AU - Dhriti Verma
AU - Surya Shravan Kumar Sajja
AU - Abhishek Singh
AU - Dzung Phan
AU - Jayant Kalagnanam
PY - 2026
DA - 2026/09/22
PB - arXiv
DO - 10.48550/arxiv.2606.28866
UR - https://arxiv.org/abs/2606.28866
AB - 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 dimension of the simulated state grows with circuit depth, which places deeper circuits outside the reach of exact matrix product state simulation at the bond dimensions available to us. Larger instances therefore need quantum hardware. Measured on the data register alone, the superposition behaves as a classical mixture over the seeds, so coherence between the branches has to be created and then looked for. We do this with a CRZ phase layer and post-selection on the ancilla qubits, which brings the branches into interference and exposes the cross terms. The idea is to see if interference between near-optimal seeds widens the range of independent sets the circuit returns. Standard VQE with this pipeline recovers the certified optimum for instances up to 125 nodes, and these run on ibm_marrakesh with parameters transferred from noiseless simulation. The ancilla construction is introduced for the sizes past that point. On a 180-node hard instance the superposition recovers the certified MIS. Five 200-node instances are solved to the certified optimum, and on the 400-node brock400-1 benchmark the method reaches size 25 against a certified optimum of 27. These are the largest hard general-graph instances we know of where a gate-based variational algorithm optimises the full circuit directly.
ER -