Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2602.17991 · Journal of Physics B Atomic Molecular and Optical Physics

Enhanced Maximum Independent Set Preparation with Rydberg Atoms Guided by the Spectral Gap

Seokho Jeong, Minhyuk Kim

quant-phSubmitted Feb 20, 2026• Announced Feb 23, 2026• 0 citations
arXivHTMLPDF

Abstract

Adiabatic quantum computation with Rydberg atoms provides a natural route for solving combinatorial optimization problems such as the maximum independent set (MIS). However, its performance is fundamentally limited by the reduction of the spectral gap with increasing system size and connectivity, which induces population leakage from the ground state during finite-time evolution. Here we introduce the Adjusted Detuning for Ground-Energy Leakage Blockade (ADGLB), a spectral-gap-guided schedule engineering method that modifies the laser detuning profile to suppress leakage without introducing additional Hamiltonian terms or iterative optimization loops. We experimentally benchmark ADGLB on a quasi-one-dimensional chain of $N=10$ atoms, and the MIS preparation probability increases substantially compared with the standard adiabatic schedule. Furthermore, we show that the schedule optimized for smaller instances can be directly applied to larger two-dimensional triangular lattices with $N=25$ and $N=37$. With a small heuristic offset, the method also remains effective for instances with higher hardness parameters. These findings demonstrate that spectral-gap-guided schedule engineering offers a scalable and hardware-efficient strategy for enhancing adiabatic quantum optimization on neutral-atom platforms.

Related papers

Degree-Guided Adiabatic Quantum Algorithm for MIS with Neutral Atoms

Guy Karni, Noam Cohen, Adi Pick

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.

quant-pharXiv:2605.16944•May 19, 2026•0 citations

Approximating Maximum Independent Set on Rydberg Atom Arrays Using Local Detunings

Hyeonjun Yeo, Ha Eum Kim, Kabgyun Jeong

Abstract Rydberg atom arrays operated by a quantum adiabatic principle are among the most promising quantum simulating platforms due to their scalability and long coherence time. From the perspective of combinatorial optimization, they offer an efficient solution for an intrinsic maximum independent set problem because of the resemblance between the Rydberg Hamiltonian and the cost function of the maximum independent set problem. In this study, a strategy is suggested to approximate maximum independent sets by adjusting local detunings on the Rydberg Hamiltonian according to each vertex's vertex support, which is a quantity that represents connectivity between vertices. By doing so, the strategy successfully reduces the error rate three times for the checkerboard graphs with defects when the adiabaticity is sufficient. In addition, the strategy decreases the error rate for random graphs even when the adiabaticity is relatively insufficient. Moreover, it is shown that the strategy helps to prepare a quantum many‐body ground state by raising the fidelity between the evolved quantum state and a 2D cat state on a square lattice. Finally, the strategy is combined with the non‐abelian adiabatic mixing and this approach is highly successful in finding maximum independent sets compared to the conventional adiabatic evolution with local detunings.

arXiv:2402.09180•Advanced Quantum Technologies•Sep 26, 2024•4 citations

Quantum Optimization for Maximum Independent Set Using Rydberg Atom Arrays

Hannes Pichler, Sheng-Tao Wang, Leo Zhou +2 more

We describe and analyze an architecture for quantum optimization to solve maximum independent set (MIS) problems using neutral atom arrays trapped in optical tweezers. Optimizing independent sets is one of the paradigmatic, NP-hard problems in computer science. Our approach is based on coherent manipulation of atom arrays via the excitation into Rydberg atomic states. Specifically, we show that solutions of MIS problems can be efficiently encoded in the ground state of interacting atoms in 2D arrays by utilizing the Rydberg blockade mechanism. By studying the performance of leading classical algorithms, we identify parameter regimes, where computationally hard instances can be tested using near-term experimental systems. Practical implementations of both quantum annealing and variational quantum optimization algorithms beyond the adiabatic principle are discussed.

arXiv:1808.10816•Aug 31, 2018•34 citations

Circumventing superexponential runtimes for hard instances of quantum adiabatic optimization

Benjamin F. Schiffer, Dominik S. Wild, Nishad Maskara +3 more

