Degree-Guided Adiabatic Quantum Algorithm for MIS with Neutral Atoms

The gist The LD-AQC algorithm, which engineers local controls to preferentially excite atoms with few neighbors, accelerates convergence to the Maximum Independent Set state and suppresses population in trap states, resulting in higher success probabilities than traditional global controls and a 25% reduction in fidelity decay rate as problem hardness increases<ref:2605.16944#pg2>

The Problem and Mapping

Neutral atom arrays are a promising platform for solving graph optimization problems [1–3]<ref:2605.16944#pg2>. Specifically, the maximum independent set (MIS) problem can be mapped onto the preparation of an atom array in a state with maximal number of Rydberg excitations [4]<ref:2605.16944#pg2>. The MIS problem is defined as finding the largest subset of non-adjacent vertices in a graph—this mapping is achieved by preparing an atom array in a state with maximal number of Rydberg excitations<ref:2605.16944#pg2>. To scale up the performance of adiabatic quantum computation (AQC) for larger systems, a challenge arises since the spectral gap typically shrinks upon increasing system size and that limits the time complexity of AQC<ref:2605.16944#pg2>.

The LD-AQC Approach

The approach is based on the observation that vertices of smaller degrees are more likely to belong to the MIS, and vice versa<ref:2605.16944#pg2>. This trend is demonstrated in Fig. 1(a), where a typical graph is shown with local degrees (LDs) labeling the vertices and the MIS colored in red<ref:2605.16944#pg2>. In Fig. 1(b), we generate an ensemble of random graphs and plot the average probability that a vertex belongs to the MIS as a function of its LD, demonstrating a scaling of P(i ∈ MIS) ≈ (1 − MIS/N)di where N is the number of graph nodes, di is the degree of node i, and MIS is the MIS size<ref:2605.16944#pg2>. Guided by this observation, we choose degree-dependent detuning profiles for the control fields that favor excitation of atoms with small LDs<ref:2605.16944#pg2>. Our work is referred to as ”local-degree adiabatic quantum computation” (LD-AQC), and it analyzes its performance on thousands of disordered King’s graphs with a random distribution of holes<ref:2605.16944#pg2>.

Hamiltonian Engineering

