⚛️ quantum physics

Quantum Variational Approaches to the Maximum Independent Set Problem at Utility Scale

This paper demonstrates that variational quantum algorithms, enhanced by spectral preprocessing, classical post-processing, and a novel ancilla-assisted superposition initialization, can solve the Maximum Independent Set problem to optimality on benchmark graphs with up to 180 vertices, representing the largest scale of gate-based variational success for this problem to date.

Original authors: Kalyan Dasgupta, Sumanta Mukherjee, Dhriti Verma, Surya Shravan Kumar Sajja, Abhishek Singh, Dzung Phan, Jayant Kalagnanam

Published 2026-06-30

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Kalyan Dasgupta, Sumanta Mukherjee, Dhriti Verma, Surya Shravan Kumar Sajja, Abhishek Singh, Dzung Phan, Jayant Kalagnanam

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Finding the Best Group of Strangers

Imagine you are hosting a party and you have a list of 180 guests. However, some of these guests hate each other and cannot be in the same room together. Your goal is to invite the largest possible group of people who all get along (no enemies in the room). In math, this is called the Maximum Independent Set problem.

This is a notoriously difficult puzzle. As the number of guests grows, the number of possible combinations explodes, making it nearly impossible for even the fastest supercomputers to find the absolute best group without checking every single possibility.

This paper describes how researchers used a new type of computer—a Quantum Computer—to solve this puzzle for groups of 64, 99, and even 180 people. They didn't just find a good group; they found the perfect group for all three sizes.

The Tools: Two Different Ways to Search

The researchers tried two main quantum strategies, which we can think of as two different ways to search a dark maze:

QAOA (The "Flashlight" Approach): This method starts with a uniform search, shining a light everywhere at once. The paper found that on real hardware, this flashlight was too dim and the maze too complex. It got stuck and found almost no valid groups.
VQE (The "Scout" Approach): This method uses a flexible, adjustable map. It starts with a guess and slowly tweaks the map to find lower energy (better) solutions. This approach worked much better, finding hundreds of different valid groups in a single run.

The Problem: Getting Stuck at "Good Enough"

For the 180-person party, the researchers hit a wall. Their best quantum "scouts" kept finding groups of 14 people who got along. But they knew the perfect answer was actually 15 people.

Think of it like climbing a mountain. The quantum computer climbed up to a high plateau (14 people) and thought, "This is the top!" It couldn't see the tiny peak just a few feet away (15 people) because the path to get there required a very specific, coordinated move that the computer wasn't making. Classical computers (standard algorithms) also got stuck on this same plateau.

The Breakthrough: The "Group Huddle" Trick

To solve the 180-person problem, the researchers invented a clever new trick called Ancilla Superposition.

Imagine you have four different maps, each showing a slightly different route to a high plateau (the 14-person groups).