Classical optimization problems can be solved by adiabatically preparing the ground state of a quantum Hamiltonian that encodes the problem. The performance of this approach is determined by the smallest gap encountered during the evolution. Here, we consider the maximum independent set problem, which can be efficiently encoded in the Hamiltonian describing a Rydberg atom array. We present a general construction of instances of the problem for which the minimum gap decays superexponentially with system size, implying a superexponentially large time to solution via adiabatic evolution. The small gap arises from locally independent choices which cause the system to initially evolve and localize into a configuration far from the solution in terms of Hamming distance. We investigate remedies to this problem. Specifically, we show that quantum quenches in these models can exhibit signatures of quantum many-body scars, which in turn, can circumvent the superexponential gaps. By quenching from a suboptimal configuration, states with a larger ground-state overlap can be prepared, illustrating the utility of quantum quenches as an algorithmic tool. Published by the American Physical Society 2024

arXiv:2306.13131•Physical Review Research•Mar 12, 2024•18 citations

Hardness-dependent quantum adiabatic schedules for the maximum-independent-set problem

Sébastien Perseguers

We propose a numerical approach to design highly efficient adiabatic schedules for analog quantum computing, focusing on the maximum-independent-set problem and neutral atom platforms. On the basis of a representative dataset of small graphs, we present numerical evidence that the optimum schedules depend principally on the hardness of the problem rather than on its size. These schedules perform better than the benchmark protocols and admit a straightforward implementation in the hardware. This allows us to extrapolate the results to larger graphs and to successfully solve moderately hard problems using QuEra’s 256-qubit Aquila computer. We believe that extending our approach to hybrid algorithms could be the key to solving the hardest instances with the current technology, making yet another step toward real-world applications.

arXiv:2410.08995•Physical Review Applied•Jun 10, 2025•3 citations

Avoid First Order Quantum Phase Transition by Changing Problem Hamiltonians

Vicky Choi

In Amin and Choi \cite{AC09}, we show that an adiabatic quantum algorithm for the NP-hard maximum independent set (MIS) problem on a set of special family of graphs in which there are exponentially many local maxima would have the exponentially small minimum spectral gap and thus would require the exponential time, due to the first order quantum phase transition (FQPT). The problem Hamiltonian of the adiabatic quantum algorithm for MIS is based on the reduction to the Ising problem and has flexible parameters. In this paper, we show numerically on the 15-vertex graph that by choosing the parameters appropriately in the problem Hamiltonian (without changing the problem to be solved) for MIS, we can prevent the FQPT and drastically increase the minimum spectral gap. The result is further supported by visualization from the Decomposed State Evolution Visualization (\desev) --- a visualization tool we introduced. Furthermore, our result also serves to concretely clarify that it is not sufficient to consider one specific problem Hamiltonian for proving the failure of adiabatic quantum optimization for a problem. We also raise the basic question about what the appropriate formulation of adiabatic running time should be.

