Technical Summary: A Scalable Quantum-Enhanced Greedy Algorithm for Maximum Independent Set Problems

Problem Statement

The paper addresses the Maximum Independent Set (MIS) problem, a fundamental NP-hard combinatorial optimization task in graph theory. Given a graph $G=(V, E)$, the goal is to find the largest subset of vertices $I \subseteq V$ such that no two vertices in $I$ are adjacent. While classical greedy algorithms offer linear-time scalability, they often fail to capture intricate global structures, leading to suboptimal solutions. Conversely, standalone quantum algorithms like the Quantum Approximate Optimization Algorithm (QAOA) face significant challenges in the Noisy Intermediate-Scale Quantum (NISQ) era: they require deep circuits to achieve optimality (which current hardware cannot support due to noise) and suffer from the "barren plateau" problem during variational parameter optimization. Furthermore, theoretical results suggest that constant-depth QAOA cannot solve MIS to near-optimality due to locality constraints.

Methodology

The authors propose a hybrid quantum-classical algorithm that integrates QAOA as a subroutine within a classical greedy framework. The core methodology involves the following components:

1. Fixed-Angle QAOA: Instead of performing instance-specific variational parameter optimization (which is computationally expensive and prone to barren plateaus), the algorithm utilizes pre-computed QAOA angles. These angles are derived from depth-$p$ QAOA circuits on regular trees (Bethe lattices), which serve as accurate approximations for the local neighborhoods of large $d$-regular graphs.
2. Quantum-Enhanced Greedy Selection:
   • The algorithm iteratively builds an independent set.
   • At each step, rather than selecting a node based solely on its degree (as in classical minimal-degree greedy), the algorithm selects the node $i$ that maximizes the local expectation value $\langle Z_i \rangle_p$ derived from a QAOA state $|\gamma^*, \beta^*\rangle$.
   • This expectation value is estimated by executing a shallow QAOA circuit restricted to the light-cone subgraph (the neighborhood of radius $p$) of the candidate node.
   • The selected node is added to the independent set, and the node along with its neighbors are removed from the graph.
3. Efficiency Mechanisms:
   • Local Recomputation: Due to the locality of QAOA, removing a node only affects the expectation values of nodes within a distance $p+1$. The algorithm recomputes only these affected values.
   • Caching: Expectation values for isomorphic light-cone subgraphs are cached to avoid redundant calculations.
   • Complexity: For a fixed depth $p$, the cost of computing local expectation values is constant with respect to the graph size $N$. Consequently, the total runtime scales linearly, $O(N)$, matching the complexity of the bare classical greedy algorithm.

Key Contributions

• Elimination of Variational Optimization: The work demonstrates a "plug-and-play" approach where QAOA parameters are fixed based on tree models, removing the need for costly classical optimization loops and making the algorithm scalable.
• Scalable Hybrid Architecture: The authors present a method that maintains shallow quantum circuits (suitable for NISQ devices) while leveraging quantum correlations to guide classical decisions, achieving linear-time complexity.
• Experimental Validation: The algorithm was implemented on a 20-qubit IQM superconducting quantum processor (Garnet). The study successfully found independent sets in graphs with thousands of nodes, validating the approach on real hardware.
• Tensor Network Benchmarking: To evaluate performance beyond current hardware limits, the authors employed tensor network simulations (using the QUIMB package) to compute exact expectation values for depths up to $p=4$ and graph sizes up to $N=5000$.

Results

• Performance vs. Classical Baselines:
  • On random 3-regular graphs, the quantum-enhanced greedy algorithm significantly outperforms the standard minimal-degree greedy baseline.
  • At depth $p=4$, the hybrid method achieves a statistically significant improvement over the State-Of-The-Art (SOTA) linear-time prioritized search algorithm (Marino et al.) for graph sizes up to $N \approx 5000$.
  • Even at low depths ($p=2, 3$), the quantum-enhanced method yields better independence ratios than purely classical approaches.
• Hardware Implementation:
  • Experiments on the IQM Garnet device at $p=2$ and $p=3$ confirmed that expectation values extracted from noisy hardware can effectively guide the greedy selection.
  • The algorithm demonstrated robustness to noise; while noise degrades the precision of the "advice" provided by the quantum processor, it does not cause the algorithm to produce invalid independent sets.
• Scaling and Limits:
  • Tensor network simulations revealed that the classical cost of computing expectation values scales exponentially with depth $p$ (specifically $O(\exp(O(p)))$ for tree-like structures), whereas the quantum hardware cost scales polynomially with $p$ (assuming all-to-all connectivity) or as $O(\exp(p)^{1/2})$ on planar hardware. This suggests a regime where quantum processors become essential for evaluating these local quantities efficiently.

Significance and Claims

The paper posits that this work illustrates a practical path for NISQ-era quantum utility. By reframing QAOA not as a standalone solver but as a subroutine that enhances classical heuristics, the authors overcome the limitations of shallow circuits and the difficulty of parameter optimization.

Key claims regarding significance include:

1. Modest Quantum Resources, Significant Gains: The integration of modest quantum resources (shallow circuits, fixed angles) into classical strategies can yield outcomes superior to either method alone.
2. Scalability: The linear-time scaling makes the approach viable for large-scale problems (thousands of nodes) on current and near-future hardware.
3. Robustness: The hybrid nature provides intrinsic robustness; noise affects the quality of the heuristic guidance but preserves the validity of the solution (the independent set constraint).
4. Generalizability: The authors suggest this non-variational, quantum-enhanced paradigm is naturally extensible to other sparse-graph combinatorial optimization problems (e.g., MaxCut, Minimum Vertex Cover) where local structure is dominant.

The authors conclude that while standalone QAOA struggles to outperform simple greedy heuristics at low depths, the quantum-enhanced greedy algorithm successfully leverages quantum correlations to break ties and navigate the solution space more effectively, offering a compelling candidate for scalable hybrid optimization.