Efficient Hamiltonian Engineering for Adiabatic MIS Algorithms
Guy Karni 1 , Noam Cohen 2 , Adi Pick 3,∗ · 2026
Read Efficient Hamiltonian Engineering for Adiabatic MIS Algorithms by Guy Karni 1 , Noam Cohen 2 , Adi Pick 3,∗ (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-16944.txt.
Introduction
Karni, Cohen and Pick present a quantum adiabatic algorithm for maximum independent set problems on Rydberg atoms, engineered from graph degrees. It extends an earlier method that excites atoms under global controls while the Rydberg blockade blocks neighbouring excitations. Local light shifts favour low-degree nodes, and the final Hamiltonian is constrained so energy scales inversely with excitation count, steering away from non-independent-set states. On one thousand test instances, their degree-dependent method widens the minimal spectral gap and scales better than the standard global protocol.
Catalog record
| CREATOR | Guy Karni 1 , Noam Cohen 2 , Adi Pick 3,∗ |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 42503 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.16944
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Efficient Hamiltonian Engineering for Adiabatic MIS Algorithms Guy Karni 1 , Noam Cohen 2 , Adi Pick 3,∗ Abstract We present a hybrid adiabatic algorithm for maximum independent set (MIS) using Rydberg atom arrays. We engineer local controls that preferentially excite atoms with few neighbors, which represent graph nodes with small degrees. Numerical simulations show that the designed pulses accelerate convergence to the MIS state and suppress population in trap states. We obtain higher success probabilities than traditional global controls and a 25 % 25\% reduction in fidelity decay rate as problem hardness increases. Neutral atom arrays are a promising platform for solving graph optimization problems Ebadi et al. 2022 ; Graham et al. 2022 ; Kim et al. 2022 . Specifically, the maximum independent set (MIS) problem — defined as finding the largest subset of non-adjacent vertices in a graph — can be mapped onto the preparation of an atom array in a state with maximal number of Rydberg excitations Pichler et al. 2018 . Adiabatic and adiabatic-inspired algorithms were implemented on Rydberg arrays containing hundreds of atoms Bernien et al. 2017 ; Ebadi et al. 2022 ; Kim et al. 2024 ; De Oliveira et al. 2025 . 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 Sachdev 1999 and that limits the time complexity of AQC Farhi et al. 2000 ; Albash and Lidar 2018 . We propose a modified adiabatic algorithm that effectively inflates the gap and reduces the time-complexity of existing algorithms. Our approach is based on the observation that vertices of smaller degrees are more likely to belong to the MIS, and vice versa. 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. 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\in\text{MIS})\approx(1-|\text{MIS}|/N)^{d_{i}} where N is the number of graph nodes, d_{i} is the degree of node i , and |\text{MIS}| is the MIS size. Guided by this observation, we choose degree-dependent detuning profiles for the control fields that favor excitation of atoms with small LDs [Fig. 1 (c)]. Our work is inspired both by quantum adiabatic algorithms that use heuristic initial states for accelerated convergence Perdomo-Ortiz et al. 2011 ; King et al. 2019 ; Passarelli et al. 2020 ; Developers 2021 and by classical MIS algorithms that use LDs Alon et al. 1986 ; Fomin et al. 2006 ; Halldórsson and Radhakrishnan 1994 . We refer to our Hamiltonian-engineering approach as ”local-degree adiabatic quantum computation” (LD-AQC), and analyze its performance on thousands of disordered King’s graphs with a random distribution of holes. Benchmarking LD-AQC with the traditional AQC algorithm from Ref. Pichler et al. 2018 , we find an increased average fidelity and improved scaling of the computational error upon increasing problem hardness (Fig. 3 ). Fig. 1: (a) King’s graph with vertices labeled by their degrees. Colored vertices highlight independent sets (IS) of size 3, 4, and 5. (b) Probability that a vertex belongs to the MIS versus degree. Numerical average over 10,000 King’s graphs (red) is compared with the analytic estimate (blue). (c) The LD-AQC algorithm uses linear detuning profiles, \Delta_{i}(t) , with smaller degrees corresponding to larger slopes. (d-e) The LD-AQC algorithm (Alg. Efficient Hamiltonian Engineering for Adiabatic MIS Algorithms ) requires finding a critical size ( k^{*} ) and detuning parameter ( a^{*} ). The former is found using the sorted degree table (d) while the latter is found using the eigenvalues of the parameterized Hamiltonian at the final time H(t_{f};a) [Eq. ( 1 )] (e). The critical k^{*} and a^{*} are defined in Alg. Efficient Hamiltonian Engineering for Adiabatic MIS Algorithms . We briefly review the development of MIS AQC with Rydberg atoms since its inception. While the original theoretical proposal from Pichler et al. 2018 suggested adiabatic following of ground states using AQC Farhi et al. 2000 , the experimental realization in Ebadi et al. 2022 used hybrid algorithms, including quantum approximate optimization algorithm (QAOA) Farhi et al. 2014 and variational quantum adiabatic algorithm (VQAA) Schiffer et al. 2022 , to analyze planar graphs with hundreds of vertices. These results were extended to non-planar graphs and various lattice geometries Dalyac and Henriet 2022 ; Dalyac et al. 2023 ; Andrist et al. 2023 ; Kim et al. 2024 ; Pan et al. 2025 . Using polynomial mappings of MIS to other problem in NP, adiabatic algorithms were developed for the weighted MIS problem (WMIS) De Oliveira et al. 2025 , integer factorization Nguyen et al. 2023 , and energy optimization in electric charging Leclerc et al. 2025 . Since the time complexity of AQC algorithms is limited by the minimal gap, various methods for inflating the gap were proposed. These include optimizing the adiabatic schedule numerically Koch et al. 2022 ; Turyansky et al. 2024 or analytically Roland and Cerf 2002 ; Turyansky et al. 2026 , and the introduction of counter-diabatic controls Berry 2009 ; Sels and Polkovnikov 2017 ; Guéry-Odelin et al. 2019 . Quantum algorithms that accelerate AQC using heuristic initial states are particularly related to the present work Crosson and Lidar 2021 . In Perdomo-Ortiz et al. 2011 , an algorithm for k-SAT introduced heuristic initial states along with increased fluctuations that enable escape from local minima while approaching the solution. A similar approach was used to prepare the ground state of the p -spin model, known as “reversed quantum annealing” Developers 2021 ; Chancellor 2017 . A related approach of randomized initial states in AQC was explored in Chancellor 2017 ; King et al. 2019 and realized experimentally with the DWAVE processor Developers 2021 . Finally, we mention classical MIS algorithms that utilize vertex degrees. A widely used greedy algorithm constructs the MIS by iteratively selecting minimum-degree vertices, removing them along with their neighbors, and repeating on the reduced graph Halldórsson and Radhakrishnan 1994 . Another example is a branch-and-reduce method, which constructs the MIS recursively using a degree-dependent graph branching rule Fomin et al. 2006 . Finally, a randomized parallel algorithm for MIS that uses vertex degree for the probability of vertex selection achieves a logarithmic complexity scaling, i.e. \mathcal{O}(\log{N}) compared to exponential complexity of \mathcal{O}(\alpha 2^{N}) of the above-mentioned single-processor algorithms Alon et al. 1986 , 1 1 1 The quoted result for the parallel MIS algorithm assumes a concurrent-read concurrent-write parallel random access machine (CRCW-PRAM) with \mathcal{O}(|E|d_{\mathrm{max}}) processors, with |E| denoting the number of edges and d_{\mathrm{max}} the maximum degree. . Motivated by the speedup gained by heuristic AQC algorithms and that of degree-based classical MIS algorithms, we develop a degree-based heuristic for accelerating the traditional AQC MIS algorithm. The AQC MIS algorithm: Finding a MIS of a unit-disc graph G(V,E) is equivalent to finding the ground state of a Rydberg-atom array Pichler et al. 2018 . Each vertex V is encoded in an atomic qubit with a ground hyperfine and an excited Rydberg state, while edges E connect