IBM Research reports successfully finding the exact Maximum Independent Set (MIS) on graphs containing 180 vertices, a new scale for gate-based variational algorithms tackling this notoriously difficult problem. Researchers achieved this milestone by employing the Variational Quantum Eigensolver (VQE) with a novel approach utilizing ancilla-assisted superposition initialization, enabling a quantum-parallel search over multiple starting points after other methods had been tried. This technique allowed the team to discover the optimal solution for the 180-node instance, where standard approaches previously stalled at a solution size of 14, while the true MIS is 15. The study demonstrates that VQE with CVaR optimization can recover up to 10 distinct MIS per run on a 99-node instance, indicating the algorithm explores multiple optimal solutions.
Maximum Independent Set Problem and Applications
Gate-based quantum algorithms have optimally solved the Maximum Independent Set (MIS) problem on a graph of 180 vertices, a scale previously inaccessible to this approach and signaling progress toward quantum problem solving. Researchers at IBM Research detailed a hybrid quantum-classical approach that combines careful circuit preprocessing with a variational quantum eigensolver (VQE) and, crucially, a novel method for leveraging quantum superposition. The team, comprised of scientists from both IBM Research Bangalore and Yorktown Heights, tackled the computationally intensive MIS problem, finding the largest set of unconnected vertices within a graph, using benchmark graphs of 64, 99, and 180 vertices. A key innovation involved spectral graph reordering, utilizing the Fiedler vector, which consistently outperforms BFS-based and Reverse Cuthill-McKee alternatives on dense instances by minimizing circuit complexity. Distance-based sparsification was applied specifically to QAOA circuits, reducing the computational burden on the quantum circuit.
Recognizing that optimal solutions often reside within an exponentially small region of the solution space, the team introduced ancilla-assisted superposition initialization. This allowed for quantum-parallel variational search over multiple seeds simultaneously, discovering the exact MIS where single-seed methods fail. Remarkably, the algorithm doesn’t simply find a solution; with CVaR optimization, VQE with SPSA recovers up to 10 distinct MIS per run on a 99-node instance, demonstrating an ability to explore the solution space and enumerate multiple optimal configurations. Hardware validation on IBM Quantum hardware showed that VQE recovers approximately half the noiseless MIS diversity at 40% of the shot budget for the 64- and 99-node instances.
Variational Quantum Algorithms for Combinatorial Optimization
Recent advances demonstrate the growing potential of variational quantum algorithms to tackle complex combinatorial problems, specifically the Maximum Independent Set (MIS) problem, with increasingly large graphs. This spectral reordering, utilizing the Fiedler eigenvector, minimizes circuit depth without sacrificing solution fidelity. With CVaR optimization, VQE with SPSA recovers up to 6 distinct MIS per run for the 64-node instance and up to 10 distinct MIS per run for the 99-node instance, sampling broadly from the optimal solution population. Repeated runs further expanded the enumeration of all possible MIS for each instance.
Spectral Reordering for Enhanced Circuit Performance
A key element of their approach centers on optimizing the initial arrangement of data fed into quantum circuits, specifically through a technique called spectral graph reordering. This preprocessing step, utilizing the Fiedler eigenvector, aims to minimize circuit depth and improve performance, particularly on dense graphs where connections are numerous. Distance-based sparsification was applied specifically to QAOA circuits. The researchers successfully used VQE with SPSA to find the exact MIS for a graph containing 180 vertices, a significant milestone representing the largest scale at which gate-based variational algorithms have solved MIS to optimality. With CVaR optimization, VQE with SPSA recovers up to 6 distinct MIS per run for the 64-node instance and up to 10 distinct MIS per run for the 99-node instance, suggesting a capacity for exploring multiple solution pathways simultaneously and enhancing the reliability and effectiveness of the quantum optimization process.
Distance-Based Sparsification of QAOA Circuits
Beyond optimizing the initial arrangement of qubits, researchers at IBM Research focused on streamlining the quantum circuits themselves through distance-based sparsification, a technique designed to reduce computational load without sacrificing solution quality. This preprocessing step specifically targets QAOA circuits by strategically removing long-range interactions during circuit construction, while still retaining them for energy evaluation, a crucial balance for maintaining fidelity. By minimizing circuit depth, sparsification reduces the demands on limited qubit coherence times and helps to mitigate the phenomenon where gradient signals diminish as system size increases. The researchers demonstrated this by successfully finding the exact MIS on 64- and 99-node instances, leveraging a combination of spectral reordering and sparsification.
CVaR Optimization and Post-Processing for MIS Recovery
While quantum algorithms often aim for a single optimal solution, recent work from IBM Research demonstrates a capacity to explore multiple Maximum Independent Sets (MIS) simultaneously, revealing a more nuanced approach to combinatorial optimization. This isn’t simply about finding a solution, but rather sampling a diverse range of optimal possibilities. For the 180-node instance, where standard approaches stalled at size 14, the researchers introduced ancilla-assisted superposition initialization. The researchers emphasize that this approach is a quantum-parallel variational search, leveraging the strengths of both computational paradigms to efficiently explore the solution landscape.
Enumerating Multiple MIS with VQE and SPSA
This capability is particularly notable given the challenges posed by dense graphs, where the optimal solution represents a vanishingly small portion of the overall search space. Recognizing that optimal solutions often reside within an exponentially small region of the solution space, the team introduced ancilla-assisted superposition. With CVaR optimization, VQE with SPSA recovers up to 6 distinct MIS per run for the 64-node instance and up to 10 distinct MIS per run for the 99-node instance, sampling broadly from the optimal solution population. Repeated runs with different SPSA trajectories collectively enumerate a larger fraction of all MIS for each instance. Researchers achieved this milestone by employing the Variational Quantum Eigensolver (VQE) with a novel approach utilizing ancilla-assisted superposition initialization, enabling a quantum-parallel search over multiple starting points after other methods had been tried on the 180-node instance.
This innovative method employs an excitation-preserving circuit design that maintains a fixed Hamming weight throughout the computation. This preprocessing step, alongside distance-based sparsification, reduced the computational burden on the QAOA circuit. Hardware validation on IBM Quantum hardware showed that VQE recovers approximately half the noiseless MIS diversity at 40% of the shot budget for both the 64- and 99-node instances, while QAOA, despite being tested under simulator-constrained configurations, recovers zero valid independent sets on hardware.
Ancilla-Assisted Superposition for 180-Node Instances
While previous attempts using Variational Quantum Eigensolver (VQE) and Quantum Approximate Optimization Algorithm (QAOA) struggled with instances exceeding 64 vertices, researchers have now achieved optimality on a 180-node graph, a scale previously inaccessible to gate-based variational methods. For the 180-node instance, where standard approaches stall at size 14, and the true MIS is 15, researchers employed the Variational Quantum Eigensolver (VQE) with ancilla-assisted superposition initialization, enabling a quantum-parallel search over multiple starting points where single-seed methods fail. This innovative method employs an excitation-preserving circuit design.
Excitation-Preserving Ansatz and Hamming Weight Conservation
Their recent work details a novel approach to address limitations encountered when applying variational quantum algorithms to dense graphs with 180 vertices, a scale previously difficult to achieve with gate-based methods. The team discovered that standard techniques plateaued, consistently returning solutions of size 14 when the true MIS was 15. This innovative method employs an excitation-preserving circuit design that maintains a fixed Hamming weight, eliminating the need for penalty terms to enforce the cardinality constraint and preserving the fine-grained energy differences that distinguish size-14 from size-15 solutions. This allows the algorithm to explore multiple potential solutions simultaneously.
Validation on actual quantum hardware, specifically the ‘ibm_marrakesh’ processor, confirms the transferability of parameters optimized in simulation to noisy quantum execution, a crucial step toward practical utility. However, QAOA, under the simulator-constrained configurations accessible for parameter transfer, recovers zero valid independent sets on hardware, reflecting the combined effect of limited circuit bandwidth, shallow classical optimization, and hardware noise. This technique allows for a hybrid quantum-classical parallel search, enabling the exploration of multiple near-optimal solutions simultaneously.
Source: https://arxiv.org/abs/2606.28866