Old Way: You pick one map, follow it, and hope it leads to the top. If it doesn't, you are stuck.
New Way (The Paper's Innovation): You take all four maps and superimpose them. You create a "quantum huddle" where the computer explores all four routes simultaneously in a single run.

By using extra "helper" qubits (ancilla) to hold these different starting points, the quantum computer could search all four paths at once. It found a hidden connection between these paths that led to the extra person needed to reach the perfect group of 15.

The Key Insight: The paper proves that this wasn't just the classical "post-processing" (the cleanup crew) doing the work. If they tried to fix the 14-person groups using only classical math, they failed. It was the quantum parallel search—looking at all the starting points at the same time—that broke the barrier.

The Results: From Simulation to Real Hardware

The researchers tested this on a real quantum computer (IBM's ibm_marrakesh).

The Good News: For the smaller parties (64 and 99 people), the quantum computer successfully found the perfect groups, even with the noise and errors of real hardware. It recovered about half the variety of solutions found in the perfect simulation.
The Bad News: For the "Flashlight" approach (QAOA), the real hardware was too noisy. The circuits were too deep, and the errors drowned out the signal, resulting in zero valid groups found.
The Reality Check: The actual time the quantum chip spent working was tiny (about 8 seconds). The rest of the time was spent waiting in line and doing the heavy lifting on a classical computer to prepare and clean up the data.

The Takeaway

This paper doesn't claim that quantum computers are now faster than supercomputers for this specific task (in fact, the simulation took longer than a standard computer). Instead, it claims a methodological victory:

They built a complete pipeline that solves a hard math problem perfectly for up to 180 variables.
They proved that combining multiple "good enough" guesses into a quantum superposition allows the computer to escape local traps that trap both classical computers and standard quantum methods.
They showed that this "quantum parallel search" works even on today's noisy hardware, provided the circuit isn't too complex.

In short: They taught the quantum computer how to look at multiple "almost right" answers at the same time to find the one "perfect" answer that was hiding just out of reach.

Technical Summary: Quantum Variational Approaches to the Maximum Independent Set Problem at Utility Scale

Problem Statement

The Maximum Independent Set (MIS) problem seeks the largest subset of vertices in an undirected graph such that no two vertices are adjacent. It is a canonical NP-hard problem with applications in frequency assignment, protein interaction analysis, and VLSI design. While classical exact solvers (branch-and-bound, integer programming) struggle with hard instances beyond a few hundred vertices, quantum computing offers potential heuristics. However, gate-based variational algorithms face significant challenges in the Noisy Intermediate-Scale Quantum (NISQ) era, including limited qubit counts, short coherence times, and the "barren plateau" phenomenon where gradients vanish exponentially.

A specific structural challenge arises for large, dense graphs where the MIS constitutes a tiny fraction of the total vertices (e.g., 15 out of 180). In such cases, the optimal solution occupies an exponentially small region of the Hilbert space. Standard approaches initializing with uniform superposition assign negligible amplitude to the MIS, often causing variational circuits to converge to suboptimal energy basins from which escape is difficult without coordinated multi-qubit changes.

Methodology

The authors propose a layered framework combining circuit preprocessing, variational optimization, and classical post-processing to address these challenges across three benchmark instances: 64, 99, and 180 nodes.

1. Preprocessing and Circuit Construction

Vertex Reordering: To minimize SWAP overhead and improve entanglement efficiency, the authors compare three reordering strategies: Coupling-weighted BFS, Reverse Cuthill-McKee (RCM), and Spectral Reordering (using the Fiedler vector). Spectral reordering is adopted as it consistently outperforms others on dense instances by grouping structurally proximate vertices, thereby minimizing the index distance between strongly coupled qubits.
Distance-Based Sparsification: Applied specifically to QAOA circuits, this technique removes long-range interactions from the circuit construction (retaining only edges where $|i-j| \le k$ ) while evaluating the energy using the full Hamiltonian. This reduces circuit depth significantly, making simulations tractable on Matrix Product State (MPS) simulators.
Algorithms: The study compares the Variational Quantum Eigensolver (VQE) using an EfficientSU2 ansatz and the Quantum Approximate Optimization Algorithm (QAOA). Optimizers include COBYLA and Simultaneous Perturbation Stochastic Approximation (SPSA). The Conditional Value at Risk (CVaR) objective is used to focus optimization on the lowest-energy tail of the measurement distribution.

2. Classical Post-Processing Pipeline

A two-stage bitstring heuristic pipeline converts raw quantum measurements into valid MIS candidates:

History-Guided Suppression: An Exponential Moving Average (EMA) tracks the frequency of qubits being in the $|0\rangle$ state across top-performing bitstrings. This generates suppression masks to remove over-selected vertices (violating independence) and add under-selected vertices.
Greedy Correction & Maximality Extension: A two-pass greedy algorithm first repairs infeasible sets by removing high-weight violations, then extends the set to maximality by adding compatible vertices in ascending order of degree.

3. Ancilla-Assisted Superposition Initialization (180-Node Instance)

For the 180-node instance, standard VQE stalls at size 14 (the known MIS is 15). To overcome this, the authors introduce a novel initialization technique:

Seed Selection: Classical post-processing identifies multiple diverse, near-optimal size-14 independent sets.
Ancilla Superposition: Instead of initializing from a single seed or uniform superposition, the circuit prepares a uniform quantum superposition of these $m$ distinct size-14 solutions using ancilla qubits as an index register.
Excitation-Preserving Ansatz: The state evolves under an ansatz composed of fermionic simulation (fSim) gates that conserve the total Hamming weight (number of excitations). This restricts the search to the subspace of size-14 configurations, eliminating the need for penalty terms and sharpening the energy landscape for fine-grained optimization.
Quantum-Parallel Search: The variational parameters are optimized collectively across all seed branches simultaneously. The resulting distribution is then processed by the classical heuristic, which can extend size-14 sets to the size-15 MIS.

Key Results

Benchmark Instances (64, 99, and 180 Nodes)

64-Node Instance: VQE with SPSA and CVaR successfully recovers all 9 distinct certified MIS (size 10) across repeated runs. QAOA recovers fewer distinct sets (0–5 per run) and fails to reach size 10 with Strategy 2 (driving all recovered sets to maximality), highlighting the importance of solution diversity.
99-Node Instance: VQE recovers up to 10 distinct MIS (size 7) per run, sampling a meaningful fraction of the 56 certified solutions. QAOA is not pursued due to sparsification limits on the MPS simulator.
180-Node Instance: Standard VQE (Phase 1) converges to size 14 but cannot reach size 15. The ancilla-assisted Phase 3 (excitation-preserving VQE) successfully discovers the size-15 MIS. Ablation studies confirm that classical heuristics applied to single seeds, or excitation-preserving circuits initialized from single seeds, fail to find the size-15 MIS. Only the multi-seed quantum superposition breaks the local optimum barrier.

Hardware Validation (IBM Quantum `ibm_marrakesh`)

VQE: Using parameters transferred directly from noiseless simulation (no hardware re-optimization), VQE recovers approximately 50% of the noiseless MIS diversity at 40% of the shot budget. For the 64-node instance, 3 distinct MIS (size 10) were found; for the 99-node instance, 5 distinct MIS (size 7) were found.
QAOA: Under the same parameter transfer protocol, QAOA recovered zero valid independent sets on hardware. The authors attribute this to the compounding effect of limited circuit bandwidth (requiring deep SWAP chains), shallow classical optimization, and hardware noise.

Significance and Claims

The paper claims the following contributions and significance:

Utility-Scale Simulation: To the authors' knowledge, the 180-qubit MPS simulation represents the largest scale at which gate-based variational algorithms have solved the MIS problem to optimality.
Methodological Breakthrough: The primary contribution is the ancilla superposition technique. It provides a principled framework for breaking local optima that trap both classical heuristics and standard variational approaches. By initializing a uniform superposition over multiple near-optimal classical seeds and evolving them under an excitation-preserving ansatz, the method performs a "hybrid quantum-classical parallel search." This allows the discovery of solutions (size 15) that are inaccessible to single-seed methods.
Robustness to Noise: The hardware validation demonstrates that the bitstring heuristic pipeline is robust to realistic noise conditions, recovering significant solution diversity without hardware-aware re-optimization.
Modest Claims on Quantum Advantage: The authors explicitly state that they do not claim quantum computational advantage for these specific instances. The circuits studied are efficiently simulable classically via MPS (bond dimension $\chi_{max} = 2$ ) due to their low entanglement structure. The significance lies in demonstrating that the methodology works and provides a foundation for future hardware implementations where deeper ansätze and larger seed populations may yield genuine quantum advantage.

The work establishes that the discovery of the MIS in the 180-node case is a consequence of quantum-parallel search over multiple near-optimal initializations, rather than the classical post-processing alone. This framework is presented as a scalable approach for combinatorial optimization problems admitting an Ising formulation.