💻 computer science

Quantum Superposition over Near Optimal Seeds for Maximum Independent Set on Dense Graphs

This paper presents a quantum variational algorithm that leverages uniform superpositions of near-optimal seeds and interference-based post-selection to solve Maximum Independent Set problems on dense graphs up to 400 nodes, significantly outperforming standard VQE and classical heuristics on hard instances where previous methods stall.

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

Published 2026-09-23

📖 7 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 (https://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

In the world of computer science, there is a class of problems known as combinatorial optimization, where the goal is to find the best possible arrangement from a vast number of options. One of the most famous of these is the Maximum Independent Set problem. Imagine a group of people at a party, where some know each other and others do not. The challenge is to invite the largest possible number of guests to a private room such that no two people in the room know one another. If two people know each other, they cannot both be invited. While this sounds simple for a small group, the number of possible combinations grows so explosively fast that even the most powerful supercomputers struggle to find the absolute best answer when the group reaches a few hundred people. This difficulty makes the problem a standard test for new computing technologies, particularly quantum computers, which use the strange rules of quantum mechanics to explore many possibilities at once.

A team of researchers at IBM Research has developed a new method to tackle this problem on dense graphs, where almost everyone knows almost everyone else. In these crowded scenarios, traditional search methods often get stuck in a local trap, finding a good solution but missing the perfect one because the path to the best answer requires a series of coordinated changes that seem impossible to make one by one. The researchers found that by using a quantum computer to hold several "near-perfect" solutions in a state of superposition—a condition where the computer considers multiple options simultaneously—they could break through these traps. Their work, tested on graphs with up to 400 nodes, demonstrates that this approach can find the largest possible groups of non-adjacent vertices, solving instances that stumped standard methods. Crucially, they showed that this success relies on the quantum computer's ability to explore the landscape of solutions in parallel, rather than just improving a single starting point.

The researchers began by acknowledging a specific weakness in how quantum computers usually approach these problems. Standard methods often start with a blank slate, asking the quantum machine to search the entire universe of possibilities from scratch. For dense graphs, the correct answer is so rare that it is like finding a single specific grain of sand on a beach; starting with a blank slate means the computer has almost no chance of ever stumbling upon it. Instead, the team decided to start with a head start. They used classical computers to find several high-quality, though not perfect, solutions. These were the "seeds" of their search. They then encoded these seeds into the quantum computer, not one by one, but all at once, creating a uniform superposition. In this state, the quantum computer was effectively holding all these near-optimal solutions in its mind simultaneously, treating them as a single, complex starting point.

To ensure the search stayed on track, the team used a special type of quantum circuit designed to preserve the "excitation" count. In the language of the problem, this meant the circuit was strictly forbidden from changing the total number of people invited to the room. If the seeds started with 14 people, the quantum evolution could only shuffle those 14 people around, swapping one guest for another, but it could never accidentally invite a 15th person or drop one down to 13. This constraint was vital. It kept the search focused on the most promising area of the solution space, preventing the computer from wasting time exploring impossible or clearly inferior configurations. By keeping the number of invited guests fixed, the circuit could make fine-grained distinctions between different groups of 14, looking for the specific arrangement that was closest to the perfect answer.

The team tested this pipeline on several difficult graphs, including a challenging 180-node instance where the perfect solution involved 15 people. When they tried to solve this using a single seed, the system consistently got stuck at 14 people, unable to find the path to the 15th. However, when they used the superposition of four different 14-person seeds, the system broke through. The quantum computer, by evolving all four seeds together under the same set of rules, found a configuration that none of the individual seeds could reach on their own. The final step involved a classical computer taking the quantum output and performing a quick, smart check to see if the group could be expanded to 15. This hybrid approach successfully recovered the certified maximum of 15 people, a result that neither the classical post-processing nor the standard quantum method could achieve alone.

To understand why this worked, the researchers performed a series of checks to rule out other explanations. They tested whether the classical post-processing alone could have found the answer if given just one seed, but it failed every time. They also tested whether the quantum circuit structure itself was the magic ingredient by running it on single seeds, but again, it got stuck. The only way to escape the local trap was to have the quantum computer optimize over all the seeds at the same time. This confirmed that the power came from the parallel search: the quantum computer found a set of parameters that improved all four starting points simultaneously, effectively navigating a path that was invisible to any single starting point.

The researchers also explored whether the different branches of the superposition could interfere with each other to amplify the best answers, a phenomenon where quantum waves combine to make a signal stronger. They added a specific layer of operations designed to create this interference and then measured the results. While they could detect the presence of these quantum cross-terms, the effect was small in their current simulations. The researchers noted that for this interference to be more powerful, the different solutions would need to be very similar in their structure, or the quantum circuit would need to be much deeper. They found that the depth of the circuit they could simulate was limited by the complexity of the entanglement, suggesting that future hardware with more qubits and better stability would be needed to fully harness this interference effect.

The team validated their findings on real quantum hardware for smaller graphs, running their algorithms on an IBM processor with 156 qubits. Even with the noise and errors inherent in current machines, the method successfully recovered the optimal solutions for graphs with 64, 99, and 125 nodes. This proved that the pipeline is robust enough to work on real devices, not just in perfect simulations. For the larger graphs, such as a 400-node instance, the team relied on high-fidelity simulations because the problem size exceeded the capacity of current quantum hardware. In these simulations, they found that increasing the depth of the quantum circuit allowed them to find larger independent sets, reaching a size of 25 on a graph where the perfect answer is 27. This suggests that as quantum computers grow more powerful, this method will continue to scale.

The work highlights a shift in how quantum algorithms might be designed for hard problems. Instead of trying to find the answer from scratch, the most effective strategy may be to use classical computers to find good starting points and then use quantum computers to explore the space between them. The researchers showed that by combining the strengths of both—classical heuristics for finding seeds and quantum superposition for exploring the connections between them—they could solve problems that were previously out of reach. While they did not claim to have solved the Maximum Independent Set problem for all possible graphs, they demonstrated a clear and reproducible path to solving the hardest instances of dense graphs, providing a blueprint for how future quantum computers might tackle complex combinatorial challenges.

Technical Summary: Quantum Superposition over Near-Optimal Seeds for Maximum Independent Set on Dense Graphs

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 approaches face specific challenges in the Noisy Intermediate-Scale Quantum (NISQ) era.

A critical structural challenge arises in dense graphs where the optimal independent set is a small fraction of the total vertices (e.g., size 15 out of 180). In such cases, the optimal solution occupies an exponentially small region of the Hilbert space. Standard variational algorithms initialized in uniform superposition or a single classical seed often converge to local optima (e.g., size 14) from which greedy correction and maximality extension cannot escape, even with repeated restarts. The energy landscape presents barriers that require coordinated multi-qubit changes to traverse, which local perturbations cannot achieve.

Methodology

The authors propose a layered framework combining graph preprocessing, variational optimization, and classical post-processing. The pipeline is designed to handle instances up to 400 nodes, with specific techniques introduced for sizes exceeding current hardware capabilities.

1. Preprocessing: Reordering and Sparsification

Spectral Reordering: Vertices are reordered using the Fiedler vector of the graph Laplacian. This places structurally adjacent vertices at nearby qubit indices, minimizing the index distance $|\pi(i) - \pi(j)|$ for coupled pairs. This reduces the need for SWAP gates and aligns the problem's coupling structure with the hardware's connectivity.
Distance-Based Sparsification: For QAOA, long-range edges are dropped from the circuit's cost unitary based on a bandwidth parameter $k$ , while the full Hamiltonian is retained for energy evaluation. This keeps circuit depth tractable (specifically for MPS simulation) while ensuring the optimizer receives accurate energy feedback.

2. Variational Algorithms

Standard VQE: For instances up to 125 nodes, the authors use the Variational Quantum Eigensolver (VQE) with an EfficientSU2 ansatz. The optimization employs the SPSA (Simultaneous Perturbation Stochastic Approximation) optimizer and a Conditional Value at Risk (CVaR) objective to focus on the tail of the measurement distribution, enhancing solution diversity.
Excitation-Preserving Ansatz: For larger, denser instances (180+ nodes), the authors introduce an ansatz built on $fSim(\theta, \phi)$ gates. This gate preserves the total Hamming weight (number of excitations) of the state. By constraining the search to a fixed Hamming-weight subspace, the algorithm avoids the need for large penalty terms to enforce feasibility, allowing for finer energy distinctions between near-optimal configurations.

3. Ancilla Superposition and Interference

To overcome local optima barriers (specifically on the 180-node instance where standard methods stall at size 14), the authors introduce a novel initialization and evolution strategy:

Ancilla Superposition: Instead of initializing from a single seed or the zero state, the algorithm prepares a uniform quantum superposition of multiple classically-found near-optimal seeds (e.g., four size-14 independent sets) using ancilla qubits as an index register. The state is $|\Psi_0\rangle = \frac{1}{\sqrt{m}} \sum |s(j)\rangle |j\rangle_{anc}$ .
Parallel Optimization: The excitation-preserving ansatz evolves all seed branches simultaneously under shared variational parameters. This allows the optimizer to find parameters that improve the collective energy across all seeds, accessing regions of the solution space unreachable by single-seed optimization.
Ancilla Interference: A controlled-RZ (CRZ) phase layer followed by Hadamard gates on the ancilla and post-selection on the $|0\rangle^{\otimes a}$ state is used to create interference between seed branches. This retains cross-term contributions ( $Re[A_k A^*_{k'}]$ ) that are discarded in a classical stochastic mixture. The authors measure these terms to determine if interference amplifies configurations supported by multiple seeds.

4. Classical Post-Processing

A two-stage bitstring heuristic pipeline converts raw quantum outputs into valid independent sets:

History-Guided Suppression: An Exponential Moving Average (EMA) tracks the frequency of qubits being 0 or 1 in high-quality samples, creating suppression masks to remove over-selected vertices and add under-selected ones.
Greedy Correction and Extension: A two-pass greedy algorithm repairs independence violations and then extends the set to maximality using a minimum-degree selection rule. This step typically recovers 2–3 additional vertices over raw quantum outputs.

Key Results

Performance on Benchmarks

64, 99, and 125 Nodes: Standard VQE with the proposed pipeline recovers the certified Maximum Independent Set (MIS) for all these instances. The 125-node instance ( $c125-9$ ) was successfully executed on IBM's $ibm\_marrakesh$ hardware (156 qubits) using parameter transfer from noiseless simulations, recovering 4 distinct MIS of size 34.
180 Nodes: Standard VQE and bitstring heuristics consistently stall at size 14. The ancilla superposition technique breaks this barrier, recovering the certified MIS of size 15. Ablation studies confirm that neither the bitstring heuristic alone nor the excitation-preserving circuit initialized from a single seed can escape the size-14 local optimum; the parallel search over multiple seeds is essential.
200 Nodes: The pipeline solves five instances from the QOBLIB suite (including $brock200$ and $c-fat200$) to optimality in simulation.
400 Nodes ($brock400-1$): The certified MIS is 27. Standard VQE reaches size 23–24. The excitation-preserving ansatz with ancilla superposition reaches size 25 (92.6% of optimum) with $p=3$ layers. The authors note that reaching size 26 or 27 likely requires deeper circuits ( $p \ge 4$ ) that exceed current classical MPS simulation limits due to bond dimension growth ( $\chi_{max} \le m \cdot 2^p$ ).

Hardware Validation

Experiments on $ibm\_marrakesh$ demonstrated that the pipeline is robust to noise. Parameters optimized in noiseless simulation transferred directly to hardware recovered 3 distinct MIS for the 64-node instance and 5 for the 99-node instance, retaining approximately 50% of the noiseless solution diversity despite using only 40% of the shot budget.
QAOA configurations on hardware failed to recover any valid independent sets, attributed to the compounding effects of shallow classical optimization and decoherence in deep circuits.

Interference Analysis

The authors measured the cross-terms in the 180-node instance and found them to be small. The interference mechanism did not significantly alter the solution quality compared to the stochastic mixture baseline in the simulated regime.
The paper attributes this to the geometric distance between distinguishing vertices of near-optimal solutions on the reordered qubit chain. The branches of the superposition rarely overlap on the same bitstrings at the depths simulated. The authors posit that deeper circuits (requiring hardware) would increase the "reach" of excitation transport, potentially enabling measurable interference.

Significance and Claims

The paper makes the following modest but significant claims:

Breaking Local Optima: The primary contribution is a technique to break local optima barriers in dense MIS problems by encoding multiple near-optimal seeds into a quantum superposition and optimizing them collectively. This is demonstrated by solving the 180-node instance where all other methods in the pipeline failed.
Scalability: The framework represents the largest gate-based variational algorithm application to hard general-graph MIS instances where the full circuit is optimized directly, reaching 200 nodes in simulation and 400 nodes with partial progress.
Hardware Readiness: The pipeline is validated on real quantum hardware for instances up to 125 nodes, confirming that the approach is robust to current noise levels without requiring hardware-aware re-optimization.
No Quantum Advantage Claim: The authors explicitly state they do not claim quantum computational advantage for the simulated instances, as they are efficiently simulable via Matrix Product States (MPS) due to low entanglement (shallow depth, small seed count). The value lies in demonstrating a principled mechanism (parallel seed optimization) that works and identifying the regime (deeper circuits, larger bond dimensions) where hardware execution becomes necessary.
Interference as a Future Mechanism: While interference was not measured as a significant factor in the current simulations, the paper posits it as a mechanism that could be exploited on future hardware with deeper circuits, provided the graph structure allows seed branches to overlap.

The work concludes that for dense graphs where solutions are sparse, the combination of spectral reordering, excitation-preserving ansätze, and multi-seed superposition offers a viable path forward, with the ultimate bottleneck shifting from algorithmic design to the availability of deeper, noise-resilient quantum hardware.