The rotating-frame Hamiltonian of the atom array is given by H = X i∈V h omega(t)ˆσ(i) x − ∆i(tˆni + X (i,j)∈E Uijnˆinˆj. The first sum corresponds to RAP pulses, while the second term accounts for Rydbreg interactions<ref:2605.16944#pg2>. While the original AQC from Ref. [4] used global drives with homogeneous detunings, ∆i(t) = ∆0(t) ∀i, we construct degree-dependent local detunings<ref:2605.16944#pg2>. The LD-AQC MIS algorithm considers linear local detuning profiles as shown in Fig. 1(c): ∆i(t) = fi(a) · δ0 · t−tf /2 tf, where δ0 is an energy scale, fi(a) is a monotonic function of the vertex index i, and a is determined by Alg. 0<ref:2605.16944#pg2>. The goal of Alg. 0 is to efficiently construct fi(a) in a manner that accelerates the convergence towards the MIS state while preserving the original ground state<ref:2605.16944#pg2>. This is accomplished by requiring that the energy decreases monotonically with the number of Rydberg excitations, according to the condition in Eq. (5) explained below<ref:2605.16944#pg2>.

Algorithm Design and Complexity

The algorithm chooses a∗ to be smaller than the value at which the energy manifolds start to overlap<ref:2605.16944#pg2>. Satisfying the energy condition, Eq. (5), implies that any state with k − 1 excitations has a higher energy than any state with k excitations<ref:2605.16944#pg2>. Algorithm 0 consists of two steps: First, find a critical k∗ that minimizes the difference function Dk, i.e., Dk∗ (a) ≤ Dk(a) ∀k & a[3]. Secondly, find a critical a∗ for which the minimum vanishes, Dk∗ (a∗) = 0[3]. The overall classical complexity of Alg. 0 is bounded by O(M + N log N), implying a polynomial overhead<ref:2605.16944#pg2>.

Performance and Hardness Parameter

The time complexity of AQC is bounded by the inverse minimal energy gap [10]<ref:2605.16944#pg2>. The minimal gap correlates well with a graph property called the hardness parameter (HP)<ref:2605.16944#pg2>. For the LD-AQC, a generalized hardness parameter HPLD is introduced, defined as HPLD ≡ P j∈MIS-1 wj P j∈MIS-1 wj · cj where wj ≡ 1/Ej − EMIS, (8)<ref:2605.16944#pg2>. Our simulations confirm that this definition efficiently describes the performance<ref:2605.16944#pg2>. The LD-AQC algorithm consistently outperforms the traditional AQC in both metrics<ref:2605.16944#pg2>.

Conclusion and Scaling

The LD-AQC algorithm exhibits superior scaling, with a larger scale-factor (a = 14.5 vs. 13.1) and a smaller exponent (b = −1.24 vs. −1.38) relative to the traditional protocol<ref:2605.16944#pg2>. This 25% reduction in the scaling exponent (btrad) demonstrates that the LD protocol achieves a sublinear speedup compared to the traditional algorithm<ref:2605.16944#pg2>. The performance is expected to improve by optimizing local detuning profiles, e.g., via quantum optimal control [26]<ref:2605.16944#pg2>. The framework presented here also naturally extends to other combinatorial optimization problems, such as MAX-cut [41]<ref:2605.16944#pg2>. The approach is applicable, more generally, to other qubit platforms<ref:2605.16944#pg2>.

How it works

The essence of our algorithm is to raise the average energy of the disconnected IS states, therefore, suppressing their population during the AQC<ref:2605.16944#pg2>. Figure 2(b) shows the energy spectrum of the Hamiltonian at the end of the protocol for a graph from (a)<ref:2605.16944#pg2>. In LD-AQC, local detunings lift this degeneracy, requiring a modification of Eq. (7)<ref:2605.16944#pg2>.

Quantifying the Improvement

The success probability metric SPM ≡ − log(1 − PMIS) exhibits a power-law dependence on the problem hardness [(as defined in Eq. (8)]<ref:2605.16944#pg2>. Specifically, the LD-AQC algorithm exhibits superior scaling, with a larger scale-factor (a = 14.5 vs. 13.1) and a smaller exponent (b = −1.24 vs. −1.38) relative to the traditional protocol<ref:2605.16944#pg2>. A comparison of the SPM values in Fig. 3(c) reveals a sub-linear relationship between the two protocols, SPMLD ∝ (SPMtrad)0.75<ref:2605.16944#pg2>. This 25% reduction in the scaling exponent (btrad) demonstrates that the LD protocol achieves a sublinear speedup compared to the traditional algorithm<ref:2605.16944#pg2>.

Statistical Analysis

The distribution of the logarithmic error ratio, log10[(1 − Ptrad)/(1 − PLD)], is positive across all instances, with a mean value of 0.47, showing that the LD protocol outperforms the traditional approach on all instances<ref:2605.16944#pg2>. A mean value of 0.47 implies a nearly triple reduction in the average error rate<ref:2605.16944#pg2>. The generalized hardness parameter, HPLD, typically yields a smaller hardness parameter than the traditional homogeneous AQC, with an average reduction in effective problem hardness of ∼ 3.5%<ref:2605.16944#pg2>.

1. Bold header: Local-Degree Adiabatic Quantum Computation (LD-AQC) implementation for MIS optimization. This system can solve Maximum Independent Set (MIS) problems on large graphs by engineering local controls that preferentially excite atoms with few neighbors, leading to higher success probabilities than traditional global controls.

2. Bold header: Accelerated convergence through degree-dependent detuning profiles. The AI system will employ a control field defined by the function in Eq. (2), where smaller degrees corresponding to larger slopes, allowing the algorithm to accelerate convergence towards the MIS state while ensuring that the energy decreases monotonically with the number of Rydberg excitations.

3. Bold header: Enhanced robustness against problem hardness through generalized hardness parameter analysis. The improved system will use the generalized hardness parameter, HPLD, which is defined as Pj∈MIS-1 wj Pj∈MIS-1 wj · cj, to accurately quantify algorithmic difficulty and predict performance scaling across different graph ensembles.

4. Bold header: Optimized control pulse design for optimal performance. The system will search for a critical parameter 'a' that satisfies the energy condition, "Dk(a∗) > 0 ∀ k = 1,..., N, ensuring that the ground state of the WMIS problem coincides with that of the MIS."

5. Bold header: Predictive capability based on spectral gap correlation. By utilizing Fig. S1(a), the system can correlate instances with a strong inverse correlation between their minimal spectral gap and HPLD, allowing for an accurate assessment of computational difficulty before running the full annealing protocol.

We present a quantum adiabatic algorithm for solving MIS with Rydberg atoms, which uses graph degrees to engineer the Hamiltonian for adiabatic evolution. Our approach extends the algorithm of Pichler et al. for MIS state preparation, which uses time-dependent global controls to excite atoms while the Rydberg blockade mechanism suppresses adjacent excitations. To accelerate adiabatic evolution, we introduce local light shifts that favor excitation of low-degree nodes and constrain the final Hamiltonian so that energy scales inversely with the number of Rydberg excitations, preventing convergence to non-MIS states. Benchmarking our degree-dependent MIS algorithm with the traditional adiabatic algorithm on a set of 1000 MIS instances, we demonstrate numerically that our algorithm inflates the minimal spectral gap and, consequently, accelerates the convergence. By fitting power-law relations for both the time-to-solution and success probability metrics as a function of the hardness parameter, we demonstrate a superior scaling exponent for our algorithm over the traditional global protocol. Furthermore, the classical Hamiltonian engineering step required to construct degree-dependent controls introduces only polynomial overhead. These results indicate that our algorithm can be used to extend the size of graphs for which MIS can be found on physical hardware. Moreover, our approach extends beyond MIS to additional graph problems such as MAX-CUT.