arXiv:1010.1220•Oct 6, 2010•6 citations
Adiabatic quantum computation with Rydberg atoms provides a natural route for solving combinatorial optimization problems such as the maximum independent set (MIS). However, its performance is fundamentally limited by the reduction of the spectral gap with increasing system size and connectivity, which induces population leakage from the ground state during finite-time evolution. Here we introduce the Adjusted Detuning for Ground-Energy Leakage Blockade (ADGLB), a spectral-gap-guided schedule engineering method that modifies the laser detuning profile to suppress leakage without introducing additional Hamiltonian terms or iterative optimization loops. We experimentally benchmark ADGLB on a quasi-one-dimensional chain of N=10N=10N=10 atoms, and the MIS preparation probability increases substantially compared with the standard adiabatic schedule. Furthermore, we show that the schedule optimized for smaller instances can be directly applied to larger two-dimensional triangular lattices with N=25N=25N=25 and N=37N=37N=37. With a small heuristic offset, the method also remains effective for instances with higher hardness parameters. These findings demonstrate that spectral-gap-guided schedule engineering offers a scalable and hardware-efficient strategy for enhancing adiabatic quantum optimization on neutral-atom platforms.
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.
Abstract Rydberg atom arrays operated by a quantum adiabatic principle are among the most promising quantum simulating platforms due to their scalability and long coherence time. From the perspective of combinatorial optimization, they offer an efficient solution for an intrinsic maximum independent set problem because of the resemblance between the Rydberg Hamiltonian and the cost function of the maximum independent set problem. In this study, a strategy is suggested to approximate maximum independent sets by adjusting local detunings on the Rydberg Hamiltonian according to each vertex's vertex support, which is a quantity that represents connectivity between vertices. By doing so, the strategy successfully reduces the error rate three times for the checkerboard graphs with defects when the adiabaticity is sufficient. In addition, the strategy decreases the error rate for random graphs even when the adiabaticity is relatively insufficient. Moreover, it is shown that the strategy helps to prepare a quantum many‐body ground state by raising the fidelity between the evolved quantum state and a 2D cat state on a square lattice. Finally, the strategy is combined with the non‐abelian adiabatic mixing and this approach is highly successful in finding maximum independent sets compared to the conventional adiabatic evolution with local detunings.
We describe and analyze an architecture for quantum optimization to solve maximum independent set (MIS) problems using neutral atom arrays trapped in optical tweezers. Optimizing independent sets is one of the paradigmatic, NP-hard problems in computer science. Our approach is based on coherent manipulation of atom arrays via the excitation into Rydberg atomic states. Specifically, we show that solutions of MIS problems can be efficiently encoded in the ground state of interacting atoms in 2D arrays by utilizing the Rydberg blockade mechanism. By studying the performance of leading classical algorithms, we identify parameter regimes, where computationally hard instances can be tested using near-term experimental systems. Practical implementations of both quantum annealing and variational quantum optimization algorithms beyond the adiabatic principle are discussed.
Classical optimization problems can be solved by adiabatically preparing the ground state of a quantum Hamiltonian that encodes the problem. The performance of this approach is determined by the smallest gap encountered during the evolution. Here, we consider the maximum independent set problem, which can be efficiently encoded in the Hamiltonian describing a Rydberg atom array. We present a general construction of instances of the problem for which the minimum gap decays superexponentially with system size, implying a superexponentially large time to solution via adiabatic evolution. The small gap arises from locally independent choices which cause the system to initially evolve and localize into a configuration far from the solution in terms of Hamming distance. We investigate remedies to this problem. Specifically, we show that quantum quenches in these models can exhibit signatures of quantum many-body scars, which in turn, can circumvent the superexponential gaps. By quenching from a suboptimal configuration, states with a larger ground-state overlap can be prepared, illustrating the utility of quantum quenches as an algorithmic tool. Published by the American Physical Society 2024
We propose a numerical approach to design highly efficient adiabatic schedules for analog quantum computing, focusing on the maximum-independent-set problem and neutral atom platforms. On the basis of a representative dataset of small graphs, we present numerical evidence that the optimum schedules depend principally on the hardness of the problem rather than on its size. These schedules perform better than the benchmark protocols and admit a straightforward implementation in the hardware. This allows us to extrapolate the results to larger graphs and to successfully solve moderately hard problems using QuEra’s 256-qubit Aquila computer. We believe that extending our approach to hybrid algorithms could be the key to solving the hardest instances with the current technology, making yet another step toward real-world applications.
In Amin and Choi \cite{AC09}, we show that an adiabatic quantum algorithm for the NP-hard maximum independent set (MIS) problem on a set of special family of graphs in which there are exponentially many local maxima would have the exponentially small minimum spectral gap and thus would require the exponential time, due to the first order quantum phase transition (FQPT). The problem Hamiltonian of the adiabatic quantum algorithm for MIS is based on the reduction to the Ising problem and has flexible parameters. In this paper, we show numerically on the 15-vertex graph that by choosing the parameters appropriately in the problem Hamiltonian (without changing the problem to be solved) for MIS, we can prevent the FQPT and drastically increase the minimum spectral gap. The result is further supported by visualization from the Decomposed State Evolution Visualization (\desev) --- a visualization tool we introduced. Furthermore, our result also serves to concretely clarify that it is not sufficient to consider one specific problem Hamiltonian for proving the failure of adiabatic quantum optimization for a problem. We also raise the basic question about what the appropriate formulation of adiabatic running time should